정렬(2) 선택정렬

선택 정렬이라는 것은 순회를 돌며 가장 작은 수를 구하고 그 작은 수와 바꿀 요소값과 비교. 하는 형태이다.

3

5

2

4

1

 

위와 같은 숫자가 있다면

3

5

2

4

1

 

3부터 1까지 즉, [0] ~ [4] 까지 배열 번지에 접근을 하고 그 요소값들을 비교하며 가장 작은 수를 뽑아 

[ 0 ] 에 있는 값과 바꾸겠다라는 뜻이다. 

즉, 1이 가장 작은 최소값이기에  3과 1의 위치는 바뀌게 될 것이다.

1

5

2

4

3

 

위와 같이 말이다.

 

그러고 다음 또 순회를 돌며 다음 최소값을 구한다. 다음 최소값은 2다 그럼 [ 1 ] 요소값과 바꾼다

즉, 5와 2의 위치를 바꾼다.

1

2

5

4

3

 

다음과 같이 말이다.

이런식으로 반복을 하면 최종적으로 다음과 같이 정렬된 결과를 볼 수 있다.

1

2

3

4

5

 

그럼 위 선택정렬 알고리즘의 원리를 이용하여 정렬을 해보자.

 

이번에도 어떻게 하면 선택정렬의 원리를 이용하여 정렬된 결과를 추출해줄 수 있을지 고민해보자.

 

자~ 고민했다고 가정하에 소스 코드를 보이겠다.

 

#include <iostream>

int main() { 
    int array [] {3,5,2,4,1};
    int temp; int small; 
    
    for (int i=0; i<4; i++) {
        small = i;
        for (int j=i; j<4; j++) { 
            if (array[small]>array[j+1]) { 
                small = j+1;
            }
        }
        temp = array[i];
        array[i] = array[small];
        array[small] = temp;
    }
    
    
    for (int i=0; i<5; i++) { std::cout<<array[i]<<' '; }
    
}

 

 

위와 같은 방법도 있고

 

다음과 같은 방법도 있다

 for (int i=0; i<4; i++) { 
         int small = i; //핵심1
         for (int j=i+1; j<=4; j++) { 
             if (array[small]>array[j]) { 
                 small = j; // 핵심2 이야.
             }
        }
         temp = array[i];
         array[i] = array[small];
         array[small] = temp;    
}