[자료구조](7)[정렬 알고리즘 1]

// 중간에 순서를 바꾸는 경우를 위해 swap 함수를 정의해놨다.

void swap(int[] arr, int i, int j){
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

 

버블 정렬 (bubble sort)

옆에 있는 것과 비교하며 계속 이동
예) 4 3 2 1 를 정렬한다면
    round 1: 3 2 1 4
    round 2: 2 1 3 4
    round 3: 1 2 3 4
-> 정렬 라운드마다 맨 끝의 수가 정렬된다.

void bubble_sort(int[] arr){
    for (int i = 0; i<arr.size()-1; i++){
        for (int j = 0; j<arr.size()-1-i; j++){
            if (arr[j]>arr[j+1])
                swap(arr, j, j+1)
        }
    }
}

2중 중첩 반복문에 각 반복문마다 거의 N씩 돌리므로
최악, 평균, 최선일 때 O(n^2)

 

선택 정렬 (selection sort)

가장 작은 요소를 찾고 정렬
예) 4 3 2 1
    round 1: 1 4 3 2
    round 2: 1 2 4 3
    round 3: 1 2 3 4
-> 정렬 라운드마다 맨 앞의 수가 정렬된다.

void selection_sort(int[] arr){
    for (int i = 0; i<arr.size()-1; i++){
        min_index = i;
        for (int j = 0; j<i+1; j++){
            if (arr[j] < arr[min_index])
                min_index = j;
        }
        swap(arr, j, j+1);
    }
}

2중 중첩 반복문에 각 반복문마다 거의 N씩 돌리므로
최악, 평균, 최선일 때 O(n^2)

 

삽입 정렬 (insertion sort)

왼쪽과 자기 자신을 비교 (구역을 나누고 거기서 정렬)
예) 4 3 2 1
    round 1: 3 4 | 2 1
    round 2: 2 3 4 | 1
    round 3: 1 2 3 4 |

void insertion_sort(int[] arr){
    for (int i = 1; i<arr.size()-1; i++){ //특이하게 1부터 정렬 시작한다.
        int key = arr[i];
        j = i-1 //자신보다 왼쪽에 있는 것 비교하기 위해 구역 쪼개기
        while (i>=0 && arr[j]>key){
            arr[j+1] = arr[j] //1칸씩 밀기
            j = j-1;          // 1칸씩 밀어 정렬된 key 값이 들어오게 할 수 있다.
        }
        arr[j+1] = key;
    }
}

반복문과 그 안에 while문이 있으므로
최악, 평균일 때 O(n^2)
최선일 때 O(n) (거의 정렬되어서 while문을 거의 안 돌림)