[알고리즘/C++] - 정렬 모음

프로그래밍의 세계에서는 여러 개의 데이터들을 순차적으로 정렬하는 다양한 방법을 제공합니다.

1,2,3,4,5 처럼 숫자를 오름차순으로 정렬하는 것부터

가,나,다처럼 이름순으로 정렬하기도 하고,

5,4,3,2,1과 같이 숫자를 내림차순으로 거꾸로 정렬하기도 합니다.

프로그래밍에서는 이렇게 데이터를 적절히 정렬해두는 것이 중요합니다. 그래야만 해당 데이터가 필요한 순간에 손쉽게 그 데이터를 탐색하고 접근할 수 있기 때문입니다.

 

오늘은 알고리즘에서 소개되는 몇가지 정렬 방법들을 알아보도록 하겠습니다.

---

 버블 정렬(Bubble Sort)

 

• 시간복잡도: O(n²)
• 인접한 두 원소를 비교하여 교환하는 방식으로 정렬하며, 가장 큰 원소가 뒤로 이동합니다.
• 코드가 간단하여 구현이 쉬운 반면, 시간복잡도 면에서 효율이 떨어지기에 큰 데이터들을 정렬하는 작업에 사용되지 않습니다.

for (int a = 0; a < numbers.size(); a++) { //모든 원소에 대해진행
    bool check = false;
    for (int i = 0; i < numbers.size()-1-a; i++) //끝에서 a번째까지만 -> 다 정렬되었으므로
    {
        if (numbers[i] > numbers[i + 1]) { //양옆비교하고 바꿔야 할 시,
            check = true; //바꾸기로 합니다
            int swap = numbers[i + 1];//바꿉니다
            numbers[i + 1] = numbers[i];
            numbers[i] = swap;
        }
    }
    if (!check) break;//바꿔야하지 않는경우 다음 원소로!
}

 

선택 정렬(Selection Sort)

• 시간복잡도: O(n²)
• 전체 리스트에서 가장 작은 원소를 선택하여 앞부터 차례대로 교환하는 방식으로 정렬합니다
• 구현이 쉽고, 추가적으로 메모리를 사용하지도 않기 때문에 공간적으로 효율적이지만, 버블정렬과 마찬가지로 시간복잡도 면에서의 효율이 떨어집니다.

for (int i = 0; i < numbers.size(); i++)//모든 원소에 대해 진행
{
    int index = i;
    for (int j = i; j < numbers.size(); j++))//본인보다 작은 원소를 찾아 저장
    { 
        if (numbers[index] > numbers[j])
        {
            index = j;
        }
    }
        int swap = numbers[index]; //최종적으로 찾은 가장 작은 원소와 자신을 변경 
        numbers[index] = numbers[i];
        numbers[i] = swap;
}

 

삽입 정렬(Insertion Sort)

 

• 시간복잡도: O(n) ~O(n²)
• 정렬된 부분과 정렬되지 않은 부분으로 나누고, 정렬되지 않은 원소를 적절한 위치에 삽입하여 정렬합니다.
• 만약 데이터가 대부분 정렬된 상태의 경우는 시간복잡도가O(n)까지도 될 수 있는 성능을보이지만, 최악의경우 위 정렬들과 마찬가지의 낮은 시간복잡도 효율을 보입니다.

int j = 0;
for (int i = 0; i < numbers.size(); i++) { //모든 원소를 돌아감
    int num = numbers[i];
    for (int j= i - 1; j >= 0; j--){ //본인보다 앞에잇는 원소들을 찾음
        if (numbers[j] > num) //해당 원소가 본인보다 큰 경우
            numbers[j + 1] = numbers[j];//뒤로보내기
        else 
            break;
    }
    numbers[j] = num; //뒤로 보내고 남은 자리에 본인을 넣음
}

 

퀵 정렬(Quick Sort)

 

• 시간복잡도:  O(n log n) ~ O(n²)
• pivot을 기준으로 작은 원소와 큰 원소를 분할하여 정렬하는 방식으로, 분할 정복 기법을 사용합니다.
• 평균적으로  O(n log n)의 시간복잡도를 사용하기에 효율적이라고 볼 수 있으나 최악의 경우에는 O(n²) 까지도 갈 수 있습니다. 

int partition(std::vector<int>& numbers, int low, int high)
{
    //마지막을 피봇으로 합시다.
    int pivot = numbers[high];

    int i = (low - 1); //시작지점
    //나보다 작은 아이들 왼쪽정렬
    for (int j = low; j <= high - 1; j++)
    {
        if (pivot > numbers[j]) {
            i++;
            std::swap(numbers[j], numbers[i]);
        }
    }
    //작을 수 있게 그 위치로 교환..
    std::swap(numbers[i + 1], numbers[high]);

    return (i + 1);
}

void quickSort(std::vector<int>& numbers, int low, int high)
{
    if (low >= high) return; 
    int pi = partition(numbers, low, high);

    quickSort(numbers, low, pi - 1);
    quickSort(numbers, pi + 1, high);
}

 

병합 정렬(Merge Sort)

• 시간복잡도: O(n log n)
• 리스트를 절반씩 분할하고, 각 부분을 정렬한 후 병합하여 정렬합니다.
• 다른 정렬들과 다르게 일관되고 효율적인 시간복잡도를 사용합니다. 하지만 해당 정렬은 추가적인 메모리 공간이 필요한 데다가 구현 또한 상당히 복잡하다는 단점이 있습니다. 

void MergeSort(std::vector<int>& numbers, int low, int high) //low와 high는 인덱스를 의미
{
    if (low >= high) return; //인덱스가 역전된다면 정렬이 끝난 것을 의미하므로 종료

    int mid = (low + high) / 2;  //중간지점 선정하여 분할
    MergeSort(numbers, low, mid); //처음~중간 재귀
    MergeSort(numbers, mid + 1, high); //중간~끝 재귀

    //Merge !!!
    std::vector<int> temp(numbers.size()); //임시 벡터
    int i = low;  //왼쪽 정렬데이터
    int j = mid + 1;//오른쪽 정렬데이터
    int k = low;//들어갈공간.
    while (i <= mid && j <= high)
    {
        //더 작은 것을 k번째에 넣어주고 k를 1더해주기
        if (numbers[i] < numbers[j])
        {
            temp[k++] = numbers[i++];
        }
        else
        {
            temp[k++] = numbers[j++];
        }
    }
    //둘중 하나의 공간만 다 써버렸다면 이제 남은 하나의 공간은 남은 뒷공간에 채워넣음
    while (i <= mid) 
    {
        temp[k++] = numbers[i++];
    }
    while (j <= high)
    {
        temp[k++] = numbers[j++];
    }
    //임시데이터를 진짜 데이터로 옮겨넣어요
    for (int i = low; i <= high; i++)
    {
        numbers[i] = temp[i];
    }
}

 

계수 정렬(Countion Sort)

• 시간복잡도: O(n + k) (k는 원소의 최대값)
• 각 원소의 빈도를 세어 배열에 저장한 후, 이를 이용하여 정렬된 배열을 구성합니다.
• 원소가 작으면 작을수록 정말 빠른 효율을 보이지만, 데이터가 커질수록 메모리 사용량이 늘며 비효율적일 수 있습니다.

void CountingSort(std::vector<int>& numbers)//ㅠㅠ
{
    int max = *std::max_element(numbers.begin(), numbers.end()); //최댓값 탐색
    int min = *std::min_element(numbers.begin(), numbers.end()); //최솟값 탐색
    int range = max - min + 1; //범위

    std::vector<int> count(range), output(numbers.size()); //두개의 공간(카운트, 결과)

    for (int i = 0; i < numbers.size(); i++) 
    {
        count[numbers[i] - min]++;
    }
    for (int i = 1; i < count.size(); i++)  //앞에꺼하나씩 더해주면서 인덱스별 카운팅.
    {
        count[i] += count[i - 1];
        std::cout << count[i];
    }
    for (int i = numbers.size() - 1; i >= 0; i--) //..
    {
        output[count[numbers[i] - min] - 1] = numbers[i];
        count[numbers[i] - min]--;
    }
    for (int i = 0; i < numbers.size(); i++) //최종 결괏값 넣어주기
    {
        numbers[i] = output[i];
    }
}

+힙 정렬, 등의 더 다양한 정렬방법이 있지만 우선 생략합니다.

 

이렇게 정렬을 살펴보았습니다.

정렬을 보면 아시겠지만, 각각 정렬이 빠르기만하다고 항상 유용한 것이 아니기에 상황에 따라 알맞은 정렬 방법을 사용해야합니다.

알고리즘에 대한 대체적인 흐름은 매 정렬마다 제공한 코드 및 주석으로 대체합니다.

---

 

추가 지식) 정렬을 분류해보자

기준 1: 안정성

버블 선택 삽입 퀵 병합 계수

안정성을 기준으로 분류합니다. 안정성은 중복된 값을 정렬할 때, 입력 순서와 동일하게 유지될 수 있는 정렬인가를 기준으로 판단됩니다. 

안정 정렬(stable Sort): 삽입, 병합, 버블, 계수정렬

불안정 정렬(unstable Sort): 선택, 퀵

기준 2: 정렬의 장소

정렬이 어디에서 이루어지는 지에 따라서 정렬을 내부정렬과 외부정렬로 나눌 수도 있습니다.

내부 정렬(internal Sort): 버블, 선택, 삽입, 퀵, 계수

외부 정렬(external Sort): 병합

병합정렬의 경우, 외부로 분류되긴 하지만, 사실 매우 큰 데이터 세트의 경우 외부정렬로 사용되며, 작은 데이터인 경우에는 다른 정렬들과 마찬가지로 내부 정렬을 수행합니다.

 

 

---

 

지금까지 정렬에 대해서 알아보았습니다..

이전까지도 정렬에 대해서는 간단하게 배웠기 때문에 알고 있다고 생각했었는데 다 까먹어버려서 다시 한 번 기록을 해두면 조금이라도 기억에 많이 남고 두고두고 볼 수 있지 않을까 싶어서 글을 좀 열심히 써보았습니다..

도움이 되었길 바랍니다.. 

그럼 20000

---

반응형

참고자료

https://bugoverdose.github.io/computer-science/sorting-basics/

[알고리즘] 정렬의 분류, 삽입 정렬, 선택 정렬, 버블 정렬