자료의 정렬 (삽입 정렬, 선택 정렬, 버블 정렬, 퀵 정렬, 이진 병합 정렬, 힙 정렬)

 

삽입 정렬

기준이 되는 키 값의 앞쪽 자료들과 비교하여 자신의 위치를 찾아 삽입하여 정렬하는 방법이다.

기준 키는 삽입 될때마다 하나씩 뒤로 해당되며 옆칸의 데이터와 비교하여 자신의 자리를 찾는다.

 

 

 

 

선택 정렬

전체 데이터를 탐색하고 최솟값을 찾아 첫번째 위치에 놓는다.

그렇게 다음 최솟값을 찾고 두번째 위치에 놓는 방법을 반복하여 정렬한다.

 

 

 

버블 정렬

인접한 데이터와 비교하여 위치가 맞지 않을 경우 서로 자리를 교환하는 방법이다.

단계 수행 중 자리 교환이 더 이상 발생하지 않으면 정렬이 완료된다.

 

 

 

 

퀵 정렬

분할 정복 알고리즘중 하나로 평균적으로 매우 빠른 속도의 정렬 시간을 자랑한다.

리스트 내의 한 요소를 피벗(pivot)이라고 잡고, 피벗보다 작은 요소는 왼쪽으로, 큰요소는 오른쪽으로 이동한다.

 

피벗을 기준으로 나누어진 요소들은 나누어진 요소 가운데 다시 피벗을 선정하고,

그것을 기준으로 다시 나눈다. 

그렇게 더이상 나눌 수 없을 때 까지 나누면 작은수부터 정렬이 된다.

 

 

 

 

이진 병합 정렬

아까의 퀵 정렬과 반대로 묶으면서 파일을 정렬하는 방법이다.

두개의 키들을 한 쌍으로 하여 각 쌍에 대하여 순서를 정하고 병합하여 최종적으로 하나의 정렬된 파일이 된다.

 

 

 

 

 

힙 정렬

완전 이진 트리를 이용한 정렬 방식으로 이진 트리를 힙 정렬로 변환하는 방법이다.

부모 노드가 아들 노드보다 큰값 (최대 힙) 이거나 작은 값 (최소 힙) 이 되도록 구성한다.

 

정렬 되지 않은 트리에서는 자식 노드 요소와 부모 노드 요소를 비교 하며 올라간다.

최소 힙일 경우에는 작을 경우 위로 올라가며 최대 힙일 경우에는 클 수록 올라간다.

위 그림과 같이 최대 힙/최소 힙이 완성되면 힙 정렬이 끝이 난다.