Algorithm | Sort : 선택 정렬

선택 정렬 (Selection Sort) ?

출처  https://gmlwjd9405.github.io/2018/05/06/algorithm-selection-sort.html

 선택 정렬은 제자리 정렬 알고리즘 중 하나로 배열의 첫번째 원소를 두번째 원소부터 마지막 원소까지, 그 다음은 두번째 원소를 세번째 원소부터 마지막 원소까지 차례대로 비교하여 가장 작은 수를 배열의 앞에 순서대로 가져다 놓는 정렬이다. 1회전마다 N개의 모든 원소를 전부 검사하며 이를 원소의 갯수(N개)만큼 반복하게 되므로 O(n^2)의 시간복잡도를 가지게 된다.

 

 선택 정렬은 O(N^2)의 시간 복잡도를 가지고 있어 성능이 다른 정렬에 비해 좋지 못하다. 하지만 알고리즘이 단순하며 사용할 수 있는 메모리가 제한적인 경우에 사용하면 좋다. 성능이 좋은 정렬들은 오히려 30 이하의 작은 수에서는 성능이 안좋은 경우가 있다.

 

선택정렬 구현 (in JAVA)

public static void selectionSort(int[] arr) {
  for (int i = 0; i < arr.length; i++) {
    int min_index = i;	// 최소값의 인덱스를 저장할 변수
    for (int j = i+1; j < arr.length; j++) {
      if(arr[min_index] > arr[j]) min_index = j;	// 더 작은 값이 나타나면 min_index 변경
    }
    // 최소값과 기준값을 swap
    int temp = arr[i];
    arr[i] = arr[min_index];
    arr[min_index] = temp;
  }
}

 

 자바를 이용하여 선택정렬을 구현해보았다. 과정은 다음과 같다.

 

1. 기준점의 값과 기준점 뒤에 값들을 전부 비교하여 최솟값을 찾는다.

2. 기준점과 최소값을 교환한다.

3. 기준점을 한칸 뒤로 이동하여 다시 1 - 2번을 반복하여 차례대로 최소값을 찾아낸다.

4. 기준점이 가장 마지막에 도달하면 위의 과정은 종료된다.

---

Reference

 

· 선택 정렬 이란 - https://gmlwjd9405.github.io/2018/05/06/algorithm-selection-sort.html

· 선택 정렬 - https://www.zerocho.com/category/Algorithm/post/57f728c85141fc5fe4f4ca89

· 기본 정렬 알고리즘 요약 정리 - https://hsp1116.tistory.com/33