[알고리즘] 정렬

sunny·2022년 10월 4일

알고리즘 개념

목록 보기

1/9

👉 정렬이란, 데이터를 특정한 기준에 따라서 순서대로 나열하는 것

선택 정렬

매번 가장 작은 것을 선택해서, 앞으로 보내는 과정 반복
가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복하면 어떨까?

#include <bits/stdc++.h>

using namespace std;

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

int main() {
    for (int i = 0; i < n; i++)
    {
        int min_index = i; // 가장 작은 원소의 인덱스
        for (int j = i + 1; j < n; j++)
        {
            if(arr[min_index] > arr[j]){
                min_index = j;
            }
        }
        swap(arr[i], arr[min_index]);        
    }
    
    for (int i = 0; i < n; i++)
    {
        cout << arr[i] << ' ';
    }
    return 0;
}

선택 정렬의 시간 복잡도

N-1 번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 하며 매번 가장 작은 수를 찾기 위해서 비교 연산이 필요하다.
👉 $N + (N - 1) + (N - 2) + ⋯ + 2 ≈ N \times (N + 1) / 2$
👉 $O(N^2)$

삽입 정렬

특정한 데이터를 적절한 위치에 삽입한다
데이터를 하니씩 확인하며, 각 데이터를 적절한 위치에 삽입하면 어떨까?

삽입 정렬은 필요할 때만 위치를 바꾸므로 데이터가 거의 정렬 되어 있을 때 훨씬 효율적
삽입 정렬은 특정한 데이터가 적절한 위치에 들어가기 이전에, 그 앞까지의 데이터는 이미 정렬되어 있다고 가정

첫 번째 데이터는 이미 정렬되어 있다고 판단하고, 두 번째 데이터가 어떤 위치로 들어갈지 판단하여 정렬한다.
세 번째 데이터가 어디에 위치해야 1~3 번째 데이터가 정렬될지 판단한 후 정렬한다. (오른쪽에서 왼쪽으로 이동하다가 삽입될 데이터보다 작은 데이터를 만나면 그 위치에서 멈추면 된다.)
총 N - 1 번 반복

#include <bits/stdc++.h>

using namespace std;

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

int main() {
    for (int i = 1; i < n; i++)
    {   
        for (int j = i; j > 0; j--)
        {
            // 한 칸씩 왼쪽으로 이동 (자기 왼쪽 데이터랑 swap)
            if (arr[j] < arr[j - 1]) {
                swap(arr[j], arr[j - 1]);
            }
            // 자기보다 작은 데이터를 만나면 그 위치에서 멈춤
            else break;
        }
        
    }
    
    for (int i = 0; i < n; i++)
    {
        cout << arr[i] << ' ';
    }
    return 0;
}

삽입 정렬의 시간 복잡도

👉 반복문 2번 중첩, $O(N^2)$
👉 최선의 경우 (리스트가 거의 정렬되어 있는 상태), $O(N)$

퀵 정렬

기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸면 어떨까?
퀵 정렬은 기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작한다.
큰 수와 작은 수를 교환할 때, 교환하기 위한 기준 👉 pivot
pivot을 설정한 뒤, 왼쪽에서부터 pivot보다 큰 데이터를 찾고, 오른쪽에서부터 pivot보다 작은 데이터를 찾아 둘의 위치를 교환해준다.

#include <bits/stdc++.h>

using namespace std;

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

void quickSort(int *arr, int start, int end) {
    if (start >= end) return; // 원소가 1개인 경우 종료
    int pivot = start; // 첫 번째 원소를 pivot으로 설정
    int left = start + 1;
    int right = end;
    while (left <= right) {
        // pivot보다 큰 데이터를 찾을 때까지 반복
        while (left <= end && arr[left] <= arr[pivot]) left++;
        // pivot보다 작은 데이터를 찾을 때까지 반복
        while (right > start && arr[right] >= arr[pivot]) right--;
        // 엇갈렸다면 작은 데이터와 pivot을 교체
        if( left > right) swap(arr[pivot], arr[right]);
        // 엇갈리지 않았다면 작은 데이터와 큰 데이터를 교체
        else swap(arr[left], arr[right]);
    }
    // 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행
    quickSort(arr, start, right - 1);
    quickSort(arr, right + 1, end);
}

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

퀵 정렬의 시간 복잡도

👉 $O(NlogN)$

계수 정렬

특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘
데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때만 사용 가능 👉 모든 범위를 담을 수 있는 크기의 리스트(배열)를 선언해야 하기 때문

#include <bits/stdc++.h>
#define MAX_VALUE 9

using namespace std;

int n = 15;
// 모든 원소의 값이 0보다 크거나 같다고 가정
int arr[15] = {7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2};
// 모든 범위를 포함하는 배열 선언(모든 값은 0으로 초기화)
int cnt[MAX_VALUE + 1];

int main() {
    for (int i = 0; i < n; i++)
    {
        cnt[arr[i]] += 1; // 각 데이터에 해당하는 인덱스의 값 증가
    }
    for (int i = 0; i <= MAX_VALUE; i++) // 배열에 기록된 정렬 정보 확인
    {
        for (int j = 0; j < cnt[i]; j++)
        {
            cout << i << ' '; // 띄어쓰기를 기준으로 등장한 횟수만큼 인덱스 출력
        }       
    }
    return 0;
}

계수 정렬의 시간 복잡도

👉 데이터의 개수 N, 데이터 중 최대값의 크기 K 👉 $O(N+K)$

sunny

다음 포스트