코딩 인터뷰 정복하기 3,4,5,6,7강
각종 정렬 알고리즘의 원리를 이해하고 암기하자.
4강. 선택정렬 (Selection Sort)
O(n^2) Minimum value라는 공간 필요. 포인트를 첫 번쨰수로 공간에 가장 작은 수를 찾고. 그 수를 찾았으면 첫 번째 포인트에 적힌 수와 그 수를 바꿔준다. 그 뒤 포인트를 2번째로 옮긴다. 1과 마찬가지 작업 수행 https://github.com/minsuk-heo/problemsolving/blob/master/sort/SelectionSort.py
5강 삽입 정렬
첫 번째 아이템. 정렬된 리스트에 넣는다. 두 번쨰 아이템.리스트의 마지막에 있는 정렬된 아이템보다 크면 넣고 아니면 swap한다. 그 과정을 리스트에 아이템을 넣을 때마다 아이템을 다 비교한다. 4 6 1 3 5 2 똑같이 4 6 1 3 5 2 그 다음에 교환 4 1 6 3 5 2 근데 또 작으니까 또 정렬 1 4 6 3 5 2 ….
https://github.com/minsuk-heo/problemsolving/blob/master/sort/InsertionSort.py
6강 병합정렬 (merge sort )
performance : O(n logn) space complexity: O(n) 2단계로 구성된다.
- 정렬되지 않은 리스트를 계속 반으로 쪼갠다. (하나의 아이템이 나올 때 까지) -> 쪼갤 때 log n의 시간 복잡도
- 비교를 해서 다시 정렬이 되도록 병합을 시킨다. -> 병합할 때 -> n의 시간 복잡도 따라서 n * log n
https://github.com/minsuk-heo/problemsolving/blob/master/sort/MergeSort.py
7강 퀵 정렬(quick sort)
performance : O(n logn). worst case O(n^2) ; 리스트가 이미 정렬되어 있는 상태에서 실행했을 경우 space complexity: O(n) : 따로 메모리 사용하지 않고 현재 있는 그 메모리 안에서 모든 것을 정렬.
- 피봇을 하나 정한다. wall이 필요하다.
- 피봇 보다 작은 아이템은 wall의 왼쪽에, 피봇보다 큰 아이템은 wall의 오른쪽 세워 넣어야 한다. (만약 피봇보다 작은 아이템 발견시 벽의 가장 오른쪽에 있는 수와 해당 아이템을 swap 해준다. 그 뒤 wall을 한칸 오른쪽으로 이동.)
- 현재 있던 피봇의 모든 순회가 끝나면 피봇으로 사용했던 수를 벽의 오른쪽으로 옮긴다. (swap)
- 똑같은 방식으로 벽의 왼쪽을 퀵소트로, 벽의 오른쪽도 퀵소트로 -> 즉 리커시브 알고리즘 https://github.com/minsuk-heo/problemsolving/blob/master/sort/QuickSort.py
참고자료
허민석님 깃헙 블로그 https://github.com/minsuk-heo/problemsolving