버블 정렬, 합병 정렬, 퀵 정렬
버블 정렬(Bubble sort)
버블 정렬은 가장 간단한 정렬 알고리즘입니다. 이 알고리즘은 n의 크기를 가진 배열을 두 개의 중첩된 for문을 이용해서 정렬을 합니다.
버블 정렬은 바로 뒤의 자료와 비교를 통해서 정렬을 진행하는데 1회 실행하면 배열에서 가장 큰 자료가 맨 뒤로 이동하게 됩니다.
원래 배열 [ 1, 3, 8, 2, 9, 2, 5, 6];
for문 안의 첫 번째 for문 1회 실행 후 -> [ 1, 3, 2, 8, 2, 5, 6, 9];
for문 안의 첫 번째 for문 2회 실행 후 -> [ 1, 2, 3, 2, 5, 6, 8, 9];
2회 실행 후에는 배열에서 두 번째 큰 자료가 뒤에서 두번째 공간에 들어가게 됩니다.
이러한 방식으로 n번을 실행하면 -> [ 1, 2, 2, 3, 5, 6, 8, 9];
자료의 크기대로 정렬이 됩니다. 시간복잡도는 for문을 각각 n번과 n -1번 돌려서 n²-n 번 즉, O(n²)입니다.
병합 정렬(Merge sort)
병합 정렬은 재귀를 이용해서 배열을 정렬합니다. 정렬 방식은 다음과 같은 방식으로 이루어집니다.
병합정렬은 배열을 가운데 인덱스 기준으로 계속 분할해서 배열의 요소가 하나가 될 때까지 나눈 다음(분할과정), 양쪽의 배열을 비교하면서 작은 요소부터 합쳐서 정렬을 완성해 갑니다.(결합과정) 분할하고 결합하는 과정은 재귀를 통해서 구현합니다.
mergeSort 함수
mergeSort 함수는 Math.floor((start + end)/2); 로 가운데 인덱스를 구한 다음 mergeSort(arr, start, mid) 와 mergeSort(arr, mid + 1, end) 를 실행합니다.(재귀입니다.) 이 과정은 배열 요소가 하나까지 나누어질 때까지 계속 실행되어 분할과정이 이루어지도록 합니다.
merging 함수
merging 함수는 결합 과정을 담당하는 함수입니다. 정렬된 두 배열을 비교를 통해서 작은 요소부터 새로운 배열에 넣어서 정렬을 완성합니다.
병합 정렬이 효율적인 이유는 버블 정렬와 비교해서 n번 부분배열을 정렬하는 것이 아니라 정렬 함수를 실행할 때마다 절반씩 비교 대상을 줄이기 때문입니다. (버블 정렬이 이 단계에서 O(n)이라면 병합정렬은 O(log n)입니다.) 재귀를 호출하는 부분은 버블정렬과 달리 시간복잡도가 O(log n)이고 각 단계를 실행하는 부분은 버블 정렬과 마찬가지로 O(n)이 걸립니다. 따라서 병합 정렬의 총 시간복잡도는 O(n log n)입니다. 버블정렬의 시간복잡도가 O(n)인거 비교하면 굉장히 빠른 정렬입니다.
퀵 정렬(Quick sort)
퀵정렬은 정렬 알고리즘 중에 가장 빠른 알고리즘으로 피벗을 활용해서 정렬을 합니다.
quickSort 함수
quickSort 함수는 재귀를 타면서 배열의 제일 첫번째 요소를 피벗으로 설정하고 getLeft 함수와 getRight 함수를 활용해 정렬을 합니다.
getLeft 함수
getLeft 함수는 매개변수로 받은 피벗을 활용해 피벗보다 작거나 같은 배열의 요소들을 임시 배열(left)에 넣어주고 임시 배열(left)의 크기를 리턴합니다.
getRight 함수
getRight 함수는 매개변수로 받은 피벗을 활용해 피벗보다 큰 배열의 요소들을 임시 배열(right)에 넣어주고 임시 배열(right)의 크기를 리턴합니다.
퀵 정렬 알고리즘의 장점
- 속도가 가장 빠릅니다. 시간복잡도가 O(n log n)이지만 같은 시간복잡도를 가진 다른 정렬 알고리즘보다 빠릅니다.
- 추가로 메모리 공간을 필요로 하지 않습니다.
