38. 정렬(A)

삽입 정렬

• n번째 키 를 앞의 n-1개의 키와 비교하여 알맞은 순서에 삽입하여 정렬
• 시간 복잡도 : O(n²)

 

쉘 정렬

• 입력 파일을 어떤 매개변수(h)의 값으로 서브파일을 구성, 임의의 레코드 키와 h값만큼 떨어진 곳의 레코드 키를 비교하여 순서화되어 있지 않으면 서로 교환하는 것을 반복하는 정렬 방식
• 시간 복잡도 : O(n^1.5), 최악 : O(n²)

 

선택 정렬

• n개의 레코드 중에서 최소값을 찾아 첫 번째 레코드 위치에 놓고, 나머지 (n-1)개 중에서 다시 최소값을 찾아 두번째 레코드 위치에 놓는 방식
• 시간 복잡도 : O(n²)

 

버블 정렬

• 주어진 파일에서 인접한 두 개의 레코드 키 값을 비교하여 그 크기에 따라 레코드 위치를 서로 교환하는 정렬 방식
• 시간 복잡도 : O(n²)

 

퀵 정렬

• 레코드의 많은 자료 이동을 없애고 하나의 파일을 부분적으로 나누어 정렬, 분할과 정복 이용, 정렬중에 젤 빠름 \
• 평균 수행 시간 복잡도 : O(nlog2n), 최악 시간 복잡도 : O(n²)

 

힙 정렬

• 전이진 트리를 이용한 정렬 방식
• 수행 시간 복잡도 : O(nlog2n)

 

2-Way 합병 정렬

• 이미 정렬되어 있는 두 개의 파일을 한 개의 파일로 합병하는 정렬 방식
• 2개씩 한 쌍으로 하여 묶고 각 쌍에 대하여 순서를 정한다
• 수행 시간 복잡도 : O(nlog2n)

 

기수 정렬

• Queue를 이용하여 자릿수를 정렬하는 방식
• 수행 시간 복잡도 : O(dn)