Selection Sort

Selection Sort란?

선택 정렬은 리스트에서 최소값을 선택하여 정렬하는 알고리즘입니다.

과정


1. 리스트의 정렬되지 않은 부분에서 최소값을 찾음
2. 찾은 최소값을 리스트의 정렬된 부분 뒤에 넣음
3. 모든 원소가 정렬될 때까지 1번 과정부터 반복

분석

선택 정렬은 각 단계마다 한 원소씩 정렬되므로 n + (n - 1) + (n - 2) + ··· + 2 + 1 = n (n + 1) / 2 = O(n^2) 의 시간복잡도를 갖습니다.

구현

void SelectionSort(int arr[], int len) {
    for(int i = 0; i < len; i++) {
    	int min = INF;
        int idx;
    	for(int j = i; j < len; j++) {
            if(arr[j] < min) {
            	min = arr[j];
                idx = j;
            }
        }
        swap(arr[i], arr[idx]);
    }
}

Bubble Sort

Bubble Sort란?

버블 정렬은 리스트의 첫번째 원소부터 시작하여 인접한 두 원소를 비교하여 정렬하는 알고리즘입니다.

과정


1. 첫번째 원소부터 시작하여 정렬되지 않은 마지막 원소까지 인접한 두 원소를 비교
2. 앞의 원소가 뒤의 원소보다 크다면 두 원소를 교환
3. 모든 원소가 정렬될 때까지 1번 과정부터 반복

분석

버블 정렬은 각 단계마다 한 원소씩 정렬되므로 (n - 1) + (n - 2) + ··· + 2 + 1 = n (n - 1) / 2 = O(n^2) 의 시간복잡도를 갖습니다.

구현

void BubbleSort(int arr[], int len) {
    for(int i = len - 1; i > 0; i++) {
    	for(int j = 0; j < i; j++) {
            if(arr[j] > arr[j + 1]) {
            	swap(arr[j], arr[j + 1]);
            }
        }
    }
}

Insertion Sort

Insertion Sort란?

삽입 정렬은 리스트의 각 원소들을 적절한 순서에 삽입하여 정렬하는 알고리즘입니다.

과정


1. 정렬할 원소를 X 라고할 때 X 가 있던 자리를 Vacancy 로 만듦
2. Vacancy 의 왼쪽 원소와 X 를 비교
3. X 가 더 작다면 왼쪽 원소를 Vacancy 에 넣고 왼쪽 원소가 있던 자리를 Vacancy 로 설정
4. XVacancy 의 왼쪽 원소보다 클 때까지 2번 과정부터 반복
5. 모든 원소가 정렬될 때까지 1번 과정부터 반복

분석

삽입 정렬은 최악의 경우 각 단계마다 매번 리스트의 첫번째 원소까지 비교를 진행해야 하므로 1 + 2 + ··· + (n - 2) + (n - 1) = n (n - 1) / 2 = O(n^2) 의 시간복잡도를 갖습니다.

삽입 정렬은 선택 정렬, 버블 정렬과 달리 리스트가 이미 정렬되어 있는 경우 각 단계에서 비교를 1번 밖에 수행하지 않습니다. 즉 최상의 경우 O(n) 의 시간복잡도를 갖습니다.

리스트의 크기가 작을 경우 리스트가 정렬되어 있을 가능성이 높기 때문에 삽입 정렬은 리스트의 크기가 작을수록 성능이 좋은 알고리즘입니다.

구현

void InsertionSort(int arr[], int len) {
    for(int i = 1; i < len; i++) {
    	for(int j = i; j > 0 && arr[j] < arr[j - 1]; j--) {
            swap(arr[j], arr[j - 1]);
        }
    }
}

Quick Sort

퀵 정렬은 분할 정복 기법을 이용한 Randomized 정렬 알고리즘입니다. Pivot 이라고 부르는 무작위 원소를 하나 선택하여 리스트를 Pivot 을 기준으로 Pivot 보다 작거나 같은 원소 집합, Pivot 보다 큰 원소 집합으로 나누어 정렬을 진행합니다.

Randomized Algorithm

입력이 동일하더라도 알고리즘 진행 과정이 달라질 수 있는 알고리즘

과정

General Quick Sort

  1. 리스트에서 Pivot (무작위 원소)를 하나 선택
  2. Pivot 을 기준으로 리스트를 Pivot 보다 작거나 같은 원소 집합, Pivot 보다 큰 원소 집합으로 나눔
  3. 집합의 크기가 1일 때까지 재귀적으로 1, 2번 과정 반복
  4. 재귀를 탈출하면서 Pivot 보다 작거나 같은 원소 집합, Pivot 보다 큰 원소 집합 순으로 합침

In-Place Quick Sort


0. 리스트의 첫번째 원소를 가리키는 Left 포인터와 리스트의 마지막 원소를 가리키는 Right 포인터 사용
1. 리스트에서 Pivot (무작위 원소)를 하나 선택
2. Pivot 보다 큰 원소를 만날 때까지 Left 포인터를 오른쪽으로 이동시킴
3. Pivot 보다 작거나 같은 원소를 만날때까지 Right 포인터를 왼쪽으로 이동시킴
4. 두 포인터가 멈추면 해당 위치에 있는 원소를 교환함
5. Right 포인터가 Left 포인터의 왼쪽에 위치할 때까지 2번 과정부터 반복
6. Right 포인터의 위치를 Pivot 의 위치로 설정하고 Right 포인터 위치에 있던 원소는 Pivot 이 있던 위치로 이동시킴
7. 두 포인터가 만난 곳을 기준으로 리스트를 두개의 서브 리스트로 나눔
8. 모든 원소가 정렬될 때까지 각 서브 리스트에 대해 0번 과정부터 반복

In-Place Algorithm

입력으로 할당된 메모리 이외에 추가로 상수 크기의 메모리만 사용하는 알고리즘. ex) 선택 정렬, 버블 정렬, 삽입 정렬

분석

퀵 정렬은 각 단계마다 리스트를 두 개의 서브 리스트로 나눠 Pivot 과의 비교를 진행합니다. 따라서 최초의 리스트를 몇번 나누는지에 따라 성능이 결정됩니다.

리스트가 매번 한쪽으로 치우치게 나뉘는 경우엔 O(n^2) 의 시간 복잡도를 가지고 리스트가 매번 균등하게 나뉘는 경우엔 O(n · log n)의 시간복잡도를 갖습니다.

구현

In-Place 구현

void QuickSort(int arr[], int left, int right) {
    if (right <= left)
        return;
    int pivot = left;
    int leftPointer = left + 1;
    int rightPointer = right;
    bool focusedOnLeft = true;
    
    while (leftPointer <= rightPointer) {
        if (focusedOnLeft) {
            if (arr[pivot] < arr[leftPointer]) {
                focusedOnLeft = !focusedOnLeft;
            }
            else {
                leftPointer++;
            }
        }
        else {
            if (arr[pivot] >= arr[rightPointer]) {
                swap(arr[leftPointer], arr[rightPointer]);
                focusedOnLeft = !focusedOnLeft;
            }
            else {
                rightPointer--;
            }
        }
    }
    
    swap(arr[pivot], arr[rightPointer]);
    pivot = rightPointer;
    
    QuickSort(arr, left, pivot - 1);
    QuickSort(arr, pivot + 1, right);
}

Merge Sort

Merge Sort란?

병합 정렬은 분할 정복 기법을 이용한 Stable Sort 알고리즘입니다. 리스트를 반으로 나눌 수 없을 때까지 나누고 나눠진 각 서브 리스트들을 다시 합치면서 정렬을 진행합니다.

Stable Sort

입력의 상대적인 순서가 정렬 후에도 유지되는 정렬 알고리즘. ex) 삽입 정렬, 버블 정렬, 병합 정렬, 기수 정렬

과정


(출처: 위키 백과 - 합병 정렬)

  1. 재귀적으로 리스트를 나눌 수 없을 때까지 반으로 나눔
  2. 두 서브 리스트의 가장 앞에 위치한 원소를 바교
  3. 더 작은 원소를 해당 서브 리스트에서 꺼내고 새로운 리스트에 넣음
  4. 두 서브 리스트에 원소가 남아있지 않을 때까지 2, 3번 과정 반복
  5. 재귀를 탈출하면서 정렬된 새로운 리스트 반환
  6. 모든 재귀의 단계에서 2번 과정부터 반복

분석

병합 정렬은 매번 리스트를 반으로 나누기 때문에 O(log n) 깊이의 재귀 호출이 발생하며 각 재귀마다 O(n) 개의 원소를 비교하므로 O(n · log n)의 시간복잡도를 갖습니다.

서브 리스트를 합치는 과정에서 새로운 리스트를 위한 메모리가 추가로 필요하기 때문에 In-Place 구현이 불가능합니다.

구현

int newArr[MAX_SIZE];

void Merge(int arr[], int left, int mid, int right) {
    int i = left, j = mid + 1, k = left;
    for( ; k <= right; k++){
        if(j > right) 
            newArr[k] = arr[i++];
        else if(i > mid) 
            newArr[k] = arr[j++];
        else if(newArr[i] < newArr[j]) 
            newArr[k] = arr[i++];
        else 
            newArr[k] = arr[j++];
    }

    for(i = left; i <= right; i++) {
        arr[i] = newArr[i];
    }
}

void MergeSort(int arr[], int low, int high){
    if(low >= high) 
    	return;

    int mid = (low + high) / 2;

    MergeSort(arr, low, mid);
    MergeSort(arr, mid+1, high);

    Merge(arr, left, mid, right);
}

Heap Sort

Heap Sort란?

힙 정렬은 Heap 에서 최소값(혹은 최대값)를 제거하고 다시 Heap 을 만드는 과정을 반복하여 정렬된 리스트를 얻는 알고리즘입니다.

Heap이란?

과정


(출처: 나무위키 - 정렬 알고리즘)

  1. 주어진 리스트로 배열 기반의 Heap을 만듦
  2. Heap에서 루트(최소값 혹은 최대값)을 제거하여 새로운 리스트에 넣음
  3. Heap이 비어 있게 될 때까지 2번 과정을 반복하여 정렬된 리스트를 얻음

분석

힙 정렬에서 Heap을 만들때는 분할 정복 기법을 이용하여 Bottom Up Heap Construction을 합니다. Bottom Up Heap Construction 시 Heap의 순서 조건을 만족시키기 위해 Down Heap을 하는데, 이는 O(log n) 의 시간복잡도를 갖습니다. 따라서 Heap을 만드는데 O(n · log n) 이 소요됩니다.

Heap에서 루트를 제거하는 과정에도 Down Heap 과정이 존재하며 따라서 Heap의 모든 노드를 제거하는데 O(n · log n) 이 소요됩니다.

따라서 힙 정렬은 O(n · log n) 의 시간복잡도를 갖습니다.

Radix Sort

Radix Sort

기수 정렬은 각 원소의 값을 표현하는 비트수(자릿수)가 같을 때 사용하는 정렬 알고리즘입니다. 각 원소를 정렬된 Bucket 에 분배하여 정렬을 진행합니다.

과정

  1. 각 자리의 값에 대응되는 Bucket 에 원소를 분배
  2. 맨 뒷자리부터 맨 앞자리까지 단계적으로 분배를 진행

분석

기수 정렬은 자릿수만큼의 단계를 거치며 각 단계마다 데이터를 그저 대응하는 Bucket 에 분배하는 것으로 정렬이 이루어집니다. 따라서 O(k · n) 의 시간복잡도를 갖습니다. 여기서 k자릿수를 의미합니다.

Couting Sort

Counting Sort란?

카운팅 정렬은 특정 값을 갖는 원소의 개수를 값에 대응하는, 정렬된 Bucket 에 저장하여 정렬하는 알고리즘입니다.

과정

  1. 리스트의 값에 따라 대응하는 Bucket 을 찾음
  2. 해당 Bucket 에 저장된 개수를 하나 증가시킴
  3. 모든 원소에 대해 1, 2번 과정을 반복
  4. Bucket 의 순서와 Bucket 에 저장된 개수를 통해 정렬된 리스트를 만들어냄

분석

카운팅 정렬은 Bucket 으로 배열을 사용하기 때문에 원소의 값이 정수여야 하며 데이터의 범위에 따라 성능이 결정됩니다. 즉 O(n + k) 의 시간복잡도를 갖습니다. 여기서 k데이터의 최대값을 의미합니다.

profile
안드로이드 개발자를 꿈꾸는 사람

0개의 댓글