[Java] 선택 정렬(Selection Sort)

선택 정렬(Selection Sort)

: 선택 정렬은 기준 값의 오른쪽에 위치한 값들 중 최솟값을 찾아, 기준 값과 최솟값을 swap하는 방식의 정렬이다.

 

맨 끝 값은 기준 값으로 잡지 않는다. 즉, 배열의 [0] 값부터 끝에서 두 번째 값까지를 기준 값으로 잡는다.

 

일반적으로 시간복잡도는 O(n²)이다.

 

(강의자료 그림)

 

 

import java.io.*;

public class Main {
	static void SelectionSort(int[] arr, int cur, int last) {
		int smallest = cur;
		
		// 기준 값의 오른쪽 값들 중 최솟값 찾기
		for(int walker=cur+1; walker<=last; walker++) {
			if(arr[walker] < arr[smallest])
				smallest = walker;
		}
		
		// 기준 값과 최솟값 swap
		int temp = arr[cur];
		arr[cur] = arr[smallest];
		arr[smallest] = temp;
		
	}
	
	
	public static void main(String[] args) throws IOException{
		int arr[] = {5,3,7,2,1};
		
		for(int current=0; current<arr.length-1; current++) {
			SelectionSort(arr, current, arr.length-1);	// 기준 값을 한 칸씩 옮겨가며 정렬 수행
		}
		
		for(int i=0; i<arr.length; i++) {
			System.out.print(arr[i]+" ");	// 정렬된 값들 출력
		}
	}
}

 

current는 현재 기준 값을 가리키는데, 기준 값은 첫 번째 값부터 끝에서 두 번째 값까지로 설정한다.

그리고 SelectionSort 메소드에 기준 값을 넘겨주고, 메소드가 실행되면 우선 기준 값을 가장 작은 값으로 설정해둔다.

walker가 기준 값의 오른쪽 값들을 모두 거치면서 그 중 가장 작은 값의 인덱스를 smallest에 저장한다.

for문을 빠져나오면 기준 값과 최솟값을 swap한다.

이 과정을 반복하면서 오름차순으로 정렬한다.