정렬 알고리즘 _ 1. 선택정렬

🧶 정렬 알고리즘

가장 기초 정렬 알고리즘부터 해보자

정렬 알고리즘: 주어진 데이터를 순서대로 나열하는 알고리즘

• 선택 정렬
• 버블 정렬
• 삽입 정렬
• 병합 정렬
• 퀵 정렬
• 힙 정렬

등이 있다.
이번에는 선택 정렬 먼저 해보자.

🎐 선택 정렬

선택 정렬 (Selection Sort): 가장 작은 데이터의 위치를 맨 앞에 있는 데이터의 위치와 바꾸는 알고리즘

• 제자리 정렬 알고리즘 중 하나이다.

진행 과정
1. 정렬되지 않은 데이터 중 최솟값을 찾는다.
2. 그 값과 첫번째 자리에 있는 데이터의 위치를 서로 바꾼다.
3. 위 작업 반복.

🎢 구현

public class SelectionSort {

    public int[] sort(int[] data) {
        for (int i = 0; i < (data.length - 1); i++) {
            int index = i;
            for (int j = i+1; j < data.length; j++) {
                if (data[index] > data[j]) index = j;
            }
            int temp = data[i];
            data[i] = data[index];
            data[index] = temp;
        }
        return data;
    }

}

테스트 코드

class SelectionSortTest {

    @Test
    void selection_sort_test() {
        int[] answer = {1, 2, 3, 4, 5, 6, 7, 8, 9};
        int[] arr1 = {4, 1, 7, 9, 2, 5, 6, 3, 8};
        int[] arr2 = {2, 1, 8, 9, 4, 3, 6, 5, 7};

        SelectionSort selectionSort = new SelectionSort();
        assertArrayEquals(answer, selectionSort.sort(arr1));
        assertArrayEquals(answer, selectionSort.sort(arr2));

        int[] arr3 = new int[100];
        Random random = new Random();
        for (int i = 0; i < 100; i++) {
            arr3[i] = random.nextInt(1000);
        }
        final int[] answer3 = Arrays.copyOf(arr3, arr3.length);
        Arrays.sort(answer3);
        assertNotEquals(Arrays.toString(answer3), Arrays.toString(arr3));// 정렬전에는 다르고
        assertArrayEquals(answer3, selectionSort.sort(arr3));//정렬후에는 같아야 함
    }
}

테스트 결과

정리

• 장점
  - 구현이 쉽다
  - 비교 횟수는 많지만, 교환은 적게 일어나므로 많은 교환이 일어나는 경우 효율적이다.
  - 배열 외에 추가 메모리 공간을 필요로 하지 않는다.
• 단점
  - 시간 복잡도가 O(n^2) 이다.
  • 불안정(Unstable Sort) 정렬이다
    • 같은 값이 있는 경우 위치가 변경 될 수 있다.