일반적으로 정렬은 가지고 있는 Data 를 Ascending 오름차 순으로 or
Descending 내림차순으로 가지고 있는 data list를 순서를 변경하는 것이다.
이를 한정적으로 숫자에 그리고, 적용범위를 위와 같이 한정짓으면 위와 같이 되겠지만,
적용범위를 넓히면 다양하게 Sorting을 할 수도 있겠다.
일단 목적이 기본적으로 Sorting Algorithm 학습이기에 알아둬야 할 기본 용어 부터 알아보자.
- ascending sort or ascending order (오름차순 정렬 ): 1,2,3,4
- descending sort or descending order (내림차순 정렬): 4,3,2,1
2. 정렬 (Sorting Algorithm ) 비교 및 pseudo code
일반적으로 많이 사용되는 정렬 알고리즘이며 pseudo code 이들을 간단히 살펴보자.
- bubble sort: https://www.toptal.com/developers/sorting-algorithms/bubble-sort
- insertion sort: https://www.toptal.com/developers/sorting-algorithms/insertion-sort
- selection sort: https://www.toptal.com/developers/sorting-algorithms/selection-sort
- shell sort: https://www.toptal.com/developers/sorting-algorithms/shell-sort
- quick sort: https://www.toptal.com/developers/sorting-algorithms/quick-sort
- quick3 sort: https://www.toptal.com/developers/sorting-algorithms/quick-sort-3-way
- merge sort: https://www.toptal.com/developers/sorting-algorithms/merge-sort
- heap sort : https://www.toptal.com/developers/sorting-algorithms/heap-sort
이외에도 다른 많은 Sorting Algorithm 이 존재하며 이를 다 알기가 힘들어서 여기서 다루지는 않겠다.
- 상위 정렬들의 Working Time 비교분석
https://www.toptal.com/developers/sorting-algorithms/
3. 정렬 알고리즘 기본학습
기본적인 Sort만 다루겠지만, Heap sort는 priority Queue 함께 다루겠다.
3.1 기본적으올 알아둬야 할 정렬 알고리즘
- Bubble Sort
- Insertion Sort
https://ko.wikipedia.org/wiki/%EC%82%BD%EC%9E%85_%EC%A0%95%EB%A0%AC
버블정렬은 알 것이지만, Insertion Sort는 한번 살펴보자.
https://www.tutorialspoint.com/data_structures_algorithms/bubble_sort_algorithm.htm
https://www.tutorialspoint.com/data_structures_algorithms/insertion_sort_algorithm.htm
3.2 대표적으로 좋은 성능 내주는 정렬 알고리즘
- Quick Sort
- Merge Sort
divide하는 방식은 같지만, conquer의 역할이 다를 뿐이다.
Quick는 divide 다 한 후, 교환하는 방식으로 간다고 정렬하지만,
Merge는 divide 다 한 후, 별도의 Memory 공간에 이 정렬되는 과정을 넣어 이것을 정렬한다.
이 둘의 차이는 Memory의 사용량의 차이
https://www.tutorialspoint.com/data_structures_algorithms/quick_sort_algorithm.htm
https://www.tutorialspoint.com/data_structures_algorithms/merge_sort_algorithm.htm
A. Quick Sort
- data array 중 한 data를 선택하여 이를 Pivot하고 기준으로 정한다.
- Partitioning은 이는 array를 다시 순서를 맞추는 작업이다.
- Partitioning에서 얻은 큰 값을 기준으로 sub-array 작업을 반복적으로 한다.
Partitioning
왼쪽에서 pivot 위치까지 pivot 보다 작은 데이타 위치를 찾는다.
오른쪽에서 pivot 위치까지 pivot 보다 큰 데이타 위치를 찾는다.
https://en.wikipedia.org/wiki/Quicksort
https://ko.wikipedia.org/wiki/%ED%80%B5_%EC%A0%95%EB%A0%AC
http://www.cquestions.com/2008/01/c-program-for-quick-sort.html
아래의 소스는 Quick sort C로 구현을 해본것이다.
B. Merge sort
https://en.wikipedia.org/wiki/Merge_sort
https://ko.wikipedia.org/wiki/%ED%95%A9%EB%B3%91_%EC%A0%95%EB%A0%AC
- Merge sort examples
https://www.tutorialspoint.com/data_structures_algorithms/merge_sort_program_in_c.htm
http://yujuwon.tistory.com/entry/%EB%B3%91%ED%95%A9%EC%A0%95%EB%A0%ACMerge-Sort
http://nukestorm.tistory.com/54