정렬 알고리즘 - 비교기반정렬

정민주·2024년 3월 11일

알고리즘

목록 보기

2/8

⭐1. 선택정렬

a. 기본개념

리스트에서 최소값을 찾는다.
이 값을 현재 위치의 값과 교환한다.
현재 위치를 다음으로 이동하며 반복한다.

b. 성능

<비교연산>
비교연산은 n-1번, n-2번, n-3번 ... 으로 발생하게 된다. 즉 등차수열의 공식을 통해 해당 비교연산의 성능은

<교환연산>
교환연산은 비교연산을 n-1, n-2, n-3번 진행할 때 각각 1번씩만 swap 과정이 이루어진다.
즉 해당 교환연산의 성능은

c. 특징

실행 시간이 입력 데이터의 배치와 무관하다.

: 데이터가 정렬/역순/랜덤 이든 어차피 n-1번까지 for문을 돌고 1번의 swap과정이 일어나기에 입력데이터의 배치가 다르다고 실행시간이 달라지는 것은 아니다.

데이터 이동이 최소화된다.

: swap 과정이 삽입 정렬과는 달리 비교 1 챕터 당 1번만 일어난다.

제자리 정렬

: 합병정렬처럼 부가적인 저장공간이 필요없다는 뜻이다.

d. 구현

public class SelectionSort extends AbstractSort {
    public static void sort(Comparable[] a){
        int N = a.length;
        for(int i = 0; i<N; i++) {
            int min = i;
            for( int j = i+1; j<N; j++ ){
                if(less(a[j],a[min]))
                    min=j;
            }
            swap(a, i, min);
        }
        assert isSorted(a);
    }
}

⭐2. 삽입정렬

a. 기본개념

현재 위치를 i라고 가정 ( 0 < i < n)
i번째 원소를 0부터 i-1까지 정렬된 리스트에 추가
i를 n-1까지 증가하면서 반복

b. 성능

<비교연산>
삽입정렬은 배열의 현재 인덱스에서 이중반복문을 사용해 이전의 모든 인덱스와 비교연산을 진행하게 됨. 그렇기 때문에 최악의 비교연산은 O(N^2) !

그러나 이건 "최악"의 경우이지, 최선의 경우의 수는 O(n)

<교환연산>
교환연산은 비교연산과 마찬가지로, 이중 반복문으로 인해 이전의 모든 인덱스와의 교환이 발생할 수 있음. 즉 역시 최악은 O(N^2)

그러나 최선의 경우 (입력 배열이 이미 정렬이 되어 있는 경우)
-> 교환 자체가 일어나지 않으므로 0 의 성능을 자랑

c. 특징

실행 시간이 입력 데이터의 초기 배치에 따라 결정

: 이미 정렬된 경우(최선)와 역순으로 정렬된 경우(최악)이 각각 O(N^2)과 0O(N) 으로 큰 차이가 남

d. 구현

<동적교과과정 ver.>

public class InsertionSort extends AbstractSort {
    public static void sort(Comparable[] a){
        int i,j;
        for(i=1; i<a.length; i++){
            Comparable next = a[i]; //comparable 인터페이스를 구현하는 객체라면, 뭐든지 받을 수 있음
            for(j=i-1; j>=0 && less(next,a[j]); j--){ //next( a[i] ) < (a[i-1) => 내림차순임
                a[j+1] = a[j]; //a[j+1]은 Comparable next에 값 저장되어 있음.
            }
            a[j+1] = next;
        }
    }
}

<알고리즘 수업 ver.>

public class InsertionSort extends AbstractSort {
    public static void sort(Comparable[] a){
        int N = a.length;
        for(int i=1; i<N; i++){
            for(int j=i; j>0 && less(a[j],a[j-1]); j--){ //less함수가 true면, 현재 내림차순이란 의미
                swap(a, j, j-1);
            }
        }
        assert isSorted(a); //해당 함수가 true가 아니면 exception 발생
    }
}