정렬

정렬

1. 선택정렬

• 범위 중 가장 작은 데이터(최소값)를 맨 앞에 있는 데이터와 바꾸기 -> 반복
• 앞에서부터 정렬됨

2. 삽입정렬

• 두번째 데이터부터 시작
• 데이터 앞에 위치한 데이터들 중 적절한 위치에 삽입 -> 데이터보다 작은 데이터 뒤에 위치

3. 버블정렬

• 앞뒤에 위치한 데이터 중 큰 수를 뒤로 보내기
• 뒤에서부터 정렬됨

1. 선택정렬

int main() {
    
    int N,temp;
    int arr[MAXN];

    scanf("%d",&N);
    
    for(int i=0; i < N; i++){
        scanf("%d",&arr[i]);
        
    }
    
    for(int i=0; i < N-1; i++){
        int minIndex=0;
        int minNum=2147483647;
        
        for(int j=i;j < N;j++){
            if(minNum>arr[j]){ //최소찾기
                minIndex=j;
                minNum=arr[j];
            }
        }
        
        if(minNum<arr[i]){
            swap(arr[minIndex],arr[i]);
        }
        
    }
    
    for(int i=0;i<N;i++){
        printf("%d ",arr[i]);
    }
    
    return 0;
}

2. 삽입정렬

int main() {
    int N;
    int arr[MAXN];
    
    scanf("%d",&N);
    
    for(int i=0;i < N;i++){
        scanf("%d",&arr[i]);
    }
    
    for(int i=1;i < N;i++){
        int val=arr[i];
        for(int j=i-1;j>=0;j--){
            if(val<arr[j]){
                arr[j+1]=arr[j];
            }else{
                break;
            }
        }
        arr[j+1]=val;
    }
    
    for(int i=0;i<N;i++){
        printf("%d ",arr[i]);
    }
    
    return 0;
}

3. 버블정렬

int main() {
    int N;
    int arr[MAXN];
    
    scanf("%d",&N);
    
    for(int i=0;i < N;i++){
        scanf("%d",&arr[i]);
    }
    
    for(int i=0;i < N-1;i++){
        for(int j=0;j < N-i-1;j++){
            if(arr[j]>arr[j+1]){
                swap(arr[j],arr[j+1]);
            }
        }
    }
    
    for(int i=0;i<N;i++){
        printf("%d ",arr[i]);
    }
    
    return 0;
}