[Algorithm] 선택 정렬(Selection Sort) 이란?

 

📖 선택 정렬(Selection Sort)이란?

선택 정렬(Selection Sort)은 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 그 위치에 어떠한 원소를 넣을지 선택하는 알고리즘입니다.

 

 

🔎 선택 정렬의 특징

• 시간 복잡도는 n²
• 자료 이동 횟수가 미리 정해져있다
• 값이 같은 레코드가 있을 경우 상대적인 위치가 변경될 수 있고 이러한 이유로 안정성을 만족하지 않는다.

 

 

📕 알고리즘

https://github.com/GimunLee

1. 주어진 리스트 중에서 최소값을 찾는다.
2. 그 최솟값을 맨 앞 값과 교체한다.
3. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.

 

👨🏻‍💻 JAVA로 구현

import java.util.*;
public class Main {
	
	public static void selection_sort(int a[]) {
		int size = a.length;
		
		for (int i = 0; i < size; i++) {
			int idx = i;
			for (int j = i; j < size; j++) {
				if(a[idx] > a[j]) idx = j;
			}
			int tmp = a[idx];
			a[idx] = a[i];
			a[i] = tmp;
		}
	}
	
	public static void main(String[] args){
		
		Scanner sc = new Scanner(System.in);
		
		int arr[] = {9,1,6,8,4,3,2,0};
		
		System.out.println("정렬 전");
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] +" ");
		}
		System.out.println();
		
		selection_sort(arr);
		
		System.out.println("정렬 후");
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] +" ");
		}
	}
}

 

 

 

 

📚 참고

https://ko.wikipedia.org/wiki/%EC%84%A0%ED%83%9D_%EC%A0%95%EB%A0%AC