정렬 알고리즘 총 정리 +) C# 구현 코드

정렬이란?

데이터를 기준에 맞게 순서대로 배열하는 작업이다.

정렬 알고리즘이 왜 필요한가요?

주요 목적은 탐색 효율성을 높이는 것이다.

안정 정렬

정렬 후 동일한 키 값의 요소 순서가 유지되는 정렬

제자리 정렬

추가적인 메모리를 필요로 하지 않는 정렬

참조 지역성

CPU가 미래에 원하는 데이터를 예측해 캐시 메모리에 담아 놓는데 이때의 예측률을 높이기 위해 사용되는 원리이다. 최근에 참조한 메모리나 그 메모리와 인접한 메모리를 다시 참조할 확률이 높다는 이론을 기반으로 캐시 메모리에 저장해둔다.

---

삽입 정렬

데이터 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여 자신의 위치를 삽입하는 알고리즘이다.

방식

1) 매 순서마다 해당 요소를 앞의 정렬된 배열에서 삽입할 수 있는 위치를 찾아 해당 위치에 넣는다.

2) 해당 위치에 있던 요소부터 뒤의 요소들을 한 칸씩 뒤로 이동시킨다.

장점 : 안정한 정렬, 제자리 정렬, 데이터 수가 적고 이미 정렬이 많이 되어있는 상황에서 유리

단점 : 데이터 수가 많다면 비효율적, 삽입하려면 그 뒤에 있는 데이터들을 전부 밀어야하기 때문에 이동이 많음

시간 복잡도

최선 : O(N) - 이미 모든 데이터가 정렬되어 있는 경우

최악 : O(N^2) 

C# 구현 코드

void InsertionSort(int[] array)
{
    // i=1인 이유는 두번째요소부터 비교 시작
    for (int i = 1; i < array.Length; i++)
    {
        int key = array[i]; // 현재 위치 기준 다음 요소
        int j = i - 1; // 현재 위치
        
        // 정렬된 부분의 요소들을 오른쪽으로 이동
        while (j >= 0 && array[j] > key)
        {
            array[j + 1] = array[j];
            j--;
        }
        
        // 현재 요소를 삽입
        array[j + 1] = key;
    }
}

예시

int[] array = { 4, 3, 1, 2, 5 };

1) i = 1, key = 3

// 초기 array문
array = { 4, 3, 1, 2, 5 }

// while문 결과
// j = 1, 4 > 3
array = { 4, 4, 1, 2, 5 } // array[1] = array[0] 이므로 4

// 현재 요소 삽입
array = { 3, 4, 1, 2, 5 } // j=-1이므로 array[0] = key

2) i = 2, key = 1

// 초기 array문 
array = { 3, 4, 1, 2, 5 } 

// while문 결과
// j = 1, 4 > 1
array = { 3, 4, 4, 2, 5 } // array[2] = array[1]
// j = 0 4 > 1
array = { 3, 3, 4, 2, 5 } // array[1] = array[0]

// 현재 요소 삽입
array = { 1, 3, 4, 2, 5 } // array[0] = key

3) i = 3, key = 2

// 초기 array문 
array = { 1, 3, 4, 2, 5 } 

// while문 결과
// j = 2, 4 > 2
array = { 1, 3, 4, 4, 5 } // array[3] = array[2]
// j = 1 3 > 2
array = { 1, 3, 3, 4, 5 } // array[2] = array[1]
// j = 0 인 경우 조건문에 부합하지 않아서 pass!

// 현재 요소 삽입
array = { 1, 2, 3, 4, 5 } // array[1] = key

4) i = 4 key = 5

// 초기 array문 
array = { 1, 2, 3, 4, 5 } 

// while문 결과
조건문에 부합하지 않아서 다 pass!

// 현재 요소 삽입
array = { 1, 2, 3, 4, 5 }

---

버블 정렬

인접한 두 요소를 비교하여 교환하는 방식으로 정렬하는 알고리즘이다.

방식

1) 첫번째 요소와 두 번째 요소를 비교한다.

2) 다음 인접한 두 요소를 비교하여 큰 값을 뒤로 보낸다.

3) 이 과정을 배열의 크기만큼 반복한다.

장점 : 안정 정렬, 구현이 매우 간단

단점 : 데이터가 많을 수록 매우 비효율적이다.

시간복잡도

최선 : O(N) - 이미 모든 데이터가 정렬되어 있는 경우

최악 : O(N^2)

C# 구현 코드

void BubbleSort(int[] array)
{
    int n = array.Length;
    for (int i = 0; i < n - 1; i++)
    {
        for (int j = 0; j < n - i - 1; j++)
        {
            // 다음 요소가 현재 요소보다 작은 경우 값 교환
            if (array[j] > array[j + 1])
            {
                int temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
    }
}

예시

int[] array = { 4, 3, 1, 2, 5 };

1) i = 0 인 경우 

// j = 0 일때 4 > 3이므로
array = { 3, 4, 1, 2, 5}
// j = 1 일때 4 > 1이므로
array = { 3, 1, 4, 2, 5}
// j = 2 일때 4 > 2 이므로
array = { 3, 1, 2, 4, 5}
// j = 3 일때 4 > 5이므로 끝!

2) i = 1 인 경우

// j = 0일때 3 > 1
array = { 1, 3, 2, 4, 5}
// j = 1일때 3 > 2
array = { 1, 2, 3, 4, 5}
// j = 2일때 3 > 4 이므로 끝!

---

선택 정렬

가장 작은 요소를 찾아서 맨 앞으로 이동시키는 알고리즘이다.

방식

1) 배열 전체에서 가장 작은 요소를 찾아 첫번째 위치로 이동시킨다.

2) 1번의 과정을 반복하여 정렬한다.

장점 : 구현이 매우 간단

단점 : 안정 정렬이 아니다. 데이터가 많을 수록 매우 비효율적이다.

시간복잡도

 O(N^2)

C# 구현 코드

void SelectionSort(int[] array)
{
    int n = array.Length;
    for (int i = 0; i < n - 1; i++)
    {
        int minIndex = i;
        for (int j = i + 1; j < n; j++)
        {
            // 최소 요소 Index 찾기
            if (array[j] < array[minIndex])
            {
                minIndex = j;
            }
        }
        // 찾은 최소 요소로 교환
        int temp = array[minIndex];
        array[minIndex] = array[i];
        array[i] = temp;
    }
}

예시

int[] array = { 4, 3, 1, 2, 5 };

1) i = 0, 첫번째 최솟값 1을 찾아서 교환

// 첫번째 최솟값 찾기 
minIndex = 2 // 해당되는 Index값은 1
array = { 1, 3, 4, 2, 5 }

 

2) i = 1, 두번째 최솟값 2를 찾아서 교환

// 첫번째 최솟값 찾기 
minIndex = 3 // 해당되는 Index값은 2
array = { 1, 2, 4, 3, 5 }

3) i = 2, 세번째 최솟값 3를 찾아서 교환

// 첫번째 최솟값 찾기 
minIndex = 3 // 해당되는 Index값은 3
array = { 1, 2, 3, 4, 5 }

 

---

퀵 정렬

임의의 숫자(pivot)을 기준으로 좌측에는 작은 값을 우측에는 큰 값을 두며 정렬하는 알고리즘이다.

방식

1) 배열에서 Pivot을 정한다.

2) Pivot보다 작은 값은 좌측, 큰 값은 우측으로 분할한다.

3) Pivot을 기준으로 양쪽으로 분할된 배열들을 1~2과정을 반복한다.

4) 분할할 수 없으면 정렬이 완료된다.

장점 : 참조 지역성이 높다.

단점 : 불안정 정렬이다.

시간 복잡도

최선/평균 : O(NlogN)

최악 : O(N^2) - 정렬된 상태에서 왼쪽을 피벗으로 잡는 경우 트리의 높이가 N이 된다.

C# 구현 코드

void QuickSort(int[] array, int low, int high)
{
    if (low < high)
    {
        int pivotIndex = Partition(array, low, high);
        QuickSort(array, low, pivotIndex - 1);
        QuickSort(array, pivotIndex + 1, high);
    }
}

int Partition(int[] array, int low, int high)
{
    // 피벗 선택
    int pivot = array[high];
    int left = low-1;
    for (int right = low; right < high; right++)
    {
        // 피벗 보다 작은 요소들 찾아서 swap 한다
        if (array[right] < pivot)
        {
            left++;
            swap(array, left, right);
        }
    }
    // 피벗 요소의 left+1 위치의 요소를 교환
    swap(array, left+1, high);

    // 반복문을 마친 배열에서 left+1 의 값이 피벗의 인덱스가 된다.
    return left+1; 
}

예시

int[] array = {5, 2, 1, 4, 3};

먼저 파티션 결과를 확인해보면 left는 pivot보다 작은 요소들의 갯수를 알려주는 역할을 한다는 것을 알 수 있다.

가장 오른쪽에 있었던 3을 기준으로 왼쪽과 오른쪽 숫자들이 정렬이 되어있는지 모르지만 적어도 3을 기준으로 왼쪽에 있는 숫자들은 작고 오른쪽에 있는 숫자들은 큰 것을 알 수 있다. 그러므로 3의 위치는 확정이 된다!

 

 

 

결과

Partition함수가 한 번 호출될때마다 하나의 요소의 위치가 확정된다.

---

병합 정렬

하나의 리스트를 두 개의 크기의 부분 리스트로 분할해 정렬한 다음 정렬된 부분 리스트를 병합해 정렬하는 알고리즘이다.

방식

1) 배열이 더 이상 쪼개지지 않을 때(요소가 하나일 때)까지 반으로 분할한다.

2) 분할된 부분 배열들을 분할한 순서에 맞게 병합한다. 이 과정에서 정렬이 이루어진다.

3) 최종적으로 병합이 완료되면 배열이 정렬되어 있다.

장점 : 안정한 알고리즘, 성능이 데이터 분포에 영향을 덜 받는다.

단점 : 추가적인 메모리가 필요하다.(배열의 경우)

시간 복잡도

O(NlogN)

C# 구현 코드

void MergeSort(int[] array, int left, int right)
{
    if (left < right)
    {
        int middle = (left + right) / 2;
        
        MergeSort(array, left, middle); // 왼쪽으로 분할
        MergeSort(array, middle + 1, right); // 오른쪽으로 분할
        
        Merge(array, left, middle, right);
    }
}

void Merge(int[] array, int left, int middle, int right)
{
    // 왼쪽 배열과 오른쪽 배열의 시작 인덱스
    int i = left;
    int j = middle + 1;

    // 임시 배열 생성 및 데이터 복사
    int[] tempArray = new int[right - left + 1];
    int k = 0; // tempArray인덱스

    // 두 부분 배열을 병합
    while (i <= middle && j <= right)
    {
        // array[i]와 array[j]를 비교하여 더 작은 값을 tempArray에 복사
        if (array[i] <= array[j])
            tempArray[k++] = array[i++];
        else
            tempArray[k++] = array[j++];
    }

    // 남은 왼쪽 배열의 요소들을 복사
    while (i <= middle)
        tempArray[k++] = array[i++];

    // 남은 오른쪽 배열의 요소들을 복사
    while (j <= right)
        tempArray[k++] = array[j++];

    // 원본 배열에 정렬된 결과 복사
    for (int l = 0; l < tempArray.Length; l++)
        array[left + l] = tempArray[l];
}

예시

int[] array = { 4, 3, 1, 2, 5 };

1) 분할

2) 정복

전체 과정

1) MergeSort(array, 0,4)

2) MergeSort(array,0,2) 

3) MergeSort(array,0,1) 

4) MergeSort(array,0,0) → 단일 요소이므로 if문에서 탈출!

5) MergeSort(array,1,1) → 단일 요소이므로 if문에서 탈출!

6) Merge(array,0,0,1) 진행 → [3,4]

7) MergeSort(array,2,2) → 단일 요소이므로 if문에서 탈출!

8) Merge(array,0,1,2) 진행 → [1,3,4]

9) MergeSort(array,3,4)

10) MergeSort(array,3,3) → 단일 요소이므로 if문에서 탈출!

11) MergeSort(array,4,4) → 단일 요소이므로 if문에서 탈출!

12) Merge(array,3,3,4) → [2,5]

13) Merge(array,0,2,4) → [1,2,3,45]

---

힙정렬

힙 자료구조를 이용하여 정렬하는 알고리즘이다. 루트 노드를 가장 마지막 노드와 교환한 후 힙 크기를 줄이는 방식으로 정렬을 수행한다.

방식

1) 주어진 배열을 힙 구조로 변환한다.

2) 힙에서 최대값or최소값을 꺼내서 정렬된 부분에 넣는다.

3) 힙을 재구성하고 위 과정을 반복한다.

장점 : 제자리 정렬

단점 : 불안정 정렬

시간복잡도 

모든 경우 : O(NlogN)

void Swap(int[] array, int i, int j)
{
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}

void HeapSort(int[] array)
{
    int n = array.Length;

    // 힙을 빌드
    // 왜 i를 반으로 나눌까? 부모 노드만 확인하면 되기 때문이다.
    for (int i = n / 2 - 1; i >= 0; i--)
    {
        Heapify(array, n, i);
    }

    // 힙 정렬
    for (int i = n - 1; i > 0; i--)
    {
        Swap(array, 0, i); // 최대값(루트)을 배열의 끝으로 보냄
        Heapify(array, i, 0); // 나머지 힙을 다시 힙화
    }
}

void Heapify(int[] array, int n, int i)
{
    int largest = i; // 루트
    int left = 2 * i + 1; // 왼쪽 자식
    int right = 2 * i + 2; // 오른쪽 자식

    // 왼쪽 자식이 루트보다 크면
    if (left < n && array[left] > array[largest])
    {
        largest = left;
    }

    // 오른쪽 자식이 현재 가장 큰 값보다 크면
    if (right < n && array[right] > array[largest])
    {
        largest = right;
    }

    // 가장 큰 값이 루트가 아니면
    if (largest != i)
    {
        Swap(array, i, largest); // 스왑
        Heapify(array, n, largest); // 영향을 받은 하위 트리를 다시 힙화
    }
}