정렬 알고리즘

각 정렬에 대해 이해하기 쉽게 정리해보려고 한다.

 

* 정렬해야할 데이터의 크기는 N이다.

* 시간 복잡도는 알고리즘의 시간 복잡도로 코드의 시간 복잡도가 아니다.

(알고리즘에서 N^2번의 비교를 진행하는 것이 코드 상에서도 N^2번의 비교를 진행하는 것이 아니다. for문만 해도 반복할 조건이 되는지 계속 비교를 수행한다.)

* 공간 복잡도는 알고리즘의 공간 복잡도다.

* 안정도는 같은 값을 가진 두 데이터의 순서가 동일하게 유지되는지 그렇지 않을 수 있는지를 의미한다.

 

● 선택정렬

데이터에서 가장 작은 값을 찾아서 앞으로 보내면서 정렬한다.

배열의 앞에서부터 작은 값 순으로 정렬된다.

 

로직 : 

1. 아직 정렬 안된 데이터에서 가장 작은 값을 찾는다.

2. 가장 작은 값을 정렬된 데이터 마지막에 넣는다.

 

코드 : 

void SelectionSort(int[] data, int n)
{
    // 정렬 안된 i번째 데이터에서
    for (int i = 0; i < n - 1; i++)
    {
        // 현재 인덱스를 최소값으로 설정
        int indexMin = i;
        // 마지막 원소까지
        for (int j = i + 1; j < n; j++)
        {
            // 최소값을 찾으면 인덱스를 저장
            if (data[j] < data[indexMin])
            {
                indexMin = j;
            }
        }
        // 최소값과 현재 인덱스의 값을 바꿈
        int temp = data[indexMin];
        data[indexMin] = data[i];
        data[i] = temp;
        // i번째 인덱스까지 정렬됨
    }
}

 

시간 복잡도 : 최선, 평균, 최악 모두 O(n^2)

공간 복잡도 : O(1)

안정 여부 : 불안정

 

●버블정렬

큰 값을 뒤로 보내면서 정렬한다.

배열의 뒤에서부터 큰 값 순으로 정렬된다.

 

로직 :

1. 현재 값과 다음 값을 비교한다.

2. 큰 값을 뒤로 가도록 서로 바꾼다.

3. 다음 인덱스로 이동한다.

4. 1~3번을 반복해서 정렬 안 된 데이터 중 가장 큰 값을 가장 뒤로 보낸다.

5. 정렬된 데이터를 제외하고 1~4번을 반복한다.

 

코드 : 

void BubbleSort(int[] data, int n)
{
    // 정렬 안 된 i번째 값까지
    for (int i = n - 1; i > 0; i--)
    {
        // 0번부터
        for (int j = 0; j < i; j++)
        {
            // 현재 인덱스와 다음 인덱스를 비교
            if (data[j] > data[j + 1])
            {
                // 큰 값을 뒤로 보냄
                int temp = data[j];
                data[j] = data[j + 1];
                data[j + 1] = temp;
            }
        }
        // 가장 큰 값을 뒤로 보내서 i번째부터 마지막 값까지 정렬됨
    }
}

 

시간 복잡도 : 최선 O(n), 평균 및 최악 O(n^2)

공간 복잡도 : O(1)

안정 여부 : 안정

 

최선의 경우는 이미 정렬이 완료되어 있는 경우로 데이터 배열을 1번 비교했을 때 바뀐 내용이 없어 비교를 멈추는 경우이다. (위의 코드에는 구현되어 있지 않다.)

 

●삽입정렬

현재 값과 이전의 값들을 비교해서 올바른 위치에 삽입한다.

 

로직 : 

1. 시작 인덱스는 1번이다.

2. 현재 값보다 작은 값이 나올때까지 이전 인덱스들을 탐색한다.

3. 현재 값보다 작은 값이 있다면 그 뒤의 인덱스에 현재 값을 삽입한다.

4. 현재 인덱스를 다음 인덱스로 이동한다.

 

코드 : 

void InsertionSort(int[] data, int n)
{
    // 1번 인덱스부터 마지막까지
    for (int i = 1; i < n; i++)
    {
        // 현재 값을 보관
        int current = data[i];
        int j = i;
        // 현재 값이 이전 값보다 작다면 계속 이전으로 이동
        while (--j >= 0 && current < data[j])
        {
            // 삽입할 공간을 만들기 위해 이전 값을 뒤로 한 칸씩 밀어줌
            // *특정 인덱스에 바로 삽입 가능한 데이터라면 밀어줄 필요 없음.
            data[j + 1] = data[j];
        }
        // 현재 값보다 작은 값이 있다면 그 뒤에 현재 값을 삽입
        data[j + 1] = current;
    }
    // 다음 인덱스로 이동
}

 

시간 복잡도 : 최선 O(n), 평균 및 최악 O(n^2)

공간 복잡도 : O(1)

안정 여부 : 안정

 

최선의 경우는 이미 정렬이 되어있는 경우로 이전 값과 한 번씩만 비교하는 경우이다.

 

●합병정렬

데이터를 한 개의 원소를 가진 배열들로 쪼갠 다음 배열을 2개씩 합치면서 정렬한다.

원본 배열과 같은 크기의 작업용 배열이 필요하다.

 

로직 : 

1. 데이터를 한 개의 원소를 가진 배열이 될 때까지 쪼갠다.

2. 배열을 2개 선택한다.

3. 두 개의 배열에서 원소 하나씩을 비교해서 작은 값을 작업용 배열에 담는다.

4. 작은 값을 가져온 배열에서 인덱스를 한 칸 이동하고 다시 3번을 반복한다. 만약 한 쪽의 배열을 전부 끝냈다면 다른 쪽 배열의 남은 값은 비교 없이 그대로 작업용 배열에 담는다.

5. 2 ~ 4번을 모두 합쳐질 때까지 반복한다.

 

코드 : 

void mergeSort(int[] sourceArray, int low, int high, int[] workingArray)
{
    // 한 개의 원소를 가진 배열이라면 돌아감
    if (low >= high) return;

    // 배열을 두 개로 나눔
    int mid = (low + high) / 2;
    // 왼쪽 오른쪽 배열을 다시 쪼갬
    mergeSort(sourceArray, low, mid, workingArray);
    mergeSort(sourceArray, mid + 1, high, workingArray);

    // 왼쪽과 오른쪽 배열을 합침.
    int left = low, right = mid + 1;
    for (int i = low; i <= high; ++i)
    {
        if (right > high) workingArray[i] = sourceArray[left++];
        else if (left > mid) workingArray[i] = sourceArray[right++];
        else if (sourceArray[left] <= sourceArray[right]) workingArray[i] = sourceArray[left++];
        else workingArray[i] = sourceArray[right++];
    }

    // 작업용 배열에 복사
    for (left = low; left <= high; ++left) sourceArray[left] = workingArray[left];
}

 

시간 복잡도 : 최선, 평균, 최악 모두 O(nlogn)

공간 복잡도 : O(n)

안정 여부 : 안정

 

●퀵 정렬

pivot이라는 임의의 원소를 기준으로 작은 값과 큰 값을 몰아넣고 쪼개는 과정을 반복하면서 정렬한다.

 

코드 : 

public void QuickSort(int[] array, int left, int right)
{
    if (left >= right) { return; }

    int temp;
    int pivot = array[(left + right) / 2];
    int i = left, j = right;
    while (i < j)
    {
        while (array[i] < pivot) { i++; }
        while (pivot < array[j]) { j--; }

        if (i < j)
        {
            if (array[i] == array[j]) { break; }

            temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }
    }

    QuickSort(array, left, j - 1);
    QuickSort(array, j + 1, right);
}

 

시간 복잡도 : 평균 O(nlogn), 최악 O(n^2)

공간 복잡도 : 평균 O(logn), 최악 : O(nlogn)

안정 여부 : 안정