자바 선택 정렬: 단계별 예제와 전체 코드

선택 정렬이란?

선택 정렬은 남은 요소 중 가장 작은 것을 반복적으로 선택해 제자리에 놓는 직관적인 비교 기반 알고리즘입니다. 큰 데이터셋에서는 가장 빠르지 않지만, 단순함 덕분에 교육용과 작은 배열에 이상적입니다.

알고리즘 작동 원리

• 배열의 처음부터 시작합니다.
• 정렬되지 않은 부분에서 가장 작은 요소를 찾습니다.
• 현재 위치의 요소와 교환합니다.
• 정렬된 구간과 정렬되지 않은 구간의 경계를 오른쪽으로 한 칸 이동합니다.
• 전체 배열이 정렬될 때까지 반복합니다.

자바 구현

아래는 선택 정렬 알고리즘을 정수 배열에 시연하는 간결한 자바 프로그램입니다. 정렬 전후 배열과 각 패스의 중간 단계를 출력합니다.

package com.guru99;
public class SelectionSortAlgo {
    public static void main(String[] args) {
        int[] myArray = {860, 8, 200, 9};
        System.out.println("------선택 정렬 전------");
        printArray(myArray);
        selection(myArray); // 배열 정렬
        System.out.println("-----선택 정렬 후-----");
        printArray(myArray);
    }

    public static void selection(int[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            System.out.println("정렬 패스 번호 " + (i + 1));
            int index = i;
            for (int j = i + 1; j < array.length; j++) {
                System.out.println("비교 " + array[index] + " 와 " + array[j]);
                if (array[j] < array[index]) {
                    System.out.println(array[index] + " is greater than " + array[j]);
                    index = j;
                }
            }
            int smallerNumber = array[index];
            array[index] = array[i];
            array[i] = smallerNumber;
            System.out.println("요소 교환: 교환 후 새 배열");
            printArray(array);
        }
    }

    private static void printArray(int[] array) {
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + " ");
        }
        System.out.println();
    }
}

샘플 출력

------선택 정렬 전-----
860 8 200 9
정렬 패스 번호 1
비교 860 와 8
860 is greater than 8
비교 8 와 200
비교 8 와 9
요소 교환: 교환 후 새 배열
8 860 200 9
정렬 패스 번호 2
비교 860 와 200
860 is greater than 200
비교 200 와 9
200 is greater than 9
요소 교환: 교환 후 새 배열
8 9 200 860
정렬 패스 번호 3
비교 200 와 860
요소 교환: 교환 후 새 배열
8 9 200 860
-----선택 정렬 후-----
8 9 200 860

성능 참고사항

선택 정렬은 입력에 관계없이 O(n²) 비교를 수행하며 최대 O(1) 추가 메모리를 사용합니다. 결정론적 동작 덕분에 메모리가 제약된 환경에 적합합니다.