알고리즘 실습 #2. 우선순위 큐(선택 & 삽입 정렬)

[ 문제 1 ] (선택 정렬) n개의 양의 정수(중복 가능)를 입력받아, 아래에서 설명하는 선택 정렬을 이용하여 정렬하는 프로그램을 작성하시오.

구현해야 할 선택 정렬 알고리즘 (가장 큰 값을 찾는 버전):

 

• 크기가 n인 배열을 동적 할당하여, 입력된 양의 정수 저장(입력 정수는 중복 가능)

• 제자리(in place) 정렬 사용. 즉, 입력 값 저장을 위한 배열 이외에 O(1)의 추가 공간만 사용

• 배열의 뒷부분을 정렬 상태로 유지하고, 매 반복마다 최대 한 번의 교환 연산만 사용

• 매 반복마다 가장 큰 값을 찾아, 오른쪽부터 채우는 방식으로 정렬

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

int main(){
    int n;scanf("%d",&n);
    int *num = (int*)malloc(sizeof(num)*n+1);

    for(int i=0;i<n;i++){scanf("%d",&num[i]);}

    // for(int i=0;i<n;i++){printf("%d ",num[i]);}printf("\n");


    int max,maxdir,tmp;
    for(int i=0;i<n-1;i++){
        max = num[0]; maxdir = 0;
        /*
        10개의 요소가 있을때, 첫번째 요소부터 각가 10,9,8...번째 요소까지 10번 순회
        */
        for(int j=0;j<n-i;j++){if(max < num[j]){max = num[j]; maxdir = j;}} 
        // printf("[%d] in %d\n",max,maxdir);
        
        tmp = num[n-i-1]; 
        num[n-i-1] = num[maxdir]; 
        num[maxdir] = tmp;
        // for(int i=0;i<n;i++){printf("%d ",num[i]);} printf("\n");
    }
    for(int i=0;i<n;i++){printf("%d ",num[i]);}
}
/*
8
8 31 48 73 3 65 20 29
*/

 

문제 풀이

ⅰ. 입력받은 정수값을 저장할 배열을 동적 할당한다.

ⅱ. 반복 횟수 n을 입력받늗다.

ⅲ. 아래 내용을 n-1번 반복 수행한다.

     ① 최댓값을 배열의 첫 번째 값으로 저장한다. 

     ② 최댓값은 n-1번 순회 중 n-i 번째의 값이 더 큰 경우 최신화된다.

     ③ 순회 중 가장 큰 값으로 max와 maxdir(max의 배열 번호)가 최신화된다.

     ④ 순회 종료 후, 배열의 맨 마지막 값과 maxdir 위치의 값을 교환한다.

ⅳ. 배열을 출력한다.

 

위 내용을 좀 더 쉽게 풀이하면 아래와 같다.

 

먼저 선택 정렬이란 배열의 뒷부분을 정렬 상태로 유지하고, 매 반복마다 최대 한 번의 교환 연산만 사용하는 것으로, 매 반복마다 가장 큰 값을 찾아, 오른쪽부터 채우는 방식으로 정렬방식이다.

 

이 말은 즉슨, 순회 중 항상 배열의 맨뒤(순회범위)의 값이 가장 큰 수이어야 한다는 뜻이다.

8 ↦n
8 31 48 73 3 65 20 29

 

위 예시를 생각해 보자.

 

첫 번째 반복에서는 순회 범위가 (8~29)인 것은 당연하다. 각 순회에서 순회 거리는 (n-i)이다. 이때 max값은 초기 배열의 가장 큰 값인 73을 가지며, 이때 maxdir은 73의 배열 인덱스 3을 가진다.

 

순회 거리가 (n-i)이라는 뜻은, 각 반복문이 끝날 때마다 순회거리가 1씩 줄어든다는 것을 의미한다.

 

따라서 첫 번째 반복이 끝나면 초기 배열에서 29와 73의 위치가 바뀌고, 순회 구간은 8에서 7이 된다.

이는 반복문의 조건에서 주어진다.

for(int j=0;j <n-i;j++){... 생략}

 

따라서 각 순회가 이루어질 때마다, 가로축의로 의 범위는 1씩 줄어드며 오른쪽에는 순회 범위 내의 가장 큰 값들이 저장(교환)된다. 정렬 과정은 아래와 같다.

 

8 31 48 73 3 65 20 29 : 기존 배열 8 31 48 29 3 65 20 73  8 31 48 29 3 20 65 73  8 31 20 29 3 48 65 73  8 3 20 29 31 48 65 73  8 3 20 29 31 48 65 73  8 3 20 29 31 48 65 73  3 8 20 29 31 48 65 73  3 8 20 29 31 48 65 73

 

반복문을 통해 모든 순회를 거치면 최종적으로 오른쪽부터 배열의 가장 큰 수가 저장된 배열로 정렬된다.

[ 문제 2 ] (삽입 정렬) n개의 양의 정수를 입력(중복 가능) 받아, 아래에서 설명하는 삽입 정렬을 이용하여 정렬하는 프로그램을 작성하시오.

구현해야 할 삽입 정렬 알고리즘:

• 크기가 n인 배열을 동적 할당하여, 입력된 양의 정수 저장(입력 정수는 중복 가능)
• 제자리(in-place) 정렬 사용. 즉, 입력 값 저장을 위한 배열 이외에 O(1)의 추가 공간만 사용
• 배열의 앞부분을 정렬 상태로 유지

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

int main(){
    int n;scanf("%d",&n);
    int *num = (int*)malloc(sizeof(num)*n+1);

    for(int i=0;i<n;i++){scanf("%d",&num[i]);}
    
    int nowdir,tmp,now;
    for(int i=0;i<n;i++){
        // max = num[0]; maxdir = 0;
        now = num[i]; nowdir = i;
        for(int j=0;j<i+1;j++){
            // if(max < num[j]){max = num[j]; maxdir = j;}
            // printf("now : %d | num[j] = %d\n",now,num[j]);
            if(now < num[j]){
                tmp = num[nowdir]; 
                num[nowdir] = num[j]; 
                num[j] = tmp;
            }
        }
        // for(int i=0;i<n;i++){printf("%d ",num[i]);} printf("\n");

    }
    for(int i=0;i<n;i++){printf("%d ",num[i]);} //printf("\n");
    
}
/*
7
3 73 48 31 8 11 20


3 73 48 31 8 11 20
3 73 48 31 8 11 20
3 48 73 31 8 11 20
3 48 31 73 8 11 20
*/

문제 풀이

ⅰ. 입력받은 정수값을 저장할 배열을 동적 할당한다.

ⅱ. 반복 횟수 n을 입력받늗다.

ⅲ. 아래 내용을 n번 반복 수행한다.

     ① 반복 인덱스(i)와 같은 인덱스의 배열 요소값을 now로 저장한다.

     ②  반복 인덱스(i)를 nowdir로 저장한다.

     ③ 아래 내용을 0에서 i+1번 반복을 순회한다.

          a. 현재 순회 중인 값이 now보다 큰 경우를 확인한다.

          b. 조건을 만족하면 now와 num [j]를 교환한다.

ⅳ. 배열을 출력한다.

 

실행과정을 보면 꽤 복잡해 보인다. 하지만 배열의 스왑 조건과 그 과정을 확인하면 조금 이해하기 쉽다.

먼저 입력 예시가 아래와 같다고 가정해 보자.

7
3 73 48 31 8 11 20

 

먼저 위 알고리즘은 삽입 정렬로, 배열의 앞부분을 정렬 상태로 유지하고 정렬하는 정렬 기법이다.

가장 큰 포인트는 선택 정렬과는 다르게 반복문을 n번 반복해야 한다는 것이다.

 

천천히 흐름을 따라가 보자.초기의 배열 상태는 아래와 같다.

3 73 48 31 8 11 20

 

삽입 정렬은 앞부분을 항상 정렬 상태로 유지해야 하므로, 초기 배열의 순회에서 48에 도달하면 정렬이 필요하다. 왜? 48보다 큰 73이 이전 위치에 존재하기 때문이다.

 

따라서 우리는 이러한 방법을 생각해 볼 수 있다.

 

① 각 순회를 n번 반복하고, 순회 범위는 i까지 설정한다.

② 각 순회에서 가장 큰 값을 찾고, 해당 순회 범위의 마지막과 교환한다.

 

다시 초기의 배열 상태를 생각해 보자.

3 73 48 31 8 11 20

 

우리는 48까지 순회했을 때, 73이 48에 위치로 와야 "정렬"된다는 것을 알 수 있다. 따라서 48까지의 순회에서 가장 큰 값을 저장하고, 순회가 종료되면 해당 순회에서 마지막 배열의 값과 가장 큰 값을 교환하면 된다. 

 

이미 배열의 앞부분은 정렬이 되어있으므로, 해당 순회에서 마지막값과 가장 큰 값을 교환하면 해당 순회 부분은 정렬이 되는 것이다. 다시 말해, 순회의 뒤 부분은 아직 정렬이 안되어 있으며 무시해도 된다는 것이다.

 

아래는 반복문을 순회할 때의 배열의 변화이며, 하이라이트 된 부분은 순회 길이이다.

 

3 73 48 31 8 11 20  3 73 48 31 8 11 20  3 48 73 31 8 11 20  3 31 48 73 8 11 20  3 8 31 48 73 11 20  3 8 11 31 48 73 20  3 8 11 20 31 48 73

 

각 순회에서 가장 큰 값이 순회 범위 맨 뒤로 이동하여 정렬되는 것을 볼 수 있으며, 각 교환은 반복 당 한번 이루어진다.