정렬의 종류 및 구현(C++)

선택 정렬

전체 배열을 순회하며 가장 작은 원소를 앞으로 보내는 방식

#include <iostream>
using namespace std;

int main(){
	int arr[10] = { 3, 5, 1, 2, 7, 6, 9, 8, 4, 10 };

	for(int i=0; i<10; i++){
			int idx = i; //최솟값이 있어야 할 인덱스

			for(int j=i+1; j<10; j++){
				if(arr[idx] > arr[j]) idx = j; //최솟값 탐색
			}
			swap(arr[i], arr[idx]); //최솟값이 있는 인덱스와 값 스왑
	}

}

시간복잡도 : O(n^2)

 

 

 

버블 정렬

인접한 두 원소를 비교해나가며 정렬하는 방식

 

#include <iostream>
using namespace std;

int main(){
	int arr[10] = { 3, 5, 1, 2, 7, 6, 9, 8, 4, 10 };

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

}

 

각 정렬 단계마다 최댓값이 정렬된다.

따라서 모든 값이 정렬되려면 n-1번의 단계가 필요하며 이미 정렬된 오른쪽 끝값은 다시 정렬할 필요가 없다.

 

예를 들어, 위의 배열을 정렬할 때 첫 번째 단계에서는

3 < 5이므로 그대로,

5 < 1이므로 swap

...

4 < 10이므로 그대로 두는 과정을 거쳐

3 5 1 2 7 6 9 8 4 10 → 3 1 2 5 6 7 8 4 9 10가 되어 최댓값 10이 정렬되었다.

 

이제 나머지 단계를 거치면 모든 수가 정렬이 된다.

시간 복잡도 : O(n^2)

 

 

삽입 정렬

앞에서부터 정렬된 부분과 비교하여 자신의 위치를 찾아 삽입하여 정렬하는 방식

#include <iostream>
using namespace std;

int main() {
    int arr[10] = { 3, 5, 1, 2, 7, 6, 9, 8, 4, 10 };

    for(int i=1; i<10; i++){
        int elem = arr[i]; //현재 삽입될 원소
        int j;

        for(j=i-1; j>=0; j--){
            if(arr[j] > elem){
                arr[j+1] = arr[j];
            }
            else break;//원소보다 작은 값이 나오면 더 이상 갈 필요 없음
        }

        arr[j+1] = elem;//해당 위치에 원소 삽입
    }

}

시간 복잡도는 O(n^2)이지만 최선의 경우, 즉 거의 정렬되어 있는 상태일 때는 O(N)의 시간 복잡도를 가진다.

 

병합 정렬

배열을 반씩 쪼개어 정렬하고 다시 병합하는 방식

 

[3, 5, 1, 2, 7, 6, 9, 8, 4, 10]의 원소가 있을 때 모두 분할하여

3 / 5 / 1 / 2 / 7 / 6 / 9 / 8 / 4 / 10으로 나눈 뒤

3과 5를 비교하여 정렬, 1과 2를 비교하여 정렬, .. 4와 10을 비교하여 정렬하면

3 5 / 1 2 / 6 7 / 8 9 / 4 10과 같이 정렬된다.

 

이러한 과정을 거치면 모든 원소를 정렬할 수 있다.

 

분할

void partition(int left, int right){
    int mid;
    if(left < right){
        mid = (left + right) / 2;
        partition(left, mid);
        partition(mid+1, right);
        merge(left, right);
    }
}

 

병합 및 정렬

void merge(int left, int right){
    int mid = (left + right) / 2;
    
    int i = left; //i에는 분할된 왼쪽 배열의 첫 번째 값
    int j = mid + 1; //j에는 분할된 오른쪽 배열의 첫 번째 값
    int k = left;

    while(i <= mid && j <= right){
        if(arr[i] <= arr[j]) result[k++] = arr[j++];
        else result[k++] = arr[i++];
    } //분할되어 있는 양쪽 배열의 최솟값을 비교한다. 더 작은 값을 결과 배열에 넣어준다.

    if(i > mid) {
        while(j <= right) {
            result[k++] = arr[j++];
        }
    }
    else {
        while(i <= mid) {
            result[k++] = arr[i++];
        }
    } //남아 있는 값들 넣어주기

    for(int a = left; a<=right; a++){
        arr[a] = result[a];
    } //정렬된 값 다시 배열에 복사
}

시간 복잡도 : O(n log n)

 

 

퀵 정렬

기준점(Pivot)을 잡아 Pivot보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 나누어가며 재귀를 통하여 정렬하는 방식

 

void quickSort(int low, int high){
    if(low >= high) return;

    int pivot = arr[(low + high) / 2]; //배열의 가운데 값을 pivot으로 설정
    int i = low;
    int j = high;

    while(i <= j) {
        while(arr[i] < pivot) i++; //pivot의 왼쪽에서 pivot보다 큰 값 찾기
        while(arr[j] > pivot) j--; //pivot의 오른쪽에서 pivot보다 작은 값 찾기

        if(i <= j) {
            swap(arr[i], arr[j]);
            i++; j--;
        }
    }

    quickSort(low, j); //pivot의 왼쪽 재귀
    quickSort(i, high); //pivot의 오른쪽 재귀
}

시간 복잡도 : O(n log n)