선택 정렬, 아이디어, 작동 원리, 자바 구현 코드

선택 정렬 

 

비교 기반 알고리즘 중 O(n^2)의 성능을 보이며 가장 작은 값부터 정렬하는 선택 정렬에 대해 알아본다. 

 

아이디어 

 

주어진 데이터 중에서 가장 작은 값부터 차례대로 ‘선택’해서 나열하는 방식

-> n개의 데이터에 대해서 

-> 데이터의 개수 만큼을 반복하면서 

-> 정렬되지 않은 데이터 중에서 가장 작은 값을 선택

-> 선택된 값과 미정렬 데이터 부분의 첫 번째 원소와 교환

 

 

작동 원리 

 

다음과 같은 데이터를 정렬하는 과정을 통해 실제 작동 원리를 살펴보자 .

 

int[] arr1 = {6, 2, 7, 8, 3, 5, 4 };

 

먼저 데이터의 개수 만큼 반복해줄 반복문을 선언한다. 

for (int i = 0; i < n - 1; i++) {

 

 

이후 정렬되지 않은 부분에 대해 최소 값을 찾는 부분이다. 

 

// 미정렬 부분 arr[i..n-1]에서 최솟값 찾기
minIndex = findMinElementIndex(n, sortedArr, i, minIndex);

 

찾았으면 그 최소값과 정렬된 부분의 첫 번째 원소와 자리를 바꾼다. 

 

// 미정렬 부분의 첫 번째 원소와 최솟값 교환
swap(sortedArr, i, minIndex);

 

배열 {6, 2, 7, 1, 8, 3, 5, 4 } 중 가장 작은 값은 1이 될 것이다. 1을 찾은 뒤 맨 앞의 데이터인 6과 자리를 바꾼다. (i)

 

 

 

영상에서와 같이 그후 배열은 

{ 1, 2, 7, 6, 1, 8, 5, 4}가 된다. 

 

이제 1은 정렬이 된 값이며, 2 -> 4까지의 요소들은 정렬되지 않은 데이터이다.

 

그러므로 해당 요소들 중에서 다시 가장 작은 값을 찾고 2와 자리를 바꾼다. 

그런데 최솟값은 2이며 자기 자신이기 때문에 그대로 제자리에 있는다. (ii) 

 

그 다음은 어떻게 될까? 

 

{ 1, 2, 7, 6, 1, 8, 5, 4} 

 

-> 7 ~4 중 최솟값을 찾고 7과 자리를 바꾼다. (iii)

 

이 과정을 반복하여 정렬을 완수한다. 

 

 

 

시간 복잡도 (성능) 

 

 

직관적으로 보면

1) n개의 데이터를 반복하는 반복문

2) 최솟값을 탐색하는 과정에서 반복문

이 중첩되므로 

O(n^2)으로 볼 수 있다. 

 

private static int findMinElementIndex(int n, int[] sortedArr, int i, int minIndex) {
   for (int j = i + 1; j < n; j++) {
      if (sortedArr[j] < sortedArr[minIndex]) {
         minIndex = j;
      }
   }
   return minIndex;
}

 

 

직접 비교 횟수를 계산을 해보면 다음과 같다. 

 

바깥 루프	안쪽 루프
i = 0	n-1
i = 1	n-2
i = 2	n-3
.	.
.	.
.	.
i = n-2	1

 

이므로 

 

(n-1) + (n-2) + (n-3) + ... + 1 = n(n-1) / 2

 

따라서 O(n^2)의 결과를 알 수 있다.

 

 

 

 

특징

 

1. 언제나 동일한 시간 복잡도를 갖는다

-> 최솟값을 찾는 과정이 데이터의 입력과 무관하게 항상 일정하기 때문에 동일한 연산이 반복될 수 밖에 없다.

-> 다른 말로 표현하자면 모든 항목은 최대 2번씩 이동한다. 

 

2. 제자리 정렬 알고리즘이다.

 

3. 안정적인 알고리즘이 아니다.

-> 예를 들어 {10, 20, 40, 40, 30}을 살펴보면 정렬되지 않은 데이터 {40, 40, 30} 순서에서 30이 앞의 40과 자리가 바뀐다. 

 

 

 

 

자바 구현 코드

import java.util.Arrays;

public class SelectionSort {
   public static void main(String[] args) {
      int[] arr1 = {6, 2, 7, 1, 8, 3, 5, 4 };
      int[] sortedArr1 = selectionSort(arr1);
      System.out.println("원본 배열: " + Arrays.toString(arr1) + " 정렬된 배열: " + Arrays.toString(sortedArr1));

      int[] arr2 = {9, 5, 2, 8, 1};
      int[] sortedArr2 = selectionSort(arr2);
      System.out.println("원본 배열: " + Arrays.toString(arr2) + " 정렬된 배열: " + Arrays.toString(sortedArr2));
   }

   public static int[] selectionSort(int[] arr) {
      int n = arr.length;
      int[] sortedArr = Arrays.copyOf(arr, n); // 정렬된 배열을 담을 복사본 생성

      for (int i = 0; i < n - 1; i++) {
         int minIndex = i;

         // 미정렬 부분 arr[i..n-1]에서 최솟값 찾기
         minIndex = findMinElementIndex(n, sortedArr, i, minIndex);

         // 미정렬 부분의 첫 번째 원소와 최솟값 교환
         swap(sortedArr, i, minIndex);
      }
      return sortedArr;
   }

   private static int findMinElementIndex(int n, int[] sortedArr, int i, int minIndex) {
      for (int j = i + 1; j < n; j++) {
         if (sortedArr[j] < sortedArr[minIndex]) {
            minIndex = j;
         }
      }
      return minIndex;
   }

   private static void swap(int[] sortedArr, int i, int minIndex) {
      int temp = sortedArr[i];
      sortedArr[i] = sortedArr[minIndex];
      sortedArr[minIndex] = temp;
   }
}