[정렬] 선택정렬 (Selection sort)

 

선택정렬(Selection sort)

 

기준점을 선정하고 가장 작은 원소를 선택하여 서로 교환해 나가는 방식의 정렬

데이터의 양이 적을수록 성능이 좋지만 데이터의 양이 많아지게 되면 속도가 느리고 성능이 좋지않다.

---

선택정렬 수행과정

 

배열 { 3, 6, 2, 4, 7, 8} 선택 정렬 과정

1. 기준점 3과 가장 작은 값 2와 자리 교환

2 {3 , 6 , 4, 7 ,8 }

2. 기준점 3과 가장 작은 값 3과 자리 교환(제자리)

2 3 { 6, 4, 7, 8}

3. 기준점 6과 가장 작은 값 4와 자리 교환

2 3 4 {6 , 7, 8}

4. 이러한 과정을 계속 해서 반복하면 오름차순 정렬 완료

2 3 4 6 7 8

작은 값을 선택하기 위해 수행되는 비교횟수는 많지만 swap되는 횟수는 적다.

---

 

• 예제 코드

public class selectionSortTest {
    public static void selectionSort(int arr[], int start) {
        if (start < arr.length - 1) {
            int min_index = start;
            for (int i = start; i < arr.length; i++) {
                if (arr[i] < arr[min_index]) {
                    min_index = i;
                }
            }
            swap(arr, start, min_index);
            selectionSort(arr, start + 1);

        }
    }

    public static void swap(int arr[], int index1, int index2) {
        int temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }

    public static void printArray(int arr[]) {
        for (int data : arr) {
            System.out.print(data + ",");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int arr[] = { 3, 6, 2, 4, 7, 8 };
        printArray(arr);
        selectionSort(arr, 0);
        printArray(arr);
    }
}

결과 : 3, 6, 2, 4 ,7, 8

        2, 3, 4, 6, 7, 8