README.md

정렬 알고리즘 (Sorting Algorithms)

정렬(Sorting) 📶
컬렉션(e.g. an array)의 항목을 재배열하는 과정

정렬 알고리즘의 종류

1. 선택 정렬(Selection Sort)
2. 삽입 정렬(Insertion Sort)
3. 퀵 정렬(Quick Sort)
4. 합병 정렬(Merge Sort)
5. 힙 정렬(Heap Sort)
6. 기수 정렬(Redix Sort (LSD))
7. 기수 정렬(Redix Sort (MSD))
8. std::sort (gcc)
9. std::stable_sort (gcc)
10. 셸 정렬(Shell Sort)
11. 버블 정렬(Bubble Sort)
12. 칵테일 정렬(Cocktail Shaker Sort)
13. 난쟁이 정렬(Gnome Sort)
14. 바이토닉 정렬(Bitonic Sort)
15. 보고 정렬(Bogo Sort)

치트 시트(Cheat Sheet)

Algorithm	👍 Best	Avg	👎 Worst	Space Complexity	stable	in-place
선택 정렬(Selection Sort)	O($n^2$)	O($n^2$)	O($n^2$)	O(1)		✅
삽입 정렬(Insertion Sort)	O($n$)	O($n^2$)	O($n^2$)	O(1)	✅	✅
퀵 정렬(Quick Sort)	O($n\,log\,n$)	O($n\,log\,n$)	O($n^2$)	O($log\,n$)		✅
합병 정렬(Merge Sort)	O($n\,log\,n$)	O($n\,log\,n$)	O($n\,log\,n$)	O($n$)	✅
힙 정렬(Heap Sort)	O($n\,log\,n$)	O($n\,log\,n$)	O($n\,log\,n$)	O(1)		✅
기수 정렬(Redix Sort (LSD))
기수 정렬(Redix Sort (MSD))
std::sort (gcc)
std::stable_sort (gcc)
셸 정렬(Shell Sort)
버블 정렬(Bubble Sort)	O($n$)	O($n^2$)	O($n^2$)	O(1)	✅	✅
칵테일 정렬(Cocktail Shaker Sort)
난쟁이 정렬(Gnome Sort)
바이토닉 정렬(Bitonic Sort)
보고 정렬(Bogo Sort)

Array.prototype.sort()에 대해

Point 1. 브라우저마다 구현된 알고리즘은 다를 수 있다.

ECMAScript 명세에서는 Array.prototype.sort() 매서드에 대해 특정한 정렬 알고리즘에 대한 요구사항을 명시적으로 제공하지 않는다. 브라우저마다 구현된 알고리즘은 다를 수 있다.

Point 2. compareFn 생략 시, 문자열 변환 과정을 거쳐 유니 코드 코드 포인트 값에 따라 정렬된다.

자바스크립트의 내장 정렬 메서드 sort 사용 시 옵셔널 compareFn을 생략하게 되면, 배열의 모든 항목이 문자열로 변환되고 각 문자의 유니 코드 코드 포인트 값에 따라 정렬된다.

Point 3. 원본 배열이 변경된다. ^in-place

Array.prototype.sort() 매서드는 원본 배열을 직접 변경하도록 설계되었다.

---

References

15 Sorting Algorithms in 6 Minutes
Sorting Algorithms Animations
VisuAlgo - Sorting

Udemy - JavaScript Algorithms and Data Structures Masterclass