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

  선택 정렬(Selection)이란 최소 또는 최대 값을 찾아서 가장 앞 또는 뒤부터 정렬하는 방식입니다. 알고리즘 복잡도는 O(n^2)입니다.

 

정렬되지 않은 데이터

15

11

1

3

8

↓

1

11

15

3

8

↓

1

3

15

11

8

↓

정렬이 끝난 데이터

1

3

8

11

15

 

  선택 정렬 구현 코드(최솟값부터)

pubilc class Main {
	public static void selectionSort(int[] array) {
    	for (int i = 0; i < array.length - 1; i++) {
        	int min = i;
        	for (int j = i + 1; j < array.length; j++) {
            	if (array[j] < array[min]) {
                	min = j;
            	}
            }
            int temp = array[i];
            array[i] = array[min];
            array[min] = temp;
        }
    }
}

  바깥 for문이 array의 길이 - 1만큼 순회합니다.

  min 변수를 생성하고 i를 할당합니다. 안쪽 for문이 i + 1부터 시작해서 array의 길이만큼 순회합니다.

  if문에서 array의 j번째 원소가 array의 min(i)번째 원소보다 작다면 min에 j를 할당하여 값을 갱신합니다.

  임시 변수 temp에 array의 i번째 원소를 할당합니다. array의 i번째 원소에 array의 min번째 원소를 할당합니다. array의 min번째 원소에는 array의 i번째 원소를 할당했던 임시 변수 temp를 할당합니다.

 

  선택 정렬 구현 코드(최댓값부터)

pubilc class Main {
	public static void selectionSort(int[] array) {
    	for (int i = array.length - 1; i > 0; i--) {
        	int max = i;
        	for (int j = i - 1; j >= 0; j--) {
            	if (array[j] > array[max]) {
                	max = j;
            	}
            }
            int temp = array[i];
            array[i] = array[max];
            array[max] = temp;
        }
    }
}

  위 코드의 전개가 유사하되, 최솟값이 아닌 최댓값을 기준으로 원소의 위치가 변경됩니다.

 

  예제 출처: 컴퓨터 개론(자세한 설명이 필요하다면 아래 주소로)

  https://terms.naver.com/entry.naver?docId=2270435&cid=51173&categoryId=51173&expCategoryId=51173