[알고리즘] 자바에서의 선택 정렬

선택 정렬(Selection Sort)

- 다음과 같은 순서를 반복하며 정렬하는 알고리즘 이다.

    1. 주어진 데이터 중, 최소값을 찾는다.(배열 전체를 둘러보며 최소값을 찾는다.)

        * 매 반복을 수행하며 최소값을 찾을 때마다 배열 끝까지 찾아가며 데이터를 비교해봐야 한다.

    2. 해당 최소값을 데이터 맨 앞에 위치한 값과 교체한다.

    3. 맨 앞의 위치(최소값) 을 뺀 나머지 데이터를 동일한 방법으로 반복한다.

자바 코드로 직접 구현해보자.

- SelectionSort.java

public class SelectionSort {
	
	private int[] array;
	
	public SelectionSort(int[] array) {
		this.array = array;
	}
	
	public int[] selectionSort() {
		
		for(int i = 0; i < this.array.length - 1; i++) {
			int lowest = i;
			for(int index = i + 1; index < this.array.length; index++) {
				if(this.array[lowest] > this.array[index]) 
					lowest = index;
			}
			// 최소값을 찾은 이후 기준 인덱스와 위치를 바꿔준다.
			int temp = this.array[lowest];
			this.array[lowest] = this.array[i];
			this.array[i] = temp;
		}
		
		return this.array;
	}
}

 

코드가 제대로 동작하는지 확인하기 위한 main 코드는 다음과 같다.

- SelectionSort_main.java

import java.util.Arrays;
import java.util.Random;

public class SelectionSort_main {
	public static void main(String[] args) {
		int[] array = new int[10];
		
		Random random = new Random();
		
		for(int i = 0; i < array.length; i++) {
			array[i] = random.nextInt(100);
		}
		
		SelectionSort sortArray = new SelectionSort(array);
		int[] resultArray = sortArray.selectionSort();
		
		Arrays.stream(resultArray).forEach(x -> System.out.print(x + " "));
	}
}

 

선택 정렬 알고리즘 분석

- 버블 정렬, 삽입 정렬과 같이 2중첩 반복문을 활용하기 때문에 시간복잡도는 O(n^2) 이다.

    - 실제로 상세하게 계산하면 n * (n - 1) / 2