알고리즘 기초 - 정렬 알고리즘
정렬
이진 탐색은 알고리즘을 수행하기 전에 데이터를 비교하도록 특정 순서로 배열을 정렬한다. 데이터베이스는 쿼리를 실행하여 특정 속성에 따라 배열을 정렬한다.
데이터를 정렬하면 알고리즘이 중복 데이터를 빠르게 식별하거나 필요한 데이터를 매우 빠르게 찾을 수 있다.
버블 정렬(Bubble Sort)
1. 배열의 왼쪽 끝에 있는 두 요소(숫자)를 확인한다.
2. 두 요소를 비교하여 오른쪽이 왼쪽보다 크면 두 요소의 위치를 바꾼다.
3. 원래 자리에서 오른쪽으로 한 자리 이동하여 두 요소를 비교한다.
4. 두 요소를 비교하여 오른쪽이 왼쪽보다 크면 두 요소의 위치를 바꾼다.
반복하여 결국 배열에서 가장 큰 숫자가 배열의 가장 오른쪽으로 이동하면
해당 요소는 정렬이 완료된 것으로 간주한다.
배열의 요소가 모두 정렬될 때까지 과정을 반복한다.
버블 정렬은 시간 복잡도가 O(n²)으로 비효율적인 알고리즘이다. 단순하지만 느리기 때문에 실제로 응용 프로그램에 적용하기에는 적합하지 않다.
선택 정렬(Selection Sort)
선택 정렬은 선형 탐색을 응용한 알고리즘이다.
1. 선형 탐색을 사용하여 배열에서 가장 작은 요소를 찾는다.
2. 찾아낸 요소와 가장 왼쪽 요소의 위치를 바꾼다.
자리가 바뀐 요소는 정렬이 완료된 것으로 간주한다.
배열의 요소가 모두 정렬될 때까지 과정을 반복한다.
선택 정렬은 반복문 2개를 중첩하여 구현하므로 시간 복잡도가 O(n²)이다. 또한 배열에서 가장 작은 요소를 찾기 위해 선형 탐색을 사용하기 때문에 입력 데이터 개수가 증가할수록 실행 속도는 느려진다.
선택 정렬은 요소의 개수가 작은 배열에서는 잘 작동하지만, 요소의 개수가 많은 배열에서는 버블 정렬보다 조금 더 나은 성능을 제공할 뿐이다.
삽입 정렬(Insertion Sort)
1. 왼쪽 끝에서 두 번째에 있는 요소부터 앞(왼쪽)의 요소들과 비교한다.
2. 비교한 요소가 더 작다면 두 요소의 위치를 바꾼다.
3. 다음 요소가 더 크다면 위치를 바꾸지 않는다.
4. 계속해서 다음으로 넘어가며 차례대로 비교한다.
배열의 요소가 모두 정렬될 때까지 과정을 반복한다.
삽입 정렬에서는 선택 정렬처럼 가장 작은 숫자를 찾기 위해 배열의 모든 숫자를 확인할 필요가 없다. 다만 이웃한 위치로만 이동하기 때문에 삽입 정렬의 시간 복잡도는 최악의 경우 O(n²)이며, 선택 정렬보다 더 효율적이다.
셀 정렬(Shell Sort)
삽입 정렬을 더 효율적으로 실행하는 알고리즘이다.
1. 요소를 몇 개 단위로 묶은 후 단위마다 삽입 정렬을 실행한다.
2. 이후 단위 요소 수를 줄여 묶은 후 삽입 정렬을 실행한다.
3. 단위 요소 수가 1이 될 때까지 실행하면 정렬이 완료된다.
ex)
11개짜리 배열을 단위 요소 수 5로 묶어 5 / 5 / 1 로 나눈다.
각 단위마다 삽입 정렬을 실행한다.
각 부분 삽입 정렬이 완료되어 일부 정렬된 배열을 단위 요소 수를 3으로 줄여 다시 3 / 3 / 3 / 1 / 1 로 나눈다.
각 단위마다 다시 삽입 정렬을 실행한다.
단위 요소 수가 1이 될 때까지 실행하면 정렬이 완료된다.
단위 요소 수마다 조금씩 요소를 정렬하므로 최종 단위 요소 수가 1일 때는 기존 삽입 정렬보다 위치를 바꾸는 일이 훨씬 적다. 셀 정렬의 시간 복잡도는 평균 O(n¹∙⁵), 최악 O(n²)이므로 평균적으로 삽입 정렬보다 우수하다.
병합 정렬(Merge Sort)
데이터를 반으로 나누어 정렬을 수행하는 분할 정복(Divide and Conquer) 방식 알고리즘이다.
1. 배열을 더 이상 나눌 수 없을 때까지 반으로 나눈다.
(나눠진 모든 배열에 하나의 요소만 있을 때까지)
2. 두 배열씩 결합하며 정렬한다.
3. 다음 배열과 결합을 반복하며 점점 배열의 크기를 늘려나간다.
4. 반복하면 결국 완전히 정렬된 하나의 배열을 얻는다.
병합 정렬은 배열을 나눌 수 없을 때까지 반으로 나눈 다음, 요소를 정렬하며 더 결합할 수 있는 배열이 없을 때까지 결합하는 알고리즘이다. 흔히 재귀 함수를 사용하여 데이터를 나누므로 시간 복잡도가 재귀 횟수에 따라 달라지며, 일반적인 시간 복잡도는 O(nlogn)이다.
퀵 정렬(Quick Sort)
병합 정렬과 마찬가지로 분할 정복 방식의 알고리즘이다.
1. 배열에서 끝에서 마커 이동의 기준이 될 피벗(Pivot)을 정한다.
2. 피벗의 바로 옆과 반대쪽 끝 요소를 각각 마커로 정한다.
3. 왼쪽 마커는 오른쪽으로 하나씩 이동하며 피벗과 같거나 큰 요소를 찾는다.
오른쪽 마커는 왼쪽으로 하나씩 이동하며 피벗과 같거나 작은 요소를 찾는다.
4. 마커는 이동하며 처음으로 발견한 적합한 요소들을 선택한다.
5. 각 마커가 요소를 선택하고 나면 두 요소의 위치를 바꾼다.
6. 반복하다 두 마커가 서로 교차하는 상태가 되면 오른쪽 마커와 피벗의 위치를 바꾼다.
위치가 옮겨진 피벗이었던 요소는 정렬이 완료된 것으로 간주한다.
마커를 사용하여 위치를 바꾸는 동작을 반복하다 보면 피벗보다 작은 숫자는 배열의 왼쪽에, 피벗보다 큰 숫자는 배열의 오른쪽에 모이게 된다. 나뉜 두 부분마다 과정을 반복하면 정렬이 완료된다.
퀵 정렬은 피벗을 기준으로 왼쪽에는 피벗보다 작은 숫자, 오른쪽에는 피벗보다 큰 숫자로 배열이 정렬되면 이를 반씩 나눈다. 그리고 먼저 피벗의 왼쪽 배열에 대해 같은 동작을 수행한 후, 처음 피벗으로 나뉜 오른쪽 배열에 대해서도 같은 동작을 수행한다. 배열이 완전히 정렬될 때까지 배열을 작게 나눠가며 반복한다.
힙 정렬(Heap Sort)
힙 정렬은 힙 데이터 구조의 각 노드를 최대 힙 또는 최소 힙 상태로 정렬하는 방법이다.
최대 힙 정렬을 하는 경우
1. 최대 값을 가진 노드를 바로 위 부모 노드와 비교한다.
2. 비교한 부모 노드가 값이 더 작다면 두 노드의 위치를 바꾼다. 같거나 작다면 그대로 둔다.
3. 과정을 반복하다 루트 노드를 만나면 값을 비교하고 루트 노드에도 똑같이 적용한다.
4. 루트 노드와 비교가 끝나면 다음으로 큰 값을 찾아 1번부터 다시 반복한다.
모든 노드가 정렬 될때까지 반복한다.
최소 힙 정렬을 하는 경우에는 최대 힙 정렬과 반대로 적용한다.
자식 노드와 부모 노드의 값을 비교해서 더 작은 쪽을 루트 노드에 가깝도록 위치시킨다.
힙 정렬은 전체 값을 대상으로 비교해 정렬하는 것이 아닌, 가장 크거나 작은 값 기준으로 바로 이웃한 부모 및 자식 노드를 상대 비교하기 때문에 시간 복잡도가 최선, 평균, 최악에 상관없이 항상 O(nlogn)을 유지한다.
버킷 정렬(Bucket Sort)
요소들을 어떤 기준이 있는 버킷(여러 데이터를 저장하는 장소)에 나눠 넣은 후 다음 과정으로 정렬을 수행한다.
1. 어떤 순서가 있는 버킷으로 사용할 기억 공간(보통 배열이나 리스트)을 준비한다.
2. 버킷을 만들 때의 기준에 따라 요소를 분류해 넣는다.
3. 버킷별로 요소를 정렬한다.
4. 버킷 안에서 정렬한 요소를 버킷의 순서에 따라 나열해서 정렬을 완료한다.
ex) 10진수 자릿수(0~9 / 10~99 / 100~999)로 버킷을 만들어 그에 해당하는 요소를 나눠 넣은 후 버킷 안에서 정렬하여
정렬 처리 속도를 높인다.
버킷 정렬의 시간 복잡도는 보통 버킷 내에서 요소를 정렬할 때의 시간 복잡도를 따른다. 10진수 자릿수 같은 경우 보통 삽입 정렬을 사용하므로 최악의 경우는 O(n²)이다. 평균은 O(n + n² / m + m)(이때 m은 버킷 수)이다.
기수 정렬(Radix Sort)
버킷 정렬과 기본 원리는 같지만 특정한 기준이 정해져있다. 요솟값의 특정 자릿수끼리 비교해서 정렬한다.
1. 0~9까지의 버킷을 만든다.
버킷 (0 / 1 / 2 / 3 / 4 / 5 / 6 / 7 / 8 / 9), 배열 [1, 1431, 15, 25703, 171, 45, 263, 55, 553, 1430, 34762]
2. 1의 자릿수를 기준으로 해당 숫자의 버킷 내에 요소를 나눈다.
(0 / 1 / 2 / 3 / 4 / 5 / 6 / 7 / 8 / 9)
1430 / 1, 1431, 171 / 34762 / 25703, 263 . . .
2. 10의 자릿수를 기준으로 버킷 내의 요소를 다시 나눈다.
자릿수가 부족하다면 그 앞이 0이라고 간주한다.
01, 25703 / 15 / / 1430, 1431 / 45 / 55, 553 . . .
3. 100의 자릿수를 기준으로 버킷 내의 요소를 다시 나눈다.
자릿수가 부족하다면 그 앞이 0으로 간주한다.
001, 015, 045, 055 / 171 / 263 / / 1430, 1431 . . .
4. 계속 요소를 나누다보면 결국 순서대로 정렬하게 된다.
기수 정렬의 시간 복잡도는 최악의 경우 O(mn)(m은 요소의 자릿수)이다.