Chapter 03. 정렬

Chapter 03. Sort Algorithm

3.0 정렬 알고리듬

3.0-0 정렬 알고리듬

- 목록 안에 저장된 요소들을 특정한 순서대로 재배치하는 알고리듬

- 정렬하는 이유

좀 더 효율적인 알고리듬을 사용하기 위해서

사람이 읽기 편하도록

등등

- 입력 데이터는 일반적으로 배열 같은 자료 구조에 저장

아무 위치로의 임의 접근이 용이함

cf. 링크드 리스트를 사용하면 처음 혹은 끝부터 차례로 훑어야 함.

- 줄 세우는데 흔히 사용하는 순서: 숫자 순서, 사전 순서

정렬 방향: 오름차순, 내림차순

- 다양한 정렬 알고리듬이 있음

시간 복잡도 차이

메모리 사용량 차이

안정성(stability) 차이

직렬 Vs. 병렬 차이(이 과목에서는 직렬 정렬 알고리듬만.)

3.0-1 정렬 알고리듬의 안정성

- 안전성(safety)이 아님.

똑같은 키(key)를 가진 데이터들의 순서가

바뀌지 않으면 안정적인 정렬

바뀌면 불안정적인 정렬

3.0-2 안정성을 잘 모르는 이유

- 같은 키를 가진 데이터의 순서가 바뀌어도

대부분 문제가 되진 않음. 열에 하나 정도.

- 그래서 잘 모르고, 생각도 안하는 부분

- "모든 정렬 알고리듬은 같은 키를 가진 데이터의 순서를 안바꾼다."

심지어는 이렇게 잘못 생각하기도 함.

- 이 때문에 버그가 나도 못 고치는 경우가 있음.

- 결론

어떤 정렬 알고리듬은 안정성을 보장함.

어떤 정렬 알고리듬은 안정성을 보장하지 않음.

3.0-3 안정성이 문제가 되는 경우

- 정렬 기준이 되는 정렬 키(sort key)와 실제 데이터가 다를 경우

- 구조체 / 클래스의 일부 멤버로만 정렬 키로 사용할 경우

3.0-4 대표적인 정렬 알고리듬

- 버블 정렬

가장 쉬운 정렬. 언제라도 구현 가능 해야함.

- 선택 정렬

가장 쉬운 정렬.

- 삽입 정렬

- 퀵 정렬

언제라도 설명 할 수 있어야 함.

- 병합 정렬

이해하는 정도면 충분함.

- 힙 정렬

이해하는 정도면 충분함.

3.0-5 정렬 알고리듬은 아무리 빨라도

- 배열을 비교/정렬하려면 모든 요소를 최소 한 번씩은 방문해야함.

배열의 모든 요소를 방문하는 것은 O(N)

따라서 정렬 알고리듬은 아무리 빨라도 O(N)보다 느림

흔히 보는 시간 복잡도 중 O(N) 다음으로 느린 것은 O(NlogN)

3.0-6 정렬 알고리듬 비교

	평균	최악	메모리	안정성
버블	O(N^2)	O(N^2)	O(1)	O
선택	O(N^2)	O(N^2)	O(1)	X
삽입	O(N^2)	O(N^2)	O(1)	O
퀵	O(NlogN)	O(N^2)	O(NlogN)	X
병합	O(NlogN)	O(NlogN)	O(N)	O
힙	O(NlogN)	O(NlogN)	O(1)	X

3.0-7 상황에 따른 정렬 알고리듬 선택

- 기본적으로는 퀵 정렬

C도 qsort() 함수를 기본 제공

- 간단히 구현할 때는 버블 정렬

구현이 매우 쉬워서, 10년 안 써도 까먹지 않을 정도.

- 어떤 경우에도 느려지면 안될 때는 병합 또는 힙 정렬

평균은 퀵 정렬보다 느리지만 최악의 경우도 여전히 O(NlogN)

- 특수한 상황에 적합한 정렬 알고리듬도 존재함. ex. 기수 정렬

3.1 버블 정렬

3.1-0 버블 정렬(Bubble Sort)

- 가장 간단한 정렬 알고리듬 중 하나

기본기 중의 기본기

- 이웃 요소 둘을 비교해서 올바른 순서로 고치는 과정을 반복

- 한 번 목록을 순회할 때마다 가장 큰 값이 제일 위로 올라감

큰 기포일수록 수면 위로 더 빨리 떠오르는 모습을

닮았다고 해서 버블 정렬

3.1-1 버블 정렬 알고리듬

- Ex030101_bubbleSort

/* main.cpp */

#include <iostream>

using namespace std;

enum { LENGTH = 8 };

void swap(int* op1, int* op2);
void bubbleSort(int arr[], size_t len);

int main(void)
{
    int nums[LENGTH] = { 7, 0, 6, 1, 5, 2, 4, 3};

    bubbleSort(nums, LENGTH);

    return 0;
}

void swap(int* op1, int* op2)
{
    int temp = *op1;
    *op1 = *op2;
    *op2 = temp;
}

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

3.1-2 버블 정렬의 시간 복잡도

- 목록을 훑은 총 횟수: N - 1번

- 한 번 훑을 때

가장 많이 방문했던 요소 수는 N - 1번(1회차)

가장 적게 방문했던 요소 수는 1번(N - 1회차)

평균 N/2번

- 평균 시간 복잡도: O((N-1) * N / 2) ~= O(N^2)

3.1-3 버블 정렬의 공간 복잡도

- 새로 만든 목록 없음.

즉 공간 복잡도: O(1)

3.1-4 버블 정렬의 안정성

- 값이 같은 경우 순서를 바꾸지 않음.

안정적인 정렬 알고리듬

3.2 선택 정렬

3.2-0 선택 정렬(Selection Sort)

- 역시 가장 간단한 정렬 알고리듬 중 하나

목록을 총 N - 1번 훑으면서 다음 과정을 반복

0. 요소 0부터 훑으면서 최솟값 찾아서 요소 0과 교환

1. 요소 1부터 훑으면서 최솟값 찾아서 요소 1과 교환

2. 요소 2부터 훑으면서 최솟값 찾아서 요소 2와 교환

...

- 최솟값을 찾아 선택한다고 해서 선택 정렬

3.2-1 선택 정렬 알고리듬

- Ex030201_selectionSort

/* main.cpp */

#include <iostream>

using namespace std;

enum { LENGTH = 8 };

size_t findMinIndex(int arr[], size_t len);
void swap(int* op1, int* op2);
void selectionSort(int arr[], size_t len);

int main(void)
{
    int arr[LENGTH] = { 7, 1, 6, 2, 5, 3, 4, 0};

    selectionSort(arr, LENGTH);

    for (size_t i = 0; i < LENGTH; ++i) {
        printf("%d ", arr[i]);
    }

    return 0;
}

size_t findMinIndex(int arr[], size_t start, size_t end)
{
    int min = INT32_MAX;
    size_t min_i;
    for (size_t i = start; i < end; ++i) {
        if (arr[i] < min) {
            min = arr[i];
            min_i = i;
        }
    }
    return min_i;
}

void swap(int* op1, int* op2)
{
    int temp = *op1;
    *op1 = *op2;
    *op2 = temp;
}

void selectionSort(int arr[], size_t len)
{
    for (size_t i = 0; i < len - 1; ++i) {
        size_t minIndex = findMinIndex(arr, i, len);
        swap(&arr[i], &arr[minIndex]);
    }
}

3.2-2 선택 정렬의 시간/공간 복잡도와 안정성

- 시간/공간 복잡도: 버블 정렬과 동일

안정성: 보장 안됨.

3.3 삽입 정렬

3.3-0 삽입 정렬(Insertion Sort)

- 역시 간단한 정렬 알고리듬 중 하나

- 버블 정렬, 선택 정렬보다 구현은 아주 조금 힘듦.

- 목록을 차례대로 훑으면서 다음 과정을 반복

0. 현재 위치의 요소를 뽑음.

1. 이걸 과거에 방문했던 요소들 중에

어디 사이에 넣어야 정렬이 유지되는지 판단

2. 그 위치에 삽입

3. 삽입으로 인해 다른 요소들을

오른쪽으로 밀어야(shift) 할 수도 있음.

3.3-1 삽입 정렬 알고리듬

- Ex030301_insertionSort

/* main.cpp */

#include <iostream>

using namespace std;

enum { LENGTH = 8 };

void swap(int* op1, int* op2);
void selectionSort(int arr[], size_t len);

int main(void)
{
    int nums[LENGTH] = { 7, 0, 6, 1, 5, 2, 4, 3};

    selectionSort(nums, LENGTH);

    for (size_t k = 0; k < LENGTH; ++k) {
        printf("%d ", nums[k]);
    }

    return 0;
}

void swap(int* op1, int* op2)
{
    int temp = *op1;
    *op1 = *op2;
    *op2 = temp;
}

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

3.4 퀵 정렬

3.4-0 퀵 정렬(Quick Sort)

- 실무에서 가장 많이 사용하는 정렬

일반적/범용적으로 가장 빠름.

- 진정한 분할 정복 알고리듬

모든 요소를 방문함(decrease-and-conquer와의 차이)

복잡도에 log가 있다는 것에서 눈치 챌 수 있음.

- 어떤 값(pivot)을 기준으로 목록을 하위 목록 2개로 나눔

목록을 나눈 기준은 pivot보다 작냐 크냐

이 과정을 재귀적으로 반복

재귀 단계가 깊어질 때마다 새로운 pivot 값을 뽑음.

3.4-1 퀵 정렬 알고리듬

- Ex030401_quickSort

#include <iostream>

using namespace std;

enum { LENGTH = 8 };

int partition(int arr[], int left, int right);
void quickSort(int arr[], int left, int right);

int main(void)
{
	int nums[LENGTH] = {3, 8, 7, 0, 2, 1, 4, 5};

	quickSort(nums, 0, LENGTH - 1);

	for (size_t i = 0; i < LENGTH; ++i) {
		printf("%d ", nums[i]);
	}

	return 0;
}

int partition(int arr[], int left, int right)
{
	int pivot = arr[left];
	int low = left + 1;
	int high = right;

	while (low <= high) {
		while (arr[low] < pivot) {
			++low;
		}

		while (pivot < arr[high]) {
			--high;
		}

		if (low <= high) {
			swap(arr[low], arr[high]);
		}
	}
	swap(arr[left], arr[high]);

	return high;
}

void quickSort(int arr[], int left, int right)
{
	if (right < left) {
		return;
	}

	int pivotIndex = partition(arr, left, right);
	quickSort(arr, left, pivotIndex - 1);
	quickSort(arr, pivotIndex + 1, right);
}

3.4-2 퀵 정렬의 시간 복잡도

- 각 단계마다 방문하는 요소 수: O(N)

- 총 몇 개의 단계?

매 단계에서 좌우가 균등하게 나뉘면: O(logN)

매 단계에서 한쪽으로 몰리면: O(N)

평균: O(NlogN)

최악: O(N^2)

- 최악의 상황 예: 분할할 때마다 한쪽으로 몰리는 경우

ex. 4 3 1 5 2에서 4 3 1 2 5 -> 2 3 1 4 5가 되고

2 3 1와 5로 나뉨. 2 3 1쪽은 기준값의 최종 위치가 한쪽으로 몰림.

3.4-3 최악의 상황 피하는 방법

- 제일 끝이 아닌 다른 위치를 기준값으로 뽑음.

제일 끝을 기준값으로 잡으면 어느 경우에든

최악의 상황이 연출됨.

- 모든 경우에 작동하는 방법은 [왼쪽, 오른쪽]

범위에서 랜덤 위치를 기준값으로 뽑음.

- 그래도 최악의 상황은 나오지만, 아주 작은 확률

- 근데, O(N^2)을 절대로 허용할 수 없는 분야라면?

다른 정렬을 사용할 것.

평균 속도와 최악의 상황 사이의 균형.

3.4-4 분할함수를 구현하는 방법은 여러 가지

- 왼쪽에서 오른쪽으로만 진행하는 방식을

Lomuto 분할법이라고 함. 보통 가장 자리 값을 기준값으로 잡아야 잘 작동.

- 왼쪽->오른쪽, 오른쪽->왼쪽 번갈아 진행하는 방식을

Hoare 분할법이라고 함. 이 경우는 어떤 값을 기준값으로 잡아도 잘 작동.

3.4-5 퀵 정렬의 공간 복잡도

- 재귀적으로 함수를 호출함.

즉, 함수 호출 깊이만큼 스택 메모리 사용

O(logN). 다만 스택 메모리라 할당/해제가 매우 빠름.

- 실제 원본 배열을 고침(In-place): O(1)

- quickSort() 함수에서 재귀 함수를 두 번 호출함.

두 번째 호출은 꼬리 재귀를 통해 피할 수 있음.

- Ex030405_stability

3.5 병합 정렬

3.6 힙 정렬

3.7 퀵 정렬이 사랑받는 이유

저작자표시 비영리 변경금지

'C > 자료구조와 알고리듬' 카테고리의 다른 글

Chapter 06. 스택(Stack) (2)	2021.11.10
Chapter 05. 가변 길이 배열(Variadic Array) (0)	2021.11.10
Chapter 04. 배열(Array) (0)	2021.11.01
Chapter 02. 탐색 (0)	2021.06.17
Chapter 01. 자료구조와 알고리듬 (0)	2021.06.17

GameStudy

GameStudy

Chapter 03. 정렬

'C > 자료구조와 알고리듬' 카테고리의 다른 글

댓글

티스토리툴바

Chapter 03. 정렬

'C > 자료구조와 알고리듬' 카테고리의 다른 글

관련글

댓글

티스토리툴바