선택 정렬 (Selection sort)
선택 정렬은 이름과 같이, 현재 위치에 들어갈 값을 찾아 정렬하는 방법입니다.
현재 위치에 들어갈 값의 크기가 작으면 최소 선택 정렬 (Minimum Selection sort), 값의 크기가 크다면 최대 선택 정렬 (Maximum Selection sort)로 구분 할 수 있습니다.
최소 선택 정렬은 오름차순으로 정리되고, 최대 선택 정렬은 내림차순으로 정렬됩니다.
최소 선택 정렬의 정렬 로직은 다음과 같습니다.
정렬되지 않은 인덱스의 맨 앞부터, 배열의 마지막까지 값 중 가장 작은 값을 찾습니다.
가장 작은 값을 찾는다면(첫 인덱스부터 전체 조회가 끝난 이후) 그 값을 현재 인덱스의 값과 교체합니다.
다음 인덱스부터(N+1) 위의 과정을 반복합니다.
한번 탐색이 끝날때마다 탐색 범위의 맨 앞의 인덱스에 최소값이 고정되기 떄문에 선택 정렬 알고리즘은 n개, n-1개, n-2개 ... 1개까지 비교를 반복해서 진행하게 됩니다.
첫 배열의 정렬상태와 상관없이 전체 배열의 비교를 진행하기 떄문에 시간복잡도는 O(N^2)입니다.
공간복잡도는 하나의 배열에서 비교를 진행하기 때문에 O(N)입니다.
버블 정렬 (Bubble sort)
버블 정렬은 매번 인접한 두개의 인덱스에 할당된 값을 비교하여 정한 기준(오름차순, 내림차순)에 따라 기준의 값의 위치를 변경하는 정렬 알고리즘입니다.
오름차순으로 정렬할 경우, 비교를 진행할때마다 큰 값이 1칸씩 뒤로 이동하며 배열을 한 번 순회할때마다 제일 큰 값이 가장 마지막의 인덱스에 위치하게 됩니다.
제일 마지막에 순회하며 비교한 값들중 가장 큰 값이 제일 뒤로 위치하여 고정되기 때문에, n-1개, n-2개 ... 1개까지 비교를 반복하여 O(N^2)의 시간복잡도를 가지게 됩니다.
공간복잡도도 하나의 배열에서 비교를 진행하기 때문에 O(N)입니다.
(오름차순) 버블 정렬의 동작 로직은 다음과 같습니다.
두번째 인덱스부터, 바로 앞의 인덱스의 값과 비교를 시작합니다.
이전 인덱스의 값이 현재 인덱스의 값보다 크다면 현재 인덱스의 값과 바꿔줍니다.
현재 인덱스가 더 크다면 교환하지 않습니다.
위의 과정을 배열의 마지막 인덱스까지 반복합니다.
한번 순회를 거칠때마다 순회한 구간의 맨 마지막 인덱스는 자동으로 고정되므로, 배열의 길이가 7이라면 6번, 5번, 4번 이와같이 순회하는 배열의 마지막 인덱스가 하나씩 줄어들게 됩니다.
삽입 정렬 (Insertion Sort)
삽입 정렬은 배열의 두번째 인덱스부터 시작하며, 현재 위치에서 그 이하의(앞의 인덱스의) 배열을 비교하며 자신의 위치를 찾아서 그 위치에 값을 삽입하는 정렬입니다.
삽입 정렬의 로직은 다음과 같습니다.
- 두번째 인덱스부터 시작합니다. 현재 인덱스의 값은 별도의 변수에 저장한 후, 비교 인덱스를 현재 인덱스 -1 로 설정합니다.
- 별도로 저장한 변수의 값과, 비교 인덱스의 값을 비교하여, 비교 인덱스의 값이 더 작으면 현재 인덱스를 -1로 변경하며 인덱스가 0이 될 때까지 반복합니다. 비교 인덱스의 값보다 크다면 현재 인덱스 +1에 별도로 저장한 변수의 값을 저장합니다.
- 위 과정을 마지막 인덱스까지 반복합니다.
삽입 정렬 알고리즘의 경우 n-1개, n-2개, ... 1개까지 비교를 진행하여 시간복잡도는 O(n^2)입니다. 다만 다른 정렬 알고리즘과 다른점은 현재 저장된 배열의 값이 모두 정렬되어 있는 상태라면 배열을 한번만 순회하기 때문에 O(n)의 시간복잡도를 나타나게 되는 특징이 있습니다.
비교를 진행할때 하나의 배열만을 사용하기에, 공간복잡도는 O(n)입니다.
병합 정렬 (Merge sort)
병합 정렬은 분할 정복 알고리즘(Divide and conquer algorithm) 방식으로 설계된 알고리즘입니다. 분할 정복 알고리즘은 큰 문제를 반으로 쪼개어 해결하는 방식으로 병합 정렬의 경우, 배열의 길이가 1이 될때까지 쪼개어 반복합니다.
하나의 배열을 입력받아, 두개의 배열로 계속 쪼개나간 후, 분할이 모두 이루어진 이후에 다시 합치는 과정을 거치며 정렬된 하나의 배열을 출력(리턴)합니다.
분할 과정은 다음과 같습니다.
- 현재 배열을 반으로 나누어줍니다.
- 나누어진 배열의 길이가 1보다 클 경우, 다시 1번을 반복합니다.
- 나누어진 베열의 길이가 1보다 작을경우 분할 과정을 종료합니다.
분할 과정의 경우 크기가 n인 배열을 매번 분할한다면 처음은 n/2 n/2개, 두번째는 n/4 n/4 n/4 n/4개
, 이런 과정을 반복하게 되어서, logn만큼의 시간복잡도를 가지게 됩니다.
이후 합병 과정이 진행됩니다.
- 두 배열 a,b의 요소를 비교합니다. 현재 인덱스를 i, j로 가정합니다.
- a[i]와, b[j]를 비교합니다.
- 오름차순의 경우, a[i]보다 b[j]가 크다면 a[i]를 C라는 새 배열에 저장한 후, i의 값을 1 증가합니다.
- 2~3의 과정을 i 혹은 j가 배열의 끝까지 도달할때까지 반복합니다.
- i 혹은 j가 배열의 끝까지 도달한 이후 남은 값을 C 배열에 모두 저장합니다.
- C 배열을 원래의 배열에 저장합니다.
합병 과정의 경우 나누어진 배열만큼의 시간복잡도를 가지게 됩니다. 원래 주어진 배열이 C라고 한다면, C라는 배열을 A, B로 반씩 나누었을때 O(A + B)의 시간복잡도를 가지게 됩니다.
A + B = C이므로, O(N)의 시간복잡도를 가지게 됩니다.
분할과 합병과정을 모두 거치므로, 병합정렬의 경우 O(nlogn)의 시간복잡도를 가지게 됩니다.
배열은 정렬을 위한 배열을 하나 더 사용하므로, 2N이 됩니다.
별도의 최적화 과정(in place)과정을 거친다면 새로운 배열을 사용하지 않고 인덱스만으로 분할 과정을 거쳐서 사용되는 메모리를 줄일 수 있습니다.
퀵 정렬 (Quick sort)
퀵 정렬은 병합 정렬과 비슷하게 정복 알고리즘(Divide and conquer algorithm) 방식으로 설계된 알고리즘입니다. pivot이라는 하나의 기준이 되는 값을 정하고 이 값보다 작은 값들을 왼쪽, 큰 값들을 오른쪽으로 옮기는 방법으로 정렬이 이루어 집니다. 이를 반복해 분할되는 배열의 길이가 1보다 작을때까지 반복하게 됩니다.
퀵 정렬이 동작하는 순서는 다음과 같습니다.
- 리스트 안에 있는 한 요소를 선택한다. 이렇게 고른 원소를 피벗(pivot) 이라고 한다.
- 피벗을 기준으로 피벗보다 작은 요소들은 모두 피벗의 왼쪽으로 옮겨지고 피벗보다 큰 요소들은 모두 피벗의 오른쪽으로 옮겨진다. (피벗을 중심으로 왼쪽: 피벗보다 작은 요소들, 오른쪽: 피벗보다 큰 요소들)
- 피벗을 제외한 왼쪽 리스트와 오른쪽 리스트에 대하여 1~2번 과정을 통해 정렬을 반복합니다.
- 해당 리스트의 크기가 1보다 작을때까지 위 과정을 반복합니다.
힙 정렬 (Heap sort)
힙 정렬의 경우, 힙 트리 자료구조를 사용하여 데이터를 정렬하는 알고리즘입니다. 간단히 힙이라는 자료구조에 대해 알아보고 갈게요.
힙(heap)은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리(complete binary tree)를 기본으로 한 자료구조(tree-based structure)입니다. 항상 루트 노드에 최대값 혹은 최소값이 존재하고, 데이터를 추가하거나 삭제했을때 정렬이 빠른 장점이 있습니다.
오름차순으로 정렬이 필요하다고 가정할 때, 최대힙을 구현하면 항상 루트 노드에 최대값이 존재하기 때문에, 루트 노드의 값을 배열의 가장 마지막 부분에 저장하고 값을 고정한 이후에, 해당 노드를 제외하고 다시 최대힙으로 정렬 과정을 거치게 됩니다.
- 최대 힙으로 데이터 정렬
- 루트 노드의 값을 트리의 가장 마지막 값과 교환
- 교환한 가장 마지막 위치에 값을 저장하고 고정
- 가장 마지막 값을 제외한(n-1) 데이터를 다시 최대 힙으로 정렬
- 2~4번을 반복하여 루트 노드를 제외한 모든 값이 고정될 때까지 반복합니다.
위의 과정이 힙 정렬을 사용하여 데이터를 정렬하는 방식입니다.
힙 트리에서 데이터를 정렬하는 시간복잡도는 logn이며, 데이터를 정렬하는 과정을 n번만큼 진행하기 때문에, 시간복잡도는 O(nlong)이 됩니다.
완전이진트리 구조는 배열로 쉽게 변환이 가능하고, 정렬과정에서 새로운 배열을 사용하지 않기 때문에, 공간복잡도는 o(n)입니다.
