선택 정렬 (Selection Sort)

정렬 알고리즘

 

선택 정렬 (Selection Sort) 

기초적인 정렬 방법 중 하나입니다. 

배열에서 가장 작은 값을 찾아서 맨 앞에 숫자와 교환합니다. 이 작업을 반복하여 앞에서부터 작은 값을 채워 정렬을 완성합니다. 가장 작은 값을 선택해서 선택 정렬 입니다. 

시간 복잡도는 O(N^2) 입니다. 버블 정렬 보단 빠르고 삽입 정렬 보단 느립니다.

 

평균적인 정렬 속도 : 버블 < 선택 < 삽입 

 

선택 정렬은 이해하기 쉽고 구현하기 간단하지만 효율성은 낮은 편입니다. 각 요소를 나머지 모든 요소와 비교해야 하기 때문입니다. 대규모 데이터셋에는 효과적이지 않고 작은 데이터셋에서 사용합니다. 

 

 

동작 과정

시간 복잡도 : O(n^2)

 

1. 최소값 탐색 : 주어진 배열에서 최소값을 찾습니다. 

2. 최소값과 교환: 배열의 첫 번째 위치에 있는 값과 최소값을 교환합니다. 이로써 첫 번째 배열의 요소가 정렬됩니다.

3. 반복 : 배열의 두 번째 요소부터 마지막 요소까지 같은 과정을 반복합니다. 

 

 

예시

초기 배열

int[] array = {3,1,4,2,6,5}; 

3

1

4

2

6

5

 

 

1부터 5까지 중 최소값을 구한다. 최소값은 인덱스 1에 위치한 1이다. 

이 최소값과 0의 위치를 교환한다. 

1

3

4

2

6

5

 

 

2부터 5까지 최소값을 구한다. 최소값은 인덱스 3에 위치한 2이다.

이 최소값과 1의 위치를 교환한다.

1

2

4

3

6

5

 

 

이런 식으로 나머지 부분들을 진행하여 정렬을 완성한다. 

1

2

3

4

5

6

 

 

 

 

Java 코드 구현

/*
선택 정렬(Selection Sort)
시간 복잡도 : O(n^2)
가장 작은 값을 찾은 다음 첫 번째 인덱스에 넣는다.
이 과정을 처음부터 끝까지 반복하여 정렬을 완성한다.
 */
public class SelectionSort {

  public static void main(String[] args) {
    int[] array = {3,1,5,9,4,8,7};
    printArray(array);
    selectionSort(array);
    printArray(array);
  }

  // 선택 정렬 시작
  public static void selectionSort(int[] array) {
    selectionSort(array, 0);
  }

  // 선택 정렬 로직 수행
  public static void selectionSort(int[] array, int start) {
    if(start < array.length-1) {

      // 작은 인덱스 탐색
      int min_index = start;
      for(int i = start; i < array.length; i++) {
        if(array[i] < array[min_index]) min_index = i;
      }

      // 탐색한 작은 인덱스를 맨 앞에 인덱스랑 교환
      swap(array, start, min_index);

      // 다음 인덱스의 값 탐색
      selectionSort(array, start + 1);
    }
  }

  public static void swap(int[] array, int index1, int index2) {
    int temp = array[index1];
    array[index1] = array[index2];
    array[index2] = temp;
  }

  public static void printArray(int[] array) {
    for(int number : array) {
      System.out.print(number + " ");
    }
    System.out.println();
  }

}

 

 

 

마무리

다음에는 삽입 정렬에 대해 정리하겠습니다.

 

 

 

참고 사이트

버블 정렬, 선택 정렬, 삽입 정렬

https://www.youtube.com/watch?v=Bor_CRWEIXo&t=1s

 

선택 정렬 자바로 구현

https://www.youtube.com/watch?v=uCUu3fF5Dws&t=1s