[알고리즘] #2 선택 정렬(Selection Sort)

오늘은 저번 버블 정렬에 이어서 선택 정렬(Selection Sort)를 java코드로 구현해 보자

---

선택(Selection) 정렬 이란?
 선택정렬은 버블정렬과 유사한 알고리즘으로, 배열을 순회하면서 가장 작은(또는 큰) 요소를 선택하여 배열의 앞쪽에 차곡차곡 순차적으로 정렬하는 것

버블정렬과 마찬가지로 구현이 간단하지만 효율성이 낮은 정렬알고리즘

 

동작원리

1. 최소값 찾기 : 주어진 배열을 순회하며 가장 작은(또는 큰) 요소를 찾음

2. 교환

: 해당 요소를 배열의 맨 앞 인덱스에 위치한 요소와 교환함 ( 1 라운드 ),

2번에서 정렬이 완료된 첫번째 인덱스는 제외하고 가장 작은(또는 큰) 요소를 찾아 두 번째 인덱스에 위치한 요소와 교환함(2 라운드)

3. 반복 : 이 과정을 전체 배열이 정렬 될 때까지 반복함

자바코드로 선택정렬 구현

import java.util.Arrays;
	//선택정렬
public class Selection_Sort {

	public static void main(String[] args) {
		int[] arr = {3, 5, 6, 1, 4, 2};
		int minIndex,temp;
		System.out.println("정렬 전 : " + Arrays.toString(arr));
		
		for (int i = 0; i < arr.length-1; i++) {
			minIndex = i; // 1.정렬 되지 않은 범위에서 첫 인덱스
			for (int j = i+1; j < arr.length; j++) { // 2.최소값 탐색
				if(arr[minIndex] > arr[j]) {
					minIndex = j;
				}
			}
			// 3.최소값과 현재 위치의 값 교환
			temp = arr[i]; 
			arr[i]= arr[minIndex]; 
			arr[minIndex] = temp;
		}
		System.out.println("정렬 후 : " + Arrays.toString(arr));
	}
}

버블정렬과 동일하게 선택정렬은 2중 for문으로 이루어져 있음

 

1. 현재 정렬 되지 않은 범위의 첫 번째 인덱스 설정

: 현재 정렬 되지 않은 범위의 첫 번째 인덱스를 minIndex로 설정

=> minIndex가 현재 라운드에서 최소값을 찾기 위한 기준점을 나타냄

 

2. 최소값 탐색

: i+1 부터 배열의 끝까지 순회하면서 minIndex보다 작은 값이 있는지 탐색함

 

3.  최소값과 현재 위치의 값 교환

: 현재 위치의 값(arr[i]) 와 minIndex에 있는 값(arr[minIndex])을 교환함

=> minIndex가 가리키는 값이 현재 정렬되지 않은 범위에서 가장 작은 값이므로 이를 현재 위치에 배치하여 정렬을 진행

 

이 과정을 배열의 모든 요소에 대해 반복하여 정렬을 완료함.

 

※  위 코드는 최소값을 찾아서 정렬을 했으므로 작은수가 첫 인덱스부터 차곡차곡 쌓이므로 오름차순으로 정렬이 됨, if문의 부등호 방향을 바꾸어서 최대값을 찾아 정렬을 하게 된다면 내림차순 정렬이 가능함.

출력결과

정렬 전 : [3, 5, 6, 1, 4, 2]

정렬 후 : [1, 2, 3, 4, 5, 6]

 

GIF로 이해하기

선택정렬의 특징

• 단순함 : 버블정렬과 마찬가지로 구현이 간단하고 직관적이다.
• 효율성 : 학습 목적이나 작은크기의 데이터 정렬에는 적합할수 있으나 대규모 데이터에는 비효율적이다.
• 안정성 : 동일한 값에 대해 순서가 보장되지 않아 불안정 정렬(Unstable Sort)이다.
• 시간 복잡도 : 비교 연산이 n * (n-1) / 2 번 이루어져 최악, 최선, 평균 모두 O(n^2)로 동일하다.
• 공간 복잡도 : 주어진 배열 안에서 요소들의 위치를 바꾸어 수행하므로 O(n) 이다.

마치며

오늘은 버블 정렬과 유사하지만 다른 선택정렬에 대해 알아보고 구현해 보았다.

버블정렬과 선택정렬은 시간 복잡도와 공간 복잡도도 같고 비슷해 보이지만 인접한 요소와 비교하여 교환이 빈번히 이루어지는 버블정렬과는 다르게 선택정렬은 전체를 탐색하여 최소값을 찾아 각 회전(Round)마다 최대 한 번의 교환만 이루어 지므로 일반적으로 조금 더 나은 성능을 보일 수 있다고 한다.

알아두면 좋은 지식이니 알고 넘어가면 좋을것 같다.

 

 

[참고자료]

링크1

링크2