선택 정렬(Selection Sort)

정렬 알고리즘은 알고리즘에서 가장 먼저 배우는 알고리즘이다.

정렬 알고리즘에는 선택 정렬, 삽입 정렬, 버블 정렬, 합병 정렬, 퀵 정렬, 힙 정렬 등 다양한 정렬 알고리즘이 존재한다.

선택, 삽입, 버블 정렬은 구현이 상대적으로 쉽지만 성능이 좋지 않은 반면, 합병, 퀵, 힙 정렬은 구현이 상대적으로 복잡하지만 성능이 훨씬 좋기 때문에 후자의 정렬들을 사용하는 것을 나는 선호하는 편이다.

하지만 성능의 차이를 알기 위해선 모든 정렬 알고리즘의 원리를 알아야한다. 이번에는 선택 정렬(Seletcion Sort)을 다뤄보겠다.

선택 정렬은 주어진 리스트를 돌면서 가장 작은(큰) 원소를 찾아 정렬된 원소를 제외한 제일 앞의 원소와 교환해주면 되기 때문에 가장 이해하기가 쉽고 단순한 정렬 방법이다.

 

선택 정렬(Selection Sort)의 시간 복잡도는 O(N^2)이다.

 

선택 정렬을 Java로 구현한 코드는 다음과 같다.

public class Main {

	public static void main(String[] args) throws IOException {
		int[] num = {5, 3, 1, 2, 4};
		num = selection_Sort(num.length, num);
		for (int k : num) {
			System.out.print(k + " ");
		}
	}
	
	public static int[] selection_Sort(int n, int[] num) {
		for (int i = 0; i < n - 1; ++i) {
			int index = i;
			for (int j = i + 1; j < n; ++j) {
                //정렬되지 않은 영역에서 가장 작은 원소의 인덱스를 찾음
				if (num[j] < num[index]) {
					index = j;
				}
			}

			int temp = num[i];
			num[i] = num[index];
			num[index] = temp;
		}
		return num;
	}
}