20240129_정렬 알고리즘

오늘의 TIL은 C#에서 사용하는 정렬 알고리즘에 대한 내용이다.

 

정렬 알고리즘이란 배열 등이 주어졌을 때,

 

이를 해당하는 조건(오름차순, 내림차순 등)으로 정렬하는 알고리즘을 말한다.

 

정렬을 하는 방법이 다양하므로 알고리즘도 다양하게 존재하는데,

 

버블 정렬(bubble sort)

선택 정렬(selection sort)

삽입 정렬(insert sort)

병합 정렬(merge sort)

힙 정렬(heap sort)

퀵 정렬(quick sort)

 

등이 있다.

 

 

1. 버블 정렬(bubble sort)

버블 정렬은 서로 인접한 두 원소를 검사하여 오름차순(혹은 내림차순)으로 나열하는 방법으로,

for 문을 이중으로 사용해서 모든 원소에 대해 검사하므로 시간복잡도는(N^2)이다

예제 코드를 살펴보면 아래와 같다.

 

int[] arr = new int[]{};

int tmp = 0;

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

 

위와 같이 맨 처음 인덱스부터 마지막 인덱스까지 이중으로 순회하며 숫자의 크기를 비교하여 두 수를 바꿔주는데

 

모든 원소를 비교하므로 정밀한 비교가 가능하고 그로 인해 정확도가 높지만,

 

모든 원소를 비교하므로 시간이 오래걸린다는 단점이 있다.

 

 

2. 선택 정렬(Selection Sort)

선택 정렬은 정렬되지 않은 데이터들에 대해 가장 작은 데이터를 찾아서 가장 앞의 데이터와 교환해나가는 방식이다.

 

오름차순으로 정렬하는 경우에는

 

1. 배열에서 최소값을 찾은 후에

2. 최소값을 맨 앞의 값(0번 인덱스)와 교체한다.

3. 맨 앞의 값(0번 인덱스)를 제외한 부분에서 1번과 2번을 수행한다.

4. 인덱스를 하나씩 채워가며 3번을 반복한다.

 

예제 코드를 살펴보면 아래와 같다.

 

int[] arr = new int[]{};

int tmp = 0;
int min;

for (int i = 0; i < arr.Length - 1; i++)
{
    min = i;
    for (int j = i + 1; j < arr.Length; j++)
    {
        if (arr[j] < arr[min])
        {
            min = j;
        }
    }
    tmp = arr[min];
    arr[min] = arr[i];
    arr[i] = tmp;
}

 

위와 같이 구현할 수 있는 선택 정렬은 버블 정렬과 같이 이중 for문을 순회하면서 작업을 수행하므로

 

장단점이 같은 공통점(정밀한 비교, 높은 정확도, 시간이 오래 걸리는 단점)을 갖고있다.

 

 

3. 삽입 정렬(insert sort)

삽입 정렬은 배열에서 하나의 원소를 뽑아낸 다음, 이 원소와 나머지 원소들을 비교하며

 

조건에 맞는 위치에 삽입하는 방식이다.

 

예를 들어서 오름차순으로 정렬하는 경우에 4번 인덱스에서 뽑아낸 원소를 3번 인덱스와 비교하여 

 

4번 인덱스의 크기가 작다면 서로의 위치를 변경하고, 2번 인덱스와 비교하는 방식으로 진행하여

 

4번 인덱스보다 작은 숫자가 나올 때까지 반복한다.

 

이 과정을 모든 원소가 정렬될 때까지 반복한다.

 

예제 코드를 살펴보면 아래와 같다.

 

int[] arr = new int[]{};

int key;
int j;

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

 

삽입 정렬이 위의 두 정렬과 가장 큰 차이점은 특정 지점(key 값이 해당 인덱스보다 큰 지점)에서 break를 해준다는 점인데,

 

이를 통해서 삽입 정렬은 최대 N^2의 시간복잡도를 가지지만, 최소로는 N의 시간복잡도를 가지는 차이를 갖는다.

 

즉, 모든 요소에 대해 정밀하게 비교하지만 최적의 경우에는 훨씬 빠른 속도를 가질 수 있다는 것이다.

 

단점으로는 최악의 경우에는 N^2의 시간복잡도를 가지게 되어 시간이 오래 걸리는 점이다.

 

 

 

오늘은 정렬 알고리즘의 기본이라고 할 수 있는 시간복잡도를 N^2을 가질 것으로 예측되는 3가지 모델

 

버블 정렬, 선택 정렬, 삽입 정렬을 알아봤는데,

 

내일 이어서 nlogN을 가지는 병합 정렬에 대해 알아볼 예정이다.