정렬(Sort) 알고리즘

해당 블로그의 내용은 학교에서 배운 내용을 개인적으로 정리한 내용이므로, 잘못된 부분이 있을 수도 있습니다. 

정렬 알고리즘의 종류

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

선택 정렬 (Selection sort)

• 가장 단순한 정렬 알고리즘 
• 최솟값을 찾아서 배열의 앞쪽으로 이동한다.
• 시간 복잡도
  •  O(n^2)

void selectionSort(){ // 선택 정렬
    for (int i{0}; i < nums;++i){
        int min{i};
        for (int j{i}; j < nums;++j){
            if(arr[j] < arr[min]){
                min = j;
            }
        }
        std::swap(arr[i], arr[min]);
    }
}

버블 정렬 (Bubble sort)

• 두 인접한 원소를 검사하여 정렬
• 큰 수를 뒤쪽으로 이동
• 시간 복잡도
  • O(n^2)

void bubbleSort(){ // 버블 정렬
    for (int i{0}; i < nums;++i){
        for (int j{0}; j < nums - i - 1;++j){
            if(arr[j] > arr[j + 1]){
                std::swap(arr[j], arr[j + 1]);
            }
        }
    }
}

삽입 정렬 (Insertion sort)

• 모든 원소를 앞에서부터 차례로 정렬된 배열 부분과 비교
• 시간 복잡도
  • O(n^2)

void insertionSort(){ // 삽입 정렬
    for (int i{1}; i < nums;++i){
        int tmp{arr[i]};
        for (int j{i - 1}; j >= 0;--j){
            if(tmp < arr[j]){
                arr[j + 1] = arr[j];
                if(j == 0){
                    arr[0] = tmp;
                }
            }else{
                arr[j + 1] = tmp;
                break;
            }
        }
    }
}

합병 정렬 (Merge sort)

• 분할 정복 알고리즘 중 하나
• 원본 배열을 하나의 독립된 요소까지 분할하고 난 후, 그 요소들을 하나하나 합병하면서 배열을 전투
• 시간 복잡도
  • O(n * logN)
• 공간 복잡도
  • 2n <= O(n)

int* mergeSort(size_t begin, size_t end){
    if(begin == end)
        return new int[1]{arr[begin]};
    int *arr1 = mergeSort(begin, begin + (end - begin) / 2);
    int *arr2 = mergeSort(begin + (end - begin) / 2 + 1, end);

    // Combine
    int *merge = new int[end - begin + 1];
    size_t leftSize{(end - begin) / 2 + 1};
    size_t rightSize{(size_t)std::ceil((float)(end - begin) / 2)}; // 원본 배열의 크기가 홀수인 경우 올림(ceil)처리를 해주어야 한다
    size_t left{0};
    size_t right{0};

    for (int i{0}; i < (end - begin + 1);++i){
        if(right >= rightSize || (left < leftSize && arr1[left] < arr2[right])){
            merge[i] = arr1[left++];
        }else{
            merge[i] = arr2[right++]; 
        }
    }
    free(arr1);
    free(arr2);
    return merge;
}

void mergeSort(){ // 합병 정렬
    int *sortArray = mergeSort(0, nums - 1);
    std::swap(arr, sortArray);
    free(sortArray);
}

퀵 정렬 (Quick sort)

• 불안정한 정렬, 비교 정렬
• 합병 정렬과는 다르게, 배열을 비균등하게 분할한다.

void quickSort(size_t start, size_t end){
	// quick sort
}

1. 기준점(pivot)을 기준으로 낮은 값을 왼쪽에, 높은 값을 오른쪽으로 정렬시키고 (오름차순 기준) 분할한다.
   1. 기준점(pivot)을 제외한 나머지를 값들을 탐색하는 반복자 hi 와 lo 를 생성한다.
      pivot = start + 1; // 초깃값은 0
      hi = pivot + 1; // 초깃값은 1
      lo = end;  // 초깃값은 배열의 크기(size - 1)
   2. hi 는 왼쪽에서부터, lo 는 오른쪽에서부터 탐색한다.
   3. hi 는 기준값(arr[ pivot ])보다 큰 값을 찾으면 멈추고,
      lo 는 기준값(arr[ pivot ])보다 작은 값을 찾으면 멈춘다.
   4. hi 의 위치가 lo 위치보다 오른쪽에 있다면(= 크다면), 
      • 기준값(arr[ pivot ])과 작은 값(arr[ lo ])의 값들을 서로 교환한다.
      • 그러면 기준값이 대입된 위치, 즉 lo 위치를 기준으로 왼쪽에는arr[ lo ]보다 작은 값들이,
        오른쪽에는 arr[ lo ]보다 큰 값들이 위치하게 된다. 
      • 이제 lo 기준으로 두 영역이 분할되었다.
      • 두 영역의 시작 주소(size_t start)와 끝 주소(size_t end)를 매개 변수로
        자기 자신 함수(void quickSort())를 재귀적으로 호출한다. 
   5. 그렇지 않다면, 큰 값(arr[ hi ])과 작은 값(arr[ lo ])의 값들을 서로 교환한다. 
   6. 현재 hi 와 lo 위치에서 3번의 과정을 반복해서 진행한다.
2. 분할된 배열에도 위의 방식을 사용하여 계속해서 정렬한다. 

void QuickSort(int start, int end){ // 분할정복 알고리즘
    if(start>=end)
        return;
    int pivot{start};
    int i{start + 1}, j{end};

    while(i <= j){
        while(i <= end && nums[i] <= nums[pivot])
            ++i;
        while(j > start && nums[j] >= nums[pivot])
            --j;
        if(i > j){
            int tmp{nums[j]};
            nums[j] = nums[pivot];
            nums[pivot] = tmp;
        }else{
            int tmp{nums[j]};
            nums[j] = nums[i];
            nums[i] = tmp;
        }
    }
    QuickSort(start, j - 1);
    QuickSort(j + 1, end);
}

• 시간 복잡도
  • O(n * logN)
  • 배열이 비내림차순으로 정렬되어 있고, 오름차순 정렬을 할 때 최악의 경우가 된다

힙 정렬 (Heap sort)

• Heap 이용 

void heapify(size_t curr){ // heapify
    if(curr > nums)
        return;
    size_t left{curr * 2 + 1};
    size_t right{curr * 2 + 2};
    size_t max{curr};
    if(left < nums && arr[left] > arr[max])
        max = left;
    if(right < nums && arr[right] > arr[max])
        max = right;
    if(max!=curr){
        std::swap(arr[curr], arr[max]);
        heapify(max);
    }
}

void heapSort(){ // 힙 정렬 
    // 배열의 트리 높이 구하기
    int height{1};
    while(std::pow(2,height) < nums){
        ++height;
    }
    // build heap
    for (int i{(int)std::pow(2, height - 1) - 2}; i >= 0;--i){
        heapify(i);
    }
    // heap sort
    size_t org = nums;
    while(nums > 0){
        std::swap(arr[0], arr[--nums]);
        heapify(0);
    }
    nums = org;
}