Java - 정렬 알고리즘 - 3 (선택 정렬)

◎선택 정렬

현재 위치에 들어갈 데이터를 찾아 선택하는 방식

일반적으로 전체에서 가장 작은 원소를 선택하거나, 가장 큰 원소를 선택하여 정렬한다.

---

◎선택 정렬의 특징

1. 비교 정렬(comparison sort)

 선택 정렬은 데이터를 비교하면서 찾는다.

 

2. 제자리 정렬(in-place sort)

정렬의 대상이 되는 데이터 외에 추가적인 공간을 필요로 하지 않는다.

 

3. 불안정 정렬(unstable sort)

정렬되지 않은 상태에서 같은 키값을 가진 원소의 순서가 정렬 후에는 유지되지 않는다.

 

---

◎선택 정렬의 동작

선택 정렬의 동작, 출처: https://gmlwjd9405.github.io/2018/05/06/algorithm-selection-sort.html

1. 배열에서 최솟값을 찾는다. (원소 3이 최솟값이다)

2. 1회전에서 찾은 최솟값이므로 idx 0의 원소와 최솟값을 교환한다

3. idx 0의 원소를 제외한 배열에서 최솟값을 찾는다.(원소 5가 최솟값이다)

4. 2회전에서 찾은 최솟값이므로 idx 1의 원소와 최솟값을 교환한다

5. (배열의 길이 -1) 회전까지 위의 과정을 반복한다.

(정렬해야 할 원소가 한 개만 남았다는 것은 정렬된 것과 다름없으므로)

 

출처: https://en.wikipedia.org/wiki/Selection_sort

 

---

◎선택 정렬의 구현

package SortAlgorithm;

import java.util.Arrays;

public class sort {

	//선택 정렬
	private void selectionsort(int[] numarr) {
		
		for(int i = 0; i<numarr.length-1; i++) {
			int min = i;
			for(int j = i+1; j<numarr.length; j++) {
				// 최솟값을 가진 인덱스 찾기
				if(numarr[j]<numarr[min]) {
					min = j;
				}
			}
			//i 번째 값과 최솟값을 교환
			swap(numarr, i,min);
		}
		
		print(numarr, "선택 배열");
	}
	
	// swap
	private void swap(int[] numarr, int i, int j) {
		int temp = numarr[i];
		numarr[i] = numarr[j];
		numarr[j] = temp;
	}

	// 출력
	private void print(int[] numarr, String sortname) {
		System.out.println(sortname + "로 정렬된 배열:" + Arrays.toString(numarr));
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] numarr = { 5, 6, 3, 1, 4, 2 }; // 정렬할 배열
		System.out.println("원래 배열:" + Arrays.toString(numarr));

		sort Sort = new sort();

		Sort.insertionsort(numarr);

	}
}

실행 결과:

원래 배열:[5, 6, 3, 1, 4, 2]
선택 정렬로 정렬된 배열:[1, 2, 3, 4, 5, 6]

---

◎선택 정렬의 시간 복잡도

선택 정렬은 길이가 N인 배열에서 최솟값을 찾기 위해 언제나 배열의 끝가지 탐색하므로, 시간 복잡도 O(N^2)을 가진다.

---

◎선택 정렬의 불안정성

 

선택정렬은 불안정 정렬이므로, 같은 키값을 가진 원소의 순서가 정렬 후에는 유지되지 않는다.

예를 들면, 

성과 키가 저장되어있는 배열 ,[(김,170),(이,170),(박,180),(최,165)]을 키에 대해 선택 정렬하면

 

1회차 반복: [(최,165),(이,170),(박,180),(김,170)]

2회차 반복: [(최,165),(이,170),(박,180),(김,170)]

3회차 반복: [(최,165),(이,170),(김,170),(박,180)]

 

정렬 전 배열에는 키 170인 사람이 김, 이순으로 있었지만, 정렬한 후엔 이, 김 순으로 순서가 바뀌어있다는 걸 볼 수 있다.

 

---

◎Sorting algorithm 시간 복잡도(time complexity) & 평균 정렬 속도(average sorting rate)

Sorting algorithm 시간복잡도(time complexity) & 평균 정렬 속도(average sorting rate) 출처:  https://st-lab.tistory.com/195

 

---

◎정렬 알고리즘 구현-github

github.com/jerry-ryu/java_problemsolving_algorithm/tree/main/sorting_algorithm

jerry-ryu/java_problemsolving_algorithm