알고리즘 | 선택정렬

선택 정렬(Selection Sort)

---

• 정렬 되지 않은 데이터들에 대해 가장 작은 데이터를 찾아 가장 앞의 데이터와 교환해나가는 방식
• 선택 정렬의 비교 횟수
  = (n-1) + (n-2) + (n-3) + … + 1
  = n(n-1)/2
• 시간 복잡도
  • 평균, 최악, 최고: O(n^2)
  • 기존의 레코드들이 정렬이 되어 있던, 되어 있지 않던 상관 없이 레코드들의 가장 처음부터 끝까지 비교하는 과정이 모두 같기 때문

동작원리

---

1. 배열의 첫원소를 key값으로 설정하고 나머지 배열 원소 중 가장 작은 원소를 찾아 교체한다.
2. 교체후에 첫 원소를 제외한 두번째 원소를 키 값으로 설정하고 1단계를 반복한다.
3. 나머지 리스트를 모두 정렬이 될 때까지 1, 2 단계를 반복하여 정렬을 완료한다.

예제코드

---

void selectionSort()
{
  intDataSet[]={6,4,2,3,1,5};
  int i, j, indexMin, temp;

  for(i =0; i < n-1; i++){
    indexMin=i;
    for(j = i+1; j < n; j++){
      if(list[j] < DataSet[indexMin]){
        indexMin = j;
      }
    }
    temp=DataSet[indexMin];
    DataSet[indexMin]=DataSet[i];
    DataSet[i]=temp;
  }
}