정렬 알고리즘 정리 (C++)

삽입정렬

시간복잡도 : O(n^2) , 최선의 경우 O(N)의 시간복잡도를 가진다.

선택정렬에 비해 난이도가 조금 높은 편이지만, 일반적으로 더 효율적으로 동작한다.

선택정렬과 버블정렬보다 조금 더 빠르고, 효율적이다.

처리하지 않은 데이터를 하나씩 골라 적절한 위치에 삽입한다. 

#include <bits/stdc++.h>

using namespace std;

int n = 10;
int target[10] = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};

int main(void)
{
    for (int i=1; i<n; i++)
    {
        for (int j=i; j>0; j--)
        {
            if (target[j] > target[j-1])
            {
            	swap(target[j], target[j-1]);
            }
            else
            {
            	break;
            }
        }
    }
    for (int i=0; i<n; i++)
    {
    	cout << target[i] << ' ';
    }
    return 0;
}

 

선택정렬

N번만큼 가장 작은 수를 찾아서 맨 앞으로 보낸다.

시간복잡도 : O(n^2) = (N^2 + N - 2 / 2)

N + (N -1) + (N -2) + ... + 2 

#include <bits/stdc++.h>

using namespace std;

int n = 10;
int target[10] = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};

int main(void)
{
    for (int i=0; i<n; i++)
    {
    	int min_index = i;
        for (int j=i; j<n; j++)
        {
            if (target[min_index] > target[j])
            {
            	min_index = j;
            }
        }
        swap(target[i],target[min_index]);
    }
    for (int i=0; i<n; i++)
    {
    	cout << target[i] << ' ';
    }
    return 0;
}

 

버블정렬

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

선택정렬과 시간복잡도는 같지만 가장 느린 정렬알고리즘이다. 

이유는 계속 왼쪽 숫자와 비교하며 교체하는 작업이 있기 때문이다.

선택정렬은 가장 작은 숫자를 골라서 마지막에 한번만 교체해준다.

#include <stdio.h>

int main(void)
{
    int i, j, temp;
    int target[10] = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};
    for(i=0; i<10;i++)
    {
    	for(j=0; j<9-i; j++)
        {
            if(target[j] > target[j+1])
            {
                temp = target[j];
                target[j] = target[j+1];
                target[j+1] = temp;
            }
        }
    }
    for(i=0; i<10; i++)
    {
    	printf("%d ", target[i]);
    }
    return 0;
}

퀵정렬

시간복잡도 : 평균 -  O(NlogN) , 최악의 경우 O(N^2) --> 이미 정렬이 수행이 되어 있는 경우. (1 2 3 4 5 6 7 8 9 10)

결과적으로 이미 정렬이 되어 있는 경우에는 삽입정렬 알고리즘이 매우 빠르게 풀어 낼 수 있다.

기준 데이터를 설정하고 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법

가장 많이 사용되는 정렬 알고리즘이고, 프로그래밍 언어의 정렬 라이브러리의 근간이 되는 정렬 방법

이진탐색과 비슷한 방법이다.

#include <bits/stdc++.h>

using namespace std;

int n = 10;
int target[10] = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};

void quickSort(int *target, int start, int end)
{
    if (start >= end) return;
    int pivot = start;
    int left = start + 1;
    int right = end;
    while (left <= right)	// 엇갈릴 때 까지 반복
    {
    	// 키 값 보다 큰 값을 만날때까지
        while (left <= end && target[left] <= target[pivot]) left++;
        // 키 값보다 작은 값을 만날때까지
    	while (right > start && target[right] >= target[pivot]) right--;
        // 엇갈린 상태라면 pivot 값과 교체
        if (left < right) swap(target[pivot], target[right]);
        // 엇갈리지 않았다면 큰 값과 작은 값을 교체
    	else swap(target[left], target[right]);
    }
    // 데이터가 엇갈려서 while문을 빠져나온다면 pivot 값을 기준으로 왼쪽과 오른쪽에 대해서 퀵정렬을 수행한다.
    quickSort(target, start, right - 1);
    quickSort(target, right + 1, end);
}

int main(void)
{
    quickSort(target,0,n-1);
    for (int i=0; i<n; i++)
    {
    	cout << target[i] << ' ';
    }
    return 0;
}

pivot은 기준 값이다. pivot은 첫 번째 원소이다.

퀵정렬은 재귀적으로 수행이 된다.

퀵정렬의 경우 위의코드는 오름차순 코드인데, 내림차순으로 바꾸려면 

첫 while문 뒤의 2개의 while문에 있는 조건식의 부등호 방향만 바꿔주면 내림차순 코드가 된다.

 

 

결론 - 일반적으로는

버블정렬 < 선택정렬 < 삽입정렬 < 퀵정렬 순으로 선호된다.

하지만 결과적으로는 데이터의 특성에 따라서 적절한 정렬 알고리즘을 사용하는 것이 중요하다.

예를들어서 이미 정렬 된 데이터의 경우 퀵정렬보다 삽입정렬이 더 빠르게 풀어낼 수 있기 때문이다.