정렬

정렬

• 정렬 알고리즘 선택 시 고려사항 : 데이터의 양, 초기 데이터의 배열 상태, 키 값들의 분포 상태, 사용 컴퓨터 시스템의 특성
• 종류 : 내부 정렬, 외부 정렬

내부 정렬

삽입 정렬(Insertion Sort)

• 정렬된 파일에 새로운 하나의 레코드를 순서에 따라 삽입시켜 정렬하는 방법
• 최상, 최악, 평균 시간 복잡도 : O($n^2$)

예제

아래 배열의 값을 삽입 정렬을 이용하여 오름차순 정렬하시오.

1. ⓐ 두 번째 배열 값을 키값으로 지정하고 ⓑ 키값과 키값의 앞 배열의 값을 비교하여 키값보다 값이 크면 값을 ⓒ 한 칸 뒤로 밀어주고 뒤로 밀린 배열의 자리에 키값을 삽입함

2. 다음으로 3번째 배열 값을 키값으로 지정하고 앞의 단계를 반복함. 이번 단계에서는 키갑 앞의 값이 키값보다 작으므로 이동이 발생하지 않음

3. 다음으로 3번째 배열 값을 키값으로 지정하고 앞의 단계를 반복함

4. 계속 4, 5, 6번째 배열을 키값으로 지정하고 앞의 단계를 반복함

 

 

버블 정렬(Bubble Sort)

• 인접한 데이터를 비교하면서 그 크기에 따라 데이터의 위치를 바꾸어 정렬하는 방법
• 최상, 최악, 평균 시간 복잡도 : O($n^2$)

예제

아래 배열의 값을 버블 정렬을 이용하여 오름차순 정렬하시오.

1. 첫 번째 배열부터 인접한 1, 2번 배열의 크기를 비교하여 작은 값이 앞으로 위치하도록 교환함

2. 인접한 2, 3번 배열의 크기를 비교하여 작은 값이 앞으로 위치하도록 치환함

3. 인접한 3, 4번 배열의 크기를 비교하여 작은 값이 앞으로 위치하도록 치환함

4. 배열 뒤쪽까지 앞의 방식으로 반복함. 1회전 완료 시 가장 큰 값이 마지막에 배치됨

 

 

선택 정렬(Selection Sort)

• n개의 레코드 중에서 최소값(또는 최대값)을 찾아 1st 레코드 위치에 놓고, 나머지 (n-1) 개의 레코드 중에서 최소값(또는 최대값)을 찾아 2nd 레코드 위치에 놓는 방법을 반복하여 정렬하는 방법
• 최상, 최악, 평균 시간 복잡도 : O($n^2$)

예제

아래 배열의 값을 버블 정렬을 이용하여 오름차순 정렬하시오.

1. 첫 번째 값을 기준값으로 선택하고 기준값 뒤의 값과 하나씩 비교하여 기준값보다 값이 작은 배열의 값과 교환함

2. 다음으로 2번 배열을 기준값으로 지정하여 앞의 단계를 반복함

3. 선택 정렬은 버블 정렬과 다르게 1회전 시 가장 작은 값이 가장 앞에 배치됨

 

 

병합(합병) 정렬(2 - Way Merge Sort)

• 두 개의 키들을 한 쌍으로 하여 각 쌍에 대해 순서를 정함
• 순서대로 정렬된 각 쌍의 키들을 합병하여 하나의 정렬된 서브 리스트로 만듦
• 최상, 최악, 평균 시간 복잡도 : O($nlog_2n$)

 

퀵 정렬(Quick Sort)

• 레코드의 많은 자료 이동을 없애고 하나의 파일을 부분적으로 나누어가면서 정렬하는 방법으로 키를 기준으로 작은 값은 왼쪽에 큰 값은 오른쪽에 모이도록 서로 교환시키는 부분 교환 정렬법
• 최상, 평균 시간 복잡도 : O($nlog_2n$)
• 피벗(Pivot)을 사용하며 최악의 경우 : (n(n-1))/2

 

힙 정렬(Heap Sort)

• 완전이진 트리를 이용하여 정렬하는 방법
• 정렬한 입력 레코들로 힙을 구성하고 가장 큰 키값을 갖는 루트 노드를 제거하는 과정을 반복하여 정렬하는 기법
• 입력 자료의 레코드를 완전 이진 트리(Complete Binary Tree)로 구성함
• 최상, 최악, 평균 시간 복잡도 : O($nlog_2n$)