알고리즘91 :: 응용 알고리즘(선택정렬, 버블정렬, 삽입정렬)

ㅡ. 선택정렬

나열되어 있는 숫자를 차례대로 비교해보면서 가장 작은 수를 맨 앞에 두는 정렬 방법입니다.

e.g) 8, 5, 6, 2, 4 

첫번째 정렬

5, 8, 6, 2, 4 (첫번째 자리와 두번째 자리를 swap, 더 작은 쪽이 앞으로) => 그 다음에 5와 6을 비교합니다.

5, 8, 6, 2, 4 (5가 더 작으므로 현 상태 유지) => 그 다음에 5와 2를 비교 합니다.

2, 8, 6, 5, 4 (2가 더 작은 수 이므로 5, 2 swap) => 그 다음에 2와 4를 비교합니다. 

2, 8, 6, 5, 4 (2, 4 중 2가 더 작으므로 변화 없음) 

 

두번째 정렬

2, 8, 6, 5, 4 상태에서 8을 기준으로 (첫번째 정렬에서 첫번째 위치를 봤으므로 다음위치를 보게 됩니다.) => 8과 6을 비교

2, 6, 8, 5, 4 (6과 5를 비교, 5가 더 작은 수 이므로 swap)

2, 5, 8, 6, 4 (5와 4를 비교, 4가 더 작은 수 이므로 swap)

2, 4, 8, 6, 5 

 

세번째 정렬

2, 4, 8, 6, 5 상태에서 8을 기준으로(두번째 정렬에서 두번째 위치를 봤으므로 다음위치를 보게 됩니다. ) => 8과 6을 비교

2, 4, 6, 8, 5 (6과 5를 비교, 5가 더 작은 수 이므로 swap)

2, 4, 5, 8, 6 

 

네번째 정렬

2, 4, 5, 8, 6 에서 8을 기준으로(세번째 정렬에서 세번째 위치를 봤으므로 다음위치를 보게 됩니다.) => 8과 6을 비교

2, 4, 5, 6, 8 (정렬 완료)

 

수도코드로 구현해보면 다음과 같습니다. 

 

i = 0;

for(int k=0; k<8; k++){

    j = i;

    for(int m=k+1; j<9; j++){

           if( data[i] > data[j] ) 

            {

                 swap(data[i], data[j]);

            }

     }

}

 

ㅡ. 버블 정렬 

버블 정렬은 첫 번째, 두번 째 혹은 두번 째 세번 째 이런식으로 n-1 과 n 번째를 비교하여 맨 끝에는 가장 큰 수가 놓이게 되면서 정렬에서 제외되는 특징이 있다. 

e.g) 8, 5, 6, 2, 4

첫번째 정렬

 8, 5, 6, 2, 4 (8과 5를 비교한다. 8이 더 크므로 swap 한다.) => 5, 8, 6, 2, 4 (8과 6을 비교한다. 8이 더 크므로 swap 한다.) => 5, 6, 8, 2, 4 (8과 2를 비교한다. 8이 더 크므로 swap 한다.) => 5, 6, 2, 8, 4 (8과 4를 비교한다. 8이 더 크므로 swap 한다.) => 5, 6, 2, 4, 8 (여기에서 8은 정렬에서 제외)

 

두번째 정렬

5, 6, 2, 4, 8 상태에서

5, 6, 2, 4, 8 (5와 6을 비교한다. 6이 더 크므로 swap하지 않는다.) => 5, 6, 2, 4, 8 (6과 2를 비교한다. 6이 더 크므로 swap 한다.) => 5, 2, 6, 4, 8 (6과 4를 비교한다. 6이 더 크므로 swap 한다. ) => 5, 2, 4, 6, 8 (8은 정렬에서 제외 되었으므로 stop) 

 

세번째 정렬

5, 2, 4, 6, 8 상태에서

5, 2, 4, 6, 8 (5와 2를 비교한다. 5가 더 크므로 swap 한다.) => 2, 5, 4, 6, 8 ( 5와 4를 비교한다. 5가 더 크므로 swap 한다.) => 2, 4, 5, 6, 8 ( 6, 8은 정렬에서 제외 되었으므로 stop)

 

네번째 정렬

2, 4, 5, 6, 8 상태에서 

2, 4, 5, 6, 8 (2와 4를 비교한다. 4가 더크므로 swap 하지 않는다.) 

 

수도 코드로 구현해보면 다음과 같습니다.

 

i=0;

for(int k=0; k<9; k++){
        for(int m=0; m<9-k; m++){

             if(data[m] > data[m+1]). swap(data[m], data[m+1]);

      }

}

 

ㅡ. 삽입 정렬

삽입 정렬은 두 번째 자료부터 시작해서 왼쪽의 데이터들과 비교해 삽입할 위치를 지정하고 비교된 데이터들은 오른쪽으로 옮기고 데이터를 삽입하여 정렬 시키는 알고리즘 입니다.

e.g)

8, 5, 6, 2, 4 상태에서

첫번째 정렬

8, 5, 6, 2, 4 (5를 기준으로 합니다. 8과 비교해서 5가 더 작으므로) => 5, 8, 6, 2, 4 

 

두번째 정렬

5, 8, 6, 2, 4 (세번째 자릿수인 6을 기준으로 합니다. 8과 비교해서 6이 더 작으므로 오른쪽으로 옮긴다.) => 5, 6, 8, 2, 4 (6과 5도 비교해줘야 한다. 6을 기준으로 왼쪽에 숫자(5, 8)을 다 본다고 생각해야 함, 더 작은 수 이므로 오른쪽으로 옮기지 않는다.)

 

세번째 정렬

5, 6, 8, 2, 4 (2를 기준으로 8과 비교한다. 2가 더 작은 수 이므로 8을 2의 위치로 옮긴다. = 오른쪽으로 이동) => 5, 6, ( ), 8, 4 (2와 6을 비교해서 2가 6보다 작은 수이므로 6도 오른쪽으로 이동시킨다.) => 5, ( ), 6, 8, 4 => (2와 5를 비교해서 2가 5보다 작은 수 이므로 5도 오른쪽으로 이동시킨다.) => ( ), 5, 6, 8, 4  (2가 첫번째 자리에 위치한다.)

 

네번째 정렬

2, 5, 6, 8, 4 (4를 기준으로 8과 비교한다. 4가 더 작은 수 이므로 8을 4의 위치로 옮긴다. = 오른쪽으로 이동) => 2, 5, 6, ( ), 8 (4와 6을 비교한다. 4가 6보다 작은 수 이므로 6을 오른쪽으로 이동시킨다.) => 2, 5, ( ), 6, 8 (4와 5를 비교한다. 4가 5보다 작은 수이므로 5를 오른쪽으로 이동시킨다.) => 2, ( ), 5, 6, 8 (4가 2보다 큰 수이므로 4를 2의 오른쪽에 위치시킨다.) 

2, 4, 5, 6, 8

 

 

수도코드로 옮기면 다음과 같습니다.

for(int i=0; i<9; i++){

    key = data[i];

    for(int j=i-1; j>=0; j--){

       if(data[j] > key) data[j+1] = data[j];

       else break;

    }

    data[j+1] = key;

}