정렬, 선택정렬(Selection Sort)

1. 선택 정렬(Selection Sort)

선택 정렬 알고리즘은 정렬되지 않은 배열에서 오름차순으로 정렬한다고 가정하고 배열 중에서 최소값을 반복적으로 탐색하여 시작 부분에 배치함으로써 배열을 정렬하는 알고리즘입니다. 선택 정렬 알고리즘은 정렬 과정에서 주어진 배열에서 2개의 하위 배열을 유지합니다.

• 한 하위 배열은 최소값을 탐색하여 시작 부분에 배치함으로써 정렬된 배열입니다.
• 다른 하위 배열은 정렬되지 않은 남은 요소들이 담긴 배열입니다.

2. 선택 정렬 수행 과정

선택 정렬의 수행 과정을 그림으로 표현하면 아래와 같습니다.

선택 정렬 수행 과정을 정리하면 다음과 같다.

1. 배열의 시작부분 값을 기준으로 최소값을 탐색합니다.
2. 최소값을 찾았다면 시작부분의 위치와 최소값의 위치의 값을 서로 교환합니다.
3. 시작부분을 오른쪽으로 한칸 이동합니다.
4. 1~3번 과정을 반복합니다.

 

3. 선택 정렬 코드 구현

public class SelectionSort {
	public static void sort(int[] arr)
	{
		int n = arr.length;
		for(int i=0; i<n-1; i++)
		{
			int min_val = i;
			for(int j=i+1;j<n;j++)
			{
				if(arr[min_val]>arr[j])
				{
					min_val = j;
				}
			}
			int temp = arr[min_val];
			arr[min_val] = arr[i];
			arr[i] = temp;
		}
	}
}

class SelectionSortTest {

	@Test
	void selectionSortTest() {
		int[] arr = {5,3,2,4,1};
		
		System.out.println(Arrays.toString(arr));
		SelectionSort.sort(arr);
		System.out.println(Arrays.toString(arr));
	}

}

[5, 3, 2, 4, 1]
[1, 2, 3, 4, 5]

 

4. 선택 정렬 시간복잡도(Time Complexity)

• Worst Case : 선택 정렬의 최악의 경우는 배열 안에 요소들이 내림차순으로 정렬되어 있는 경우입니다. 이 경우 (n-1) + (n-2) + ... + 1으로 인하여 O(n²)가 소요됩니다.
• Best Case : 선택 정렬의 최고의 경우는 배열 안에 요소들이 이미 오름차순으로 정렬되어 있는 경우입니다. 하지만 이미 최소값을 찾았다 하더라도 배열의 마지막 요소까지 비교는 계속해야 하기 때문에 O(n²)가 소요됩니다.

 

References

[GeeksForGeeks] Selection Sort