[C#] 정렬 알고리즘, 선택 정렬 / 버블 정렬

기술면접 대비하기 #8

 

정렬 알고리즘이란 무엇인가?

정렬 알고리즘이란 원소를 번호순이나 사전순과 같이 일정 순서(오름차순 또는 내림차순 등)대로 열거하는 알고리즘이다. 

자료구조와 원소의 유형에 따라 시간복잡도를 고려해 알고리즘을 선택하는 것이 중요하다.

정렬 알고리즘을 사용하는 이유는 탐색과 관련이 있다. 정렬된 데이터를 갖고 있다면 특정 원소를 추출했을 때 그 원소를 기준으로 어느 부분이 크고 작은지 예상할 수 있다. 이는 탐색에서 자주 쓰는 이진 탐색을 위한 중간다리 역할을 한다. 대표적인 정렬 알고리즘으로는 버블, 선택, 삽입, 힙, 병합, 퀵 정렬 등이 있다.

 

버블 정렬

첫 번째 원소부터 인접한 원소끼리 계속 자리를 교환하면서 맨 끝부터 정렬하는 방식. 

장점 : 구현이 쉽다. 코드가 직관적이다. n개의 원소에 대해 n개의 메모리 사용. 데이터 정밀 비교 가능

단점 : 항상 O(N^2)의 시간복잡도를 가진다. 원소의 개수가 많아지면 성능이 저하된다. 비교 횟수가 많다. 

 

삽입 정렬

자료의 모든 요소를 앞에서부터 차례대로 비교하여 자신의 위치를 찾아 삽입함. 정렬되어 있는 대상에 대해서는 비교연산을 하지 않기 때문에 비교횟수를 줄일 수 있다. 정렬된 값은 교환이 발생하지 않고 N-1의 비교만 일어난다. 

이미 정렬된 자료를 사용할 때 효율적이다. 탐색을 제외한 오버헤드가 적기 때문.

장점 : 최선의 경우 O(N)이라는 빠른 효율성을 가지고 있다. 버블정렬의 비교횟수를 줄이기 위해 등장. 크기가 작은 데이터 집합을 정렬할 때 효율이 좋다.

단점 : 최악의 경우 O(N^2) 라는 시간복잡도를 가진다. 데이터 상태와 크기에 따라 성능 편차가 크다.

 

힙 정렬

최대/최소 힙 트리를 구성해 정렬하는 방법. 완전 이진 트리를 배열에 접목시킨 알고리즘. 최대값/최소값을 구할 때 유용하다. (최대 힙에서 루트는 최대값, 최소 힙에서 루트는 최소값)

장점 : 추가 메모리를 필요로 하지 않음. 항상 O(N * logN)의 시간복잡도를 가진다. O(N * logN)인 정렬 중 가장 효율적이다.

단점 : 실제 시간을 측정하면 퀵 정렬보다 느린 경우가 많다. 데이터 상태에 따라 다른 정렬에 비해 느리다. 안정성 보장이 어렵다. 

* 완전 이진 트리 : 부모 노드 밑에 자식 노드가 최대 2개까지 있으며, 마지막 레벨을 제외한 모든 레벨에 노드가 완전히 채워져 있는 트리 구조.

 

선택 정렬

앞에서부터 차례대로 정렬하는 방법. 주어진 배열에서 최소값을 찾아 맨 앞에 위치한 값과 교체하는 방식.

장점 : 정렬을 위한 비교 횟수는 많지만 교환 횟수가 적어서 교환이 많이 이루어져야 하는 상태에서 효율적이다. 내림차순을 오름차순으로 재정렬할 때 가장 적합하다.

단점 : 정렬을 위한 비교 횟수가 많다. 이미 정렬된 상태에서 소수의 자료가 추가될 때 최악의 처리 속도를 보인다.

 

퀵 정렬

pivot를 정하고, 이보다 작으면 왼쪽, 크면 오른쪽에 위치시킨 뒤 좌우를 다시 각각의 축으로 나누어 축이 1이 될 때까지 정렬한다.

장점 : 기준값(pivot)을 통해 구현하는 방법으로, 기준값 분할 시 logN이라는 시간이 소요되며 전체 시간은 N * logN으로 준수하다.

단점 : 기준값에 따른 시간복잡도의 편차가 크다. (안정성 떨어짐) 최악의 경우 O(N^2)의 시간복잡도를 갖는다.

 

병합 정렬

작은 단위로 잘게 쪼개어 작은 단위부터 정렬해서 정렬된 단위들을 계속 병합하면서 정렬하는 방식. 안정성이 있다. 크기가 큰 자료를 정렬 할 때 효율적이다. 

장점 : 퀵과 비슷하게 원본 배열을 절반씩 분할하면서 정렬한다. 분할 시 logN, 전체적으로 N * logN 의 시간복잡도를 갖는다. 기준값 없이 무조건 절반으로 분할하므로 기준값으로 성능이 달라지지 않으며 항상 O(N * logN)이 된다.

단점 : 임시 배열에 원본을 계속 옮겨주므로 추가 메모리가 필요하다. 데이터가 복잡하다면 퀵보다 병합이 빠르므로 효율적이지만, 추가 메모리를 할당하기 어렵다면 병합 정렬을 사용할 수 없다.

 

 

선택 정렬과 버블 정렬의 차이점은?

선택 정렬은 정렬되지 않은 데이터들의 최소값을 찾아 해당 데이터들의 가장 앞 부분에 위치하도록 하는 정렬 방식이다.

버블 정렬과의 차이점은 모든 원소에서 최소값을 찾아 가장 앞의 위치로 이동시키고 동일한 작업을 반복한다는 것이다.

버블 정렬은 하나의 원소를 나머지와 비교하는 과정을 모든 원소에 적용한다. 따라서 모든 원소를 확인하는 버블 정렬보다 선택 정렬이 더 빠르게 작동한다.

 

선택 정렬은 버블 정렬과 마찬가지로 정확도가 높고 정밀한 비교가 가능하다는 장점이 있지만 오래 걸린다는 단점이 있다. 복잡도는 O (n^2)이므로 큰 리스트에는 비효율적이다. 

전체 리스트에서 최소값을 찾고 값을 맨 처음 위치와 바꾼 다음 리스트의 나머지 부분에 대해 이 과정을 반복한다.

교환 과정은 n개를 넘지 않으므로 교환 비용이 많이 드는 상황에서 유리하다. 시간 복잡도가 O(n^2)인 정렬 알고리즘에서 선택 정렬은 버블 정렬보다 항상 우수하다. 

//선택 정렬
public static void SelectionSort(int[] arr)
{
    int n = arr.Length;
    for (int i = 0; i < n - 1; i++)
    {
        int minIndex = i;
        for (int j = i + 1; j < n; j++)
        {
            if (arr[j] < arr[minIndex])
            {
                // 최소값을 찾음
                minIndex = j;
            }
        }
        // 최소값과 현재 요소를 교환
        int temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
}

 

 

버블 정렬은 O(n^2)의 시간복잡도로 상당히 느리지만, 코드가 단순하다는 장점이 있다.

배열의 두 수 (a, b)를 고른 뒤, 두 수가 정렬되었다면 건드리지 않고, 아니라면 정렬하는 식으로 진행된다. 

오름차순으로 정렬할 때는 a<b, 내림차순이라면 a>b 여야 정렬된 것으로 판단한다. 정확도가 높고 정밀한 비교가 가능하다는 장점이 있다. 반면 시간이 오래 걸린다는 단점이 있다. N개의 원소가 있다면 N^2의 시간복잡도를 갖게 된다.

// 버블 정렬
int[] data = new int[] { 3, 6, 2, 4, 1, 7, 9, 8, 5 };
int hold = 0;
int[] BubbleSort = new int[] { };

for(int i = 0; i < data.Length - 1; i++)
{
    for (int j = 0; j < data.Length - 1 - i; j++)
    {
        if (data[j] > data[j + 1])
        {
            hold = data[j];
            data[j] = data[j + 1];
            data[j + 1] = hold;
        }
    }
}

for (int i = 0; i < data.Length; i++)
{
    Console.WriteLine(data[i]);
}