Sort 정리!!

정렬 알고리즘에는,  reference : 정렬알고리즘(sorting algorithm) 정리

	시간복잡도(best / worst)
- Select(선택)  현재 위치에 들어갈 값을 찾아 정렬하는 배열이다. (최솟값을 찾아 앞부터 채워준다.)	O(n^2 / n^2)
- Insert(삽입)  현재 위치에서, 그 이하의 배열들을 비교하여 자신이 들어갈 위치를 찾아, 그 위치에 삽입하는 배열 알고리즘이다.(뒤로가면 앞의 값과 비교해서 값을 삽입해 줌)	O(n / n^2)
- Bubble(버블)  매번 연속된 두개 인덱스를 비교하여, 정한 기준의 값을 뒤로 넘겨 정렬하는 방법이다. (뒤부터 쌓는다 최대값을)	O(n / n^2)
- Merge(합병)  합병 정렬은 분할 정복(Divide and conquer) 방식으로 설계된 알고리즘이다. (분할 정복은 큰 문제를 반으로 쪼개 문제를 해결해 나가는 방식) 분할은 배열의 크기가 1보다 작거나 같을 때 까지 반복한다. 입력으로 하나의 배열을 받고, 연산 중에 두개의 배열로 계속 쪼게 나간 뒤, 합치면서 정렬해 최후에는 하나의 정렬을 추력한다.	O(n log n / n log n)
- Quick(퀵)   퀵 정렬 또한 분한 정복(Divide and conquer)을 이용하여 정렬을 수행하는 알고리즘이다. pivot point라고 기준이 되는 값을 하나 설정 하는데, 이 값을 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽으로 옮기는 방식으로 정렬을 진행한다. 이를 반복하여 분할된 배열의 크기가 1이 되면 배열이 모두 정렬 된 것이다.	O(n log n / n log n / n^2)
- Heap(힙)  최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법으로서, 내림차순 정렬을 위해서는 최소 힙을 구성하고 오름차순 정렬을 위해서는 최대 힙을 구성하면 된다. 최대 힙을 구성하여 정렬하는 방법은 아래 예와 같다.   1. n개의 노드에 대한 완전 이진 트리를 구성한다. 이때 루트 노드부터 부노드, 왼쪽 자노드, 오른쪽 자노드 순으로 구성한다.    2. 최대 힙을 구성한다. 최대 힙이란 부노드가 지노드보다 큰 트리를 말하는데, 단말 노드를 자노드로 가진 부노드부터 구성하며 아래부터 루트까지 올라오며 순차적으로 만들어 갈 수 있다.   3. 가장 큰 수(루트에 위치)를 가장 작은 수와 교환한다.   4. 2와 3을 반복한다.  reference : http://www.bogotobogo.com/Algorithms/heapsort.php	O(n log n)
- Shell(쉘)  가장 오래된 정렬 알고르짐의 하나이다. 쉘 정렬은 개념을 이해하고 구현하기는 쉬우나 시간복잡도 분석은 조금 복잡하다. 쉘 정렬은 주어진 자료 리스트를 특정 매개변수 값의 길이를 갖는 부파일(subfile)로 쪼개서, 각 부파일에서 정렬을 수행한다. 즉, 매개변수 값에 따라 부파일이 발생하며, 매개변수값을 줄이며 이 과정을 반복하고 결국 매개변수 값이 1이면 정렬은 완성된다. - 쉘 정렬은 다음과 같은 과정으로 나눈다.   1. 데이터를 십수개 정도 듬성듬성 나누어서 삽입 정렬한다.   2. 데이터를 다시 잘게 나누어서 삽입 정렬한다,   3. 이렇게 계속 하여 마침내 정렬이 된다.	O(n log n)