자바 선택 정렬(Selection Sort) 완벽 가이드: 개념부터 구현까지

자바의 선택 정렬은 리스트에서 가장 작은 값을 찾아 리스트의 맨 앞으로 이동시키는 알고리즘입니다. 이 과정을 반복하면 리스트의 모든 요소가 정렬되며, 최종적으로 정렬된 리스트가 반환됩니다.

자바에서 리스트를 정렬하려면 어떻게 해야 할까요? 여러 가지 방법이 있지만, 그중 하나가 바로 선택 정렬(Selection Sort)입니다.

이 글에서는 선택 정렬이 무엇인지, 어떤 원리로 동작하는지 살펴보고, 직접 자바 코드로 구현하는 방법까지 단계별로 안내해 드립니다.

자바 선택 정렬이란?

선택 정렬은 리스트에서 최솟값을 반복적으로 찾아, 아직 정렬되지 않은 요소들의 맨 앞으로 이동시키는 알고리즘입니다. 이 과정을 리스트의 모든 요소에 대해 반복하면 전체 리스트가 정렬됩니다.

처음에는 리스트의 첫 번째 요소를 '최솟값'으로 간주합니다. 그다음 이 값과 다음 요소를 비교하는데, 다음 요소가 더 작으면 두 요소를 교체합니다. 이런 식으로 마지막 요소에 도달할 때까지 최솟값을 찾고, 찾은 최솟값을 리스트의 시작 위치로 옮깁니다.

선택 정렬에서 리스트는 두 부분으로 나뉩니다. 하나는 이미 정렬된 부분(sorted subarray), 다른 하나는 아직 정렬되지 않은 부분(unsorted subarray)입니다. 정렬이 진행될수록 요소들이 정렬되지 않은 영역에서 정렬된 영역으로 하나씩 옮겨갑니다.

선택 정렬은 오름차순과 내림차순 어느 쪽으로도 정렬할 수 있습니다.

선택 정렬은 언제 사용해야 할까?

선택 정렬은 작은 크기의 리스트를 정렬할 때 적합합니다. 대용량 데이터를 정렬할 때는 더 효율적인 알고리즘이 많기 때문입니다. 병합 정렬(merge sort), 삽입 정렬(insertion sort), 퀵 정렬(quick sort) 같은 알고리즘이 자바 프로그래밍에서 선택 정렬보다 뛰어난 성능을 보여줍니다.

반면, 배열의 모든 요소를 반드시 확인해야 하는 상황이라면 선택 정렬이 좋은 성능을 발휘합니다. 예를 들어 리스트의 요소가 거의 또는 전혀 정렬되어 있지 않은 경우가 여기에 해당합니다. 참고로 선택 정렬은 개념 이해가 더 쉬운 버블 정렬(bubble sort)보다 일반적으로 나은 성능을 보입니다.

선택 정렬의 동작 원리

알고리즘을 구현하기 전에, 먼저 우리가 만들려는 알고리즘이 무엇을 해야 하는지 정확히 이해하는 것이 중요합니다. 선택 정렬이 리스트를 정렬하는 과정을 단계별로 살펴보겠습니다.

다음과 같이 정렬되지 않은 배열이 있다고 가정해 보겠습니다.

선택 정렬은 첫 번째 요소를 리스트의 최솟값으로 설정합니다. 이 값은 임시값으로, 비교가 진행될 때마다 변경될 수 있으며 별도의 변수에 저장됩니다.

이제 'minimum' 값을 두 번째 요소와 비교합니다. 두 번째 요소는 아직 정렬되지 않은 영역에 속합니다. 정렬된 요소들 뒤에 있는 모든 요소는 정렬되지 않은 상태입니다.

두 번째 요소가 'minimum'보다 작다면, minimum 값을 해당 요소의 값으로 업데이트합니다. 14는 17보다 작으므로 새로운 최솟값은 14가 됩니다.

이 과정을 리스트의 나머지 요소에 대해서도 반복합니다. 9는 14보다 작으므로 minimum 값은 9로 바뀝니다. 하지만 9는 12보다 작지 않으므로 minimum 값은 그대로 유지됩니다.

한 번의 순회(iteration)가 끝나면 9가 가장 작은 수임을 확인하게 됩니다. 이 값을 리스트의 맨 앞으로 이동시킵니다.

이제 정렬되지 않은 첫 번째 요소부터 다시 과정을 시작합니다. 다음 비교는 17부터 진행됩니다.

• 17은 현재 최솟값과 같습니다.
• 프로그램이 17과 14를 비교하면, minimum 값은 14로 변경됩니다.
• 프로그램이 14와 12를 비교하면, minimum 값은 12로 변경됩니다.
• 프로그램이 12를 정렬된 요소들의 끝으로 이동시킵니다.

이 시점에서 리스트는 다음과 같습니다.

이 과정을 리스트가 완전히 정렬될 때까지 반복합니다. 알고리즘 실행이 끝나면 다음과 같은 결과가 반환됩니다.

리스트가 오름차순으로 정렬되었습니다.

자바로 선택 정렬 구현하기

선택 정렬의 동작 원리를 아는 것과 실제로 구현하는 것은 별개의 문제입니다. 앞서 살펴본 로직을 그대로 활용해 자바 코드로 선택 정렬을 작성해 보겠습니다.

1단계: 프로그램 기본 설정

먼저 selection_sort.java라는 이름의 파일을 생성하고, 자바 Arrays 라이브러리를 임포트합니다.

import java.util.Arrays;

이 라이브러리는 코드 후반부에 사용됩니다. 정렬된 배열을 문자열로 변환해 콘솔에 출력하기 위해 필요합니다.

2단계: 정렬 함수 생성

다음으로 클래스를 선언하고, 선택 정렬을 수행하는 메서드를 만듭니다. selection_sort.java 파일에 아래 코드를 추가하세요.

class SelectionSort {
	void sortNumbers(int array[]) {
		int size = array.length;

		for (int item = 0; item < size - 1; item++) {
			int minimum = item;
			for (int number = minimum + 1; number < size; number++) {
				if (array[number] < array[minimum]) {
					minimum = number;
				}
			}
			
			int temporary = array[item];
			array[item] = array[minimum];
			array[minimum] = temporary;
		}
	}
}

클래스 내부에는 정렬을 수행하는 sortNumbers 메서드를 정의했습니다. 먼저 배열의 길이를 계산해 변수에 저장합니다.

그다음 for 루프를 생성해 리스트의 모든 요소를 순회합니다. 이 루프 내부에서는 현재 위치의 요소를 최솟값 후보로 설정합니다.

이어서 또 다른 for 루프를 시작해 최솟값 후보를 리스트의 나머지 모든 요소와 비교합니다.

루프가 읽어 들인 숫자가 현재 최솟값보다 작으면, minimum 값을 해당 숫자로 업데이트합니다. 여기서 'number'는 최솟값과 비교 대상이 되는 숫자의 인덱스를 의미합니다.

최솟값이 리스트의 모든 숫자와 비교를 마치면 내부 for 루프가 종료됩니다. 그런 다음 최솟값을 정렬된 숫자들 바로 뒤로 이동시킵니다.

3단계: 정렬 함수 호출

아직 코드만 작성했을 뿐 실제로 실행되지는 않았습니다. 클래스를 호출하고 정렬할 리스트를 전달해야 합니다.

sortNumbers 메서드 아래에 다음 코드를 추가하세요.

public static void main(String args[]) {
	int[] toSort = { 17, 14, 9, 12 };
	SelectionSort newSort = new SelectionSort();
	newSort.sortNumbers(toSort);
	
	System.out.println(Arrays.toString(toSort));
}

main 메서드 안에서 정렬할 리스트를 담은 toSort 배열을 선언했습니다. 그다음 SelectionSort 클래스의 인스턴스인 newSort를 생성하고, 이를 통해 sortNumbers 메서드를 호출해 toSort 배열의 값을 정렬합니다.

sortNumbers 메서드 실행이 끝나면, Arrays.toString() 메서드를 사용해 정렬된 배열을 콘솔에 출력합니다. 이 메서드는 배열을 문자열 목록으로 변환해 줍니다.

코드를 실행해 보겠습니다.

[9, 12, 14, 17]

리스트가 성공적으로 정렬되었습니다!

내림차순으로 정렬하는 방법

선택 정렬은 내림차순 정렬에도 활용할 수 있습니다. sortNumbers 메서드의 다음 코드를

if (array[number] < array[minimum]) {

아래 코드로 바꾸기만 하면 됩니다.

if (array[number] > array[minimum]) {

이렇게 수정하면 'minimum' 값이 for 루프가 접근한 값보다 큰지 검사하게 됩니다. 즉, minimum 변수가 리스트에서 가장 작은 값이 아니라 가장 큰 값을 가리키게 됩니다.

혼란을 피하려면 내림차순 정렬 시에는 변수명을 'minimum'에서 'maximum'으로 변경하는 것이 좋습니다.

축하합니다! 이제 선택 정렬 알고리즘을 사용해 자바에서 리스트를 정렬할 수 있게 되었습니다.

자바 선택 정렬의 시간 복잡도

알고리즘을 평가할 때는 세 가지 시간 복잡도를 고려해야 합니다. 최선의 경우(best case), 최악의 경우(worst case), 평균적인 경우(average case)입니다.

선택 정렬의 최선, 평균, 최악의 경우 복잡도는 모두 O(n²)입니다. 이는 리스트의 요소 수가 늘어날수록 알고리즘 실행 시간이 기하급수적으로 늘어난다는 의미입니다.

알고리즘 복잡도가 헷갈린다면 빅오 표기법(Big O Notation) 관련 학습 자료를 참고해 보세요. 빅오 표기법은 알고리즘의 복잡도를 설명하는 데 사용되는 표기법입니다.

마무리

선택 정렬은 데이터 리스트를 정렬하는 효율적인 방법 중 하나입니다. 정렬되지 않은 리스트에서 가장 작은 요소를 선택해 리스트의 맨 앞으로 이동시키는 방식으로 동작하며, 이 과정을 리스트가 완전히 정렬될 때까지 반복합니다.

자바 개발자가 되고 싶으신가요? 자바 학습 가이드를 확인해 보세요. 효과적인 학습 팁과 함께 추천 온라인 강좌 및 학습 리소스 정보를 만나볼 수 있습니다.