[정렬] 선택정렬 (selection Sort)

1. 개요

 정렬 알고리즘에 하나로 비교하기 위한 자료를 선택한 후 나머지 자료들과 비교를 통해 정렬이 이루어지는 알고리즘이다.

2. 소스코드

import java.util.Arrays;   public class SelectionSort {          public static void main(String[] args) {                           int[] sampleArray = {3,6,1,8,4,9,10,2};                           // 정렬전 배열 출렬              System.out.println("정렬전 배열 :  " + Arrays.toString(sampleArray));                           // 정렬후 배열 출력              System.out.println("정렬후 배열 :  " + Arrays.toString(selectionSort(sampleArray)));                     }               public static int[] selectionSort(int[] array) {              int switchIndex;                           for (int i = 0; i < array.length - 1; i++) {                     switchIndex = i;                                         // 가장 작은 부분 찾기                     for (int j = i + 1; j < array.length; j++) {                            if (array[j] < array[switchIndex]) {                                  switchIndex = j;                            }                     }                       int tempNumber = array[i];                     array[i] = array[switchIndex];                     array[switchIndex] = tempNumber;              }                                return array;        } }

3. 출력 결과

4. 소스 설명

SelectionSort 함수는 매개변수로 int형 배열을 받으며, 바깥쪽에 for문에서 선택하여 정렬할 위치를 지정해주며,  안쪽에 for문에서는 비교할 대상을 지정해준다. 비교 대상에 가장 작은 값을 찾기 위해 switchIndex를 이용하며 비교 대상중 가장 작은 값에 배열 index값을 저장한다. 안쪽에 for문이 종료되면 가장 작은 값과 현재 선택비교한 값을 교환해주며 배열의 길이 만큼 반복하면 정렬된 배열을 확인 할 수 있다.

5. 복잡도

선택정렬 알고리즘은 배열의 길이 만큼 for문을 수행한다. 가장 바깥쪽에 for문은 배열의 길이 만큼 수행되므로 배열의 길이가 N일 경우 N - 1만큼 반복된다. 여기서 상수는 무시 할 수 있는 수준이라 생략가능하다. 안쪽에 for문은 N의 값에 -1 만큼 덜 수행한다. 따라서 공식화 하면 (n - 1) (n - 1) /2 만큼 수행되며, 일반 상수 값은 무시해도 복잡도에 이슈가 없기 때문에 총

Θ(n^2)의 복잡도를 가진다.

예 ) N = 5일 경우 (4 * 4) / 2 수행됨.

6. 정리

선택정렬에 경우 정려해야 하는 값이 많아질 수록 n^2만큼 기하 급수적으로 수행시간이 늘어난다. 비교적 쉽게 작성할 수 있는 정렬 인 만큼 안정성있지만 복잡도가 높은 알고리즘인 만큼 수행 시간이 느리다는 단점이 있다.

* 선택정렬 관련된 재미난 영상이다.