[정처기] 데이터 입출력 구현_정렬

삽입 정렬

이미 순서화된 파일에 새로운 하나의 레코드를 순서에 맞게 삽입시켜 정렬하는 방식

평균, 최악 시간 복잡도 : O(n^2)

선택 정렬

최소값을 찾아 첫 번째 레코드 위치에 놓고, 나머지 (n-1)개 중에서 다시 최소값을 찾아 두 번째 레코드 위치에 놓는 방식을 반복하여 정렬하는 방식

평균, 최악 시간 복잡도 : O(n^2)

버블 정렬

인접한 두 개의 레코드 키 값을 비교하여 그 크기에 따라 레코드 위치를 서로 교환하는 정렬 방식

평균, 최악 시간 복잡도 : O(n^2)

쉘 정렬

어떤 매개변수의 값으로 서브파일을 구성하고, 각 서브파일을 Insertion 정렬 방식으로 순서 배열하는 과정을 반복하는 정렬방식

삽입 정렬의 확장된 개념

평균 시간 복잡도 : O(n^1.5)

최악 시간 복잡도 : O(n^2)

퀵 정렬 

키를 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽 서브 파일에 분해시키는 과정을 반복하는 정렬 방식

레코드의 많은 자료 이동을 없애고 하나의 파일을 부분적으로 나누어 가면서 정렬한다

평균 시간 복잡도 : O(n log n)

최악 시간 복잡도 : O(n^2)

힙 정렬

전이진 트리를 이용한 정렬 방식

구성된 전이진 트리(Complete Binary Tree)를 Heap Tree로 변환하여 정렬한다

평균, 최악 시간 복잡도 : O(n log n)

2-Way 합병 정렬

이미 정렬되어 있는 두 개의 파일을 한 개의 파일로 합병하는 정렬 방식

평균, 최악 시간 복잡도 : O(n log n)

기수 정렬 = Bucket Sort

큐를 이용하여 자릿수(Digit) 별로 정렬하는 방식

평균, 최악 시간 복잡도 : O(dn)