Selection Sort (선택 정렬)

선택 정렬은 현재 위치에 들어갈 데이터를 찾아 선택하는 알고리즘이다.

데이터를 ‘비교’하면서 찾기 때문에 ‘비교 정렬’이며 정렬의 대상이 되는 데이터 외에 추가적인 공간이 필요하지 않아 ‘제자리 정렬(in-place sort)’ 이기도 하다.

그리고 ‘불안정 정렬’이다.

💙 정렬 방법

1. 주어진 리스트에서 최솟값을 찾는다.
2. 최솟값을 맨 앞 자리의 값과 교환한다.
3. 맨 앞자리를 제외한 나머지 값들 중 최솟값을 찾아 위와 같은 방법으로 반복한다.

💙 구현

public class Selection_Sort {
    public static void main(String[] args){
        List<Integer> nums = new ArrayList<>();

        for (int i = 1; i<=6 ;i++){
            nums.add(i);
        }

        Collections.shuffle(nums);

        int[] arr = nums.stream().mapToInt(Integer::intValue).toArray();

        selection_sort(arr);

        for (int i : arr){
            System.out.println(i);
        }

    }

    private static void selection_sort(int[] a){
        selecton_sort(a, a.length);
    }

    private static void selecton_sort(int[] a, int size){
        for(int i = 0; i < size; i++){
            int min_index = i;

            // 최솟값 인덱스 찾기
            for (int j = i + 1; j < size; j++){ // i +1 이후
                if (a[j] < a[min_index]){
                    min_index = j;
                }
            }

            swap(a, min_index, i);
        }
    }

    // 배열까지 받아야 바뀐게 배열에 적용
    // 따로 swap() 을 두는 이유는 코드 재사용성 증가, 가독성 향ㅅ아, 디버깅 편리 를 위해서다.
    private static  void  swap(int[] a, int i, int j){
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}

🤍회고

이번 선택 정렬 알고리즘은 지난번에 공부한 계수 정렬에 비해 알고리즘 자체는 쉽게 이해할 수 있었다.
다만 구현 과정에서 for(int i = 0; i < size - 1; i++)와 for(int i = 1; i < size; i++) 사이의 차이를 고민하느라 시간을 더 소요했다.
결론적으로 두 방식 모두 결과에는 큰 차이가 없지만, 일반적으로는 0부터 시작하는 방식을 더 권장한다는 것을 알게 되었다.