[JAVA] 선택 정렬(Selection Sort)

선택 정렬은 이해하기 쉽지만 빠른 알고리즘은 아니다.

먼저 전체 배열에서 가장 작은 요소를 찾고 그 요소를 배열의 첫 번째 요소와 교환한다.
다음으로 배열 A의 두 번째 요소부터 마지막 요소까지 확인하여 가장 작은 요소를 찾은 후 그 요소를 두 번째 요소와 교환한다.
이 과정을 배열 전체가 정렬될 때까지 (n - 1)번 반복한다.

 

시간복잡도 O(N^2)

 

알고리즘

SelectionSort(A[0 .. n-1])

for (i = 0; i < n - 1; i++) {
    // 배열의 가장 작은 요소 찾기
    min = i
    for (j = i; j < n; j++)
        if (A[j] < A[min]) min = j
        
    A[i]와 A[min] 교환
}

 

JAVA

public class SelectionSort {
	public static void main(String[] args) {
		int[] intArray = {89, 45, 67, 92, 39, 74, 26, 90};
		int i;
		
		System.out.print("정렬 전 배열: ");
		
		for (i = 0; i < intArray.length; i++) {
			System.out.print(intArray[i] + " ");
		}
		
		selectionSort(intArray);
		
		System.out.print("\n정렬 후 배열: ");
		
		for (i = 0; i < intArray.length; i++) {
			System.out.print(intArray[i] + " ");
		}
	}
	
	public static void selectionSort(int[] A) {
		int i, j, min, temp;
		int n = A.length;
		
		for (i = 0; i < n - 1; i++) {
			min = i;
			for (j = i; j < n; j++) {
				if (A[j] < A[min]) min = j;
			}
			
			temp = A[min];
			A[min] = A[i];
			A[i] = temp;
		}
	}
}