[정렬] 선택정렬

안녕하세요.

정렬에는 선택, 버블, 삽입 등 여러가지가 있는데요~

정렬시리즈를 포스팅할거고 그 중 선택정렬에 대해 적으려합니다.

 

 

 

선택정렬

 

주어진 원소 중에서 가장 작은 키값을 갖는 원소를 선택하여 차례대로 나열하는 정렬방식.

 

 

 

 

선택정렬의 원리

 

1. 먼저 정렬이 안된 데이터가 있다고 할 때

 

 

 

2. 가장 작은 수를 선택해 뽑아냅니다.

 

 

3. 마찬가지로 다음으로 작은 수를 선택해 뽑아냅니다.

 

 

 

4. 계속 선택해 뽑는중.....

 

 

 

5. 마지막에 남는 99까지 뽑으면 정렬이 완료됩니다.

 

이게 선택정렬의 원리인데요.

그렇다면 해당 원소들 중에 가장 작은 값은 어떻게 찾을 수 있을까요?

 

 

 

 

 

선택정렬의 풀이

 

 

1. 정렬이 안된 위와 같은 배열이 있다고 할 때 맨 왼쪽에서 오른쪽으로 최소값을 찾아간다.

 

 

2. 먼저 첫번째 원소인 30을 현재의 최소값으로 두고 다음 원소인 50과 비교한다. 비교했을 때 30이 작으니 아직까지는 최소값유지.

  

 

 

 

3. 그 다음 7과 비교했을 때 7이 작으니 최소값을 7로 교체한다.

 

 

 

 

 

4. 이런식으로 비교하면서 찾다보면 1이 제일 작으므로 최소값이 된다.

 

 

 

 

5. 전부 검색이 끝나면 최소값인 1과 첫번째 원소값이 30을 교환해준다.

 

 

 

 

 

6. 다시 배열의 왼쪽에서 오른쪽으로 이동하면서 최소값을 찾는다. 단, 1은 이미 찾은 최소값이므로 두번째 원소인 50부터 시작한다.

   끝까지 찾았을 경우 7이 최소값이다.

 

 

 

 

7. 1은 고정된 픽이고 그 다음 원소인 50과 최소값인 7 교환하고 7도 고정해준다.

 

 

이런 식으로 다시 왼쪽부터 오른쪽으로 최소값을 선택해 11이고 고정된 픽(1, 7)을 제외한 첫번째 원소인 50과 교환해

정렬 시키는 것을 선택정렬이라고 한다.

 

 

 

 

 

선택정렬의 알고리즘

 

SelectionSort(int _array[], int _n)           // _array는 정렬되지 않은 배열, _n은 원소갯수 {      for(int i = 0; i < _n; ++i)      {           int iMin = i;           for( int j = i + 1; j < _n; ++j)        // 루프 한번 돌면서 최소값 선택          {               if( _array[j] < _array[iMin] )                     iMin = j;                            // 최소값 변경(해당 원소의 위치를 iMin에 담아둔다.)          }                                                       int iTemp = _array[i];            _array[i]= _array[iMin];                // i번째 원소값과 최소값 위치에 있는 값 교체           _array[iMin]= iTemp;      } }

 

 

 

 

선택정렬의 성능

 

선택정렬은 이중 루프로 구성되며 둘 다 입력 배열의 크기 n에 비례하므로 전체 수행시간은

O(

) 이다.

 

 

 

 

 

 

항상 봐주시는 분들 감사합니다~