[알고리즘]선택정렬이란(Selection Sort)

▷ 목표

• 선택정렬 알고리즘을 이해합니다.
• 선택정렬 알고리즘의 특징
• 선택정렬 알고리즘의 시간복잡도를 이해합니다.

▷ 제자리정렬

입력 배열(정렬되지 않은 값들) 이외에 다른 추가 메모리를 요구하지 않는 정렬 방법이며
해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘입니다.

대표적으로 선택정렬, 버블정렬, 삽입정렬 등이 있습니다.

▷ 선택정렬의 개념

배열을 오름차순으로 정렬한다고 했을 때

첫 번째 값을 두 번째 값부터 마지막 값까지 차례대로 비교하여 가장 작은 값을 찾아 첫 번째에 놓고

두 번째 값을 세 번째 값부터 마지막 값까지와 차례대로 비교하여 마찬가지로 그 중 가장 작은 값을 찾아

두 번째 위치에 놓는 과정을 반복하며 정렬을 수행합니다.

이 과정을 계속 반복하면 오름차순으로 정렬됩니다

 

<선택정렬을 통한 배열 오름차순 자바 코드>

public class Main {
    public static int[]  selectionSort(int[] arr){
      for(int i=0, n=arr.length; i<n-1; i++){
        int minIndex = i;
        for(int j=i+1; j<n; j++){
           if(arr[minIndex] > arr[j]){
             minIndex = j;
           }
        }

        // 각 회전마다 최솟값을 찾아 i번째 값과 교환합니다.
        int swapped = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = swapped;
      }

      return arr;
    }

    public static void main(String[] args){
      int[] arr = {8, 2, 5, 6, 9};
      selectionSort(arr); // arr = {2, 5, 6, 8, 9}
    }
  }

▷ 선택정렬의 특징

• 장점

    1. 알고리즘이 단순하며 사용할 수 있는 메모리가 제한적인 경우에 사용시 성능 상의 이점이 있습니다.

    2. 자료 이동 횟수가 미리 결정됩니다.

    3. 비교횟수는 많지만 실제로 교환하는 횟수가 적기때문에 효율적입니다.

• 단점

    1. 안정성을 만족하지 않습니다.

    2. 값이 같은 숫자가 있는 경우에 상대적인 위치가 변경될 수 있습니다.

▷ 선택정렬의 시간복잡도

데이터의 개수가 n개라고 했을 때
첫 번째 회전에서의 비교에서 첫번째 값 ~ n번째 값까지 비교하므로 n-1번
두 번째 회전에서의 비교횟수 두번째 값 ~ n번째 값까지 비교하므로 n-2번

... 
(n-1) + (n-2) + .... + 2 + 1 → n(n-1)/2
즉 주어진 n개의 배열을 정렬하는데 필요한 시간복잡도는 O(n²)입니다.
최선, 평균, 최악의 경우 모두 동일한 시간복잡도를 가집니다.

▷ 참고

• https://en.wikipedia.org/wiki/Selection_sort