C++ 정렬(Sorting) 알고리즘 정리(1) - 이론

Intro

 

정렬 : 데이터를 특정한 기준에 따라 순서대로 나열하는 것. ex) 오름차순, 내림차순

데이터가 랜덤하게 분포해있으면 실제로 정보를 얻거나 사용하기 힘들기 때문에 보통 데이터를 사용하기 전 전처리 과정으로 정렬을 아주 많이 사용하게 된다. ex) 이진탐색

사실 sorting 함수는 C++에서도 기본적으로 제공한다. 

 

#include <algorithm>

sort(begin, end, compare_function);

 

을 이용해 사용한다. compare_function은 명시하지 않으면 기본 오름차순이다. 시간복잡도도 O(nlogn) 이기 때문에 좋은 함수이지만 구현해야 하는 경우를 위해 여러 알고리즘의 이론과, 그 코드를 정리해볼 예정이다.

 

실제 코드정리는 -> maru20564.tistory.com/11

C++ 정렬(Sorting) 알고리즘 정리(2) - 코드, 시간 복잡도 측정

 

 

 

선택 정렬 (Selection Sort)

 

정렬 코드를 배울 때 가장 기본으로 배우는 정렬 방식이다. 동작 원리를 이해하기가 쉽고 코드 구현도 쉬운 편이다.

하지만 모든 데이터들을 일일이 비교하기 때문에 시간이 오래 걸린다. 복잡도 : O(n^2)

따라서 큰 데이터나 시간 제한이 있을 때는 적합하지 않을 때가 많다.

 

선택 정렬은 전체 배열에서 가장 작은 데이터를 선택하여 배열의 가장 앞으로 보내는 과정을 반복하여 전체 배열을 정렬한다.

 

7

5

1

2

1

5

7

2

1

5

7

2

1

2

7

5

 

위와 같은 방식으로 배열 i번째~n번째까지의 data에서 가장 작은 숫자를 선택하여 i번에 해당하는 숫자와 swap한다. 그렇게 하면 1~i번째까지는 정렬이 된 배열이 된다. 이를 n번까지 반복하여 전체 배열을 정렬시킨다.

 

 

 

삽입 정렬 (Insertion Sort)

 

삽입 정렬은 선택 정렬에 비해 조금 구현이 어렵지만 직관적이고 선택 정렬보다는 빠르다. 특히 정렬이 거의 되어있는 경우에 유리하다. 삽입정렬은 말 그대로 정렬된 배열에 새로운 값을 올바른 위치에 삽입하면서 전체 정렬된 배열을 만들어낸다.

시간 복잡도 : O(n^2)

 

7

5

1

2

5

7

1

2

5

7

1

2

1

5

7

2

 

1~i-1번째까지의 정렬된 배열에 i번째 원소를 새로 삽입한다. 이 때 삽입할 위치를 골라 들어가는 것이 삽입 정렬이다. 이미 i-1번까지는 정렬이 되어있으니 그 순서에 맞게 비교하여 들어가면 된다. n번째까지 삽입하면 전체 배열이 정렬 완료 된다.

 

 

 

퀵 정렬 (Quick Sort) ☆

 

문제에서 가장 많이 물어보며 많이 사용되는 정렬이다. 기준 데이터(pivot)를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 식으로 정렬한다. 그렇게 큰 데이터와 작은 데이터를 바꾸면 왼쪽에는 pivot보다 작은 데이터들이, 오른쪽에는 pivot보다 큰 데이터들이 남게 된다. 따라서 pivot을 그 가운데 삽입하고 왼쪽 데이터들과 오른쪽 데이터들을 재귀적으로 계속 정렬해나가는 방법이다. 이 때 원소가 1개인 배열일 경우 이미 정렬이 되었다고 생각한다.

 

시간복잡도가 O(nlogn)이기 때문에 선택, 삽입 정렬에 비해 빠르다. 하나하나씩 비교하고 삽입하는 것이 아닌 배열을 쪼개가며 계산하는 방식이기 때문이다.

단 데이터가 이미 정렬되어있을 경우에는 느리게 작동할 수도 있다. 완벽히 정렬된 경우에는 worst case가 발생하기도 함.

 

파란색 : pivot, 빨간색 : left에서 pivot보다 크거나 right에서 pivot보다 작은 숫자를 탐색한 결과

 

5

7(left)

1

2

6

3(right)

5

3

1

2(right)

6(left)

7

2

3

1

5(기준)

6

7

2

3

1

6

7

 

pivot 배열의 맨 첫번째 값으로 정한 뒤 2번째부터 -> 방향으로 pivot보다 큰 수를 찾는다. 또, 마지막값부터 <- 방향으로 pivot보다 작은 수를 찾는다. 그 때 left와 right 위치가 그대로일 때 SWAP한다. (위 그림의 1번 array -> 2번 array)

만약 left가 right보다 오른쪽에 있게 된다면 pivot보다 작은 데이터와 pivot을 swap한다. (2번 array -> 3번 array)

 

이 SWAP을 left <=right 인 동안 반복한다.

반복이 끝났으면 right를 기준으로 왼쪽과 오른쪽 배열에 대해 재귀적으로 quick sort를 시작한다.

 

 

 

병합 정렬 (Merge Sort)

 

분할 정복 알고리즘 중 하나이다. (큰 문제를 두 개의 작은 문제로 분리한 후 해결 후 다시 결과를 모아 원래의 문제를 해결하는 전략)

array의 길이가 1 이하이면 이미 정렬된 것으로 보고, 그렇지 않은 경우에는 두 개의 array로 나눈다.

그 후 정렬된 작은 array들을 하나로 합쳐 원래 array의 정렬된 값을 알아낸다.

 

지금까지의 정렬은 array 안에서 진행했지만 병합 정렬은 임시 배열이 필요하기 때문에 메모리 공간이 더 필요하다.퀵 정렬과 다르게 데이터의 분포에 영향을 덜 받는다. 입력 데이터에 상관 없이 시간 복잡도는 O(nlogn)이다.

 

array로 하면 일일이 데이터를 이동시켜야 하기 때문에 낭비가 심하지만 linked list로 구성해 index만 바꾸면 효율적이게 된다.

 

5

7

1

2

6

3

5	7	1
2	6	3

-> 전부 쪼개진 다음 다시 합치면

1	5	7
2	3	6

1

2

3

5

6

7

 

부분배열로 쪼개는 곳까지는 정렬이 일어나지 않는다. 쪼갠 배열을 다시 합치는 과정에서 정렬이 일어난다. 두 배열을 하나로 합칠 때 왼쪽 배열의 value와 오른쪽의 value를 서로 비교해서 작은 것을 순서대로 대입하면 된다.

 

위 그림을 예를 들면 1과 2를 비교하여 1을 처음에 대입, 5와 2를 비교하여 2를 대입, 5와 3을 비교하여 3을 대입... 순이다.

 

 

 

이 외에도 버블 정렬, 힙 정렬, 계수 정렬 등이 존재한다. 기회가 된다면 다음에 다시 정리해보겠다.