정렬 알고리즘 - 선택 정렬(Selection Sort)

선택 정렬(Selection Sort)

• 기초적인 정렬 알고리즘(선택 정렬, 버블 정렬, 삽입정렬) 중 하나
• 전체 원소들 중에서 기준 위치에 맞는 원소를 선택하여 자리를 교환하는 방식으로 정렬
  
  
• 수행 방법
• 전체 원소 중에서 가장 작은 원소를 찾아서 선택하여 첫 번째 원소와 자리를 교환한다.
• 그 다음 두 번째로 작은 원소를 찾아 선택하여 두 번째 원소와 자리를 교환한다.
• 그 다음에는 세 번째로 작은 원소를 찾아서 세 번째 원소와 자리를 교환한다.
• 이 과정을 반복하면서 정렬을 완성한다.
  
  
• 선택 정렬 수행 과정
• 정렬 되지 않은 {69, 10, 30, 2, 16, 8, 31, 22}의 자료들을 선택정렬 방법으로 정렬하는 과정을 살펴보자.
  
  1. 첫 번째 자리를 기준 위치로 정하고, 전체 원소 중에서 가장 작은 원소 2를 선택하여 기준 위치에 있는 원소 69 와 자리를 교환한다.
  

   

  
  2. 두 번째 자리를 기준 위치로 정하고 나머지 원소 중에서 가장 작은 원소 8을 선택하여 기준 위치에 있는 원소 10과 자리를 교환한다.



 

3. 세 번째 자리를 기준 위치로 정하고, 나머지 원소 중에서 가장 작은 원소 10을 선택하여 기준 위치에 있는 원소 30과 자리를 교환한다.




 
4. 네 번째 자리를 기준 위치로 정하고, 나머지 원소 중에서 가장 작은 원소 16을 선택하여 기준 위치에 있는 원소 69와자리를 교환한다.

 




5. 다섯 번째 자리를 기준 위치로 정하고, 나머지 원소 중에서 가장 작은 원소 22를 선택하여 기준 위치에 있는 원소 69와 자리를 교환한다.





6. 여섯 번째 자리를 기준 위치로 정하고, 나머지 원소 중에서 가장 작은 원소 30을 선택하여 기준 위치에 있는 30과 자리를 교환한다. (자기자신 교환 = 제자리)



 

7. 일곱 번째 자리를 기준 위치로 정하고, 나머지 원소 중에서 가장 작은 원소 31을 선택하여 기준 위치에 있는 원소 31과 자리를 교환한다. (위와 마찬가지 경우임)



 

• 선택 정렬 알고리즘
  
  

• 선택 정렬 알고리즘 분석
• 메모리 사용공간
• n개의 원소에 대하여 n개의 메모리 사용
  
  
• 비교 횟수
• 1단계 : 첫 번째 원소를 기준으로 n개의 원소 비교
• 2단계 : 두 번째 원소를 기준으로 마지막 원소까지 n-1개의 원소 비교
• 3단계 : 세 번째 원소를 기준으로 마지막 원소까지 n-2개의 원소 비교
• i 단계 : i 번째 원소를 기준으로 n-i개의 원소 비교
  
  
• 어떤 경우에서나 비교횟수가 같으므로 시간 복잡도는 O(n²)이다