Selection / Bubble / Insertion Sort (Easy)

출처(위키피디아/GeeksforGeeks)

1. Selection Sort(선택 정렬)

- 주어진 리스중에 최소값을 찾는다.

- 그 값은 맨 앞에 위치한 값과 교체한다.

- 맨 처음을 제외한 나머지 리스트를 같은 방법으로 교체한다.

- Unstable / In-place

최악 시간복잡도	Θ( n ^2 )
최선 시간복잡도	Θ( n ^2 )
평균 시간복잡도	Θ( n ^2 )
공간 복잡도	Θ( 1 )

void selectionSort(int arr[], int n){
    int i, j, indexMin, temp;

    for(i=0; i<n-1; i++){
        indexMin = i;
        for(j=i+1; j<n; j++){
            if(arr[indexMin] > arr[j])
                indexMin = j;
        }
        swap(&arr[i], &arr[indexMin]);  
    }
}

2. Bubble Sort(거품 정렬)

- 두 인접한 원소를 비교하는 정렬하는 방법이다.

- 느리지만 매우 구현이 단순하다.

- 양방향으로 번갈아 수행하면 칵테일 정렬이 된다.

- Stable / In-place

최악 시간복잡도	Θ( n ^2 )
최선 시간복잡도	Θ( n )
평균 시간복잡도	Θ( n ^2 )
공간 복잡도	Θ( 1 )

void bubbleSort(int arr[], int n){
    int i, j, temp;

    for(i=0; i<n-1; i++){
        for(j=0; j<n-i-1; j++){
            if(arr[j] > arr[j+1])
                swap(&arr[j], &arr[j+1]);  
        }
        
    }
}

 

3. Insertion Sort(삽입 정렬) 

- 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다.

- 배열이 길수록 효율이 떨어진다. 다만, 구현이 간단하다는 장점이 있다.

- Stable / In-place

최악 시간복잡도	Θ( n ^2 )
최선 시간복잡도	Θ( n  )
평균 시간복잡도	Θ( n ^2 )
공간 복잡도	Θ( 1 )

void insertionSort(int arr[], int n){
    int i, j, temp;

    for(i=1; i<n; i++){
        temp = arr[i];
        j = i-1;
        
        while(j>=0 && arr[j]>temp){
            arr[j+1] = arr[j];
            arr[j] = temp;
            j = j-1;
        }
    }
}

 

※ Stable ↔ Unstable :

   동일 키 입력에 대하여 상대적 순서가 유지될 경우 Stable로 간주

 

※ In-place(제자리) ↔  Not in place :

   In-place(제자리) 정렬은 정렬되는 항목 외에 Θ(1)개의 메모리만 필요하며 Θ(logN)개의 추가적인 메모리를 인플레이스로 간주