[자료구조] Chap10 정렬

Chap10 정렬

 

선택 정렬

• 첫번째 자리에 올 값, 두번째 자리에 올 값.. 순서로 탐색해서 발견 시 해당 위치의 값과 자리 교환
• 비교 n(n-1)/2 회
• 교환 n-1 회 
• => O(n^2)

 

버블 정렬

• 맨 첫 값부터 바로 옆 값과 비교해 교환할지 말지 결정. 끝까지 가면 마지막 값부터 정렬 완료됨. 반복
• 비교 n(n-1)/2 회
• 교환 n(n-1)/2 회 (최악 : 비교할 때마다 교환)
• => O(n^2)
• 개선 - 중간 단계에서 정렬 완료된 경우. 현 단계에서 데이터 이동이 일어나지 않으면 다음 단계들을 수행하지 않고 종료

 

삽입 정렬

• 앞에서부터 현재 값을 앞쪽이 이미 정렬되어있는 값들 사이의 알맞은 위치에 삽입함(삽입하는 과정은 현재 위치에서 바로 앞 값과 비교해서 교환 결정하며 앞쪽으로 보냄. 계속 비교 교환하는 것)
• 비교 n(n-1)/2 회
• => O(n^2)

 

합병 정렬

• 개별 숫자로 시작해 숫자를 두 묶음씩 합치며 하나의 리스트로 만들어 나감
• 비교 O(nlogn) (매 단계마다 전체로 보았을 때 항상 n번의 비교를 함. 둘씩 합치는 거니 단계를 logn번함.)
• 제자리 정렬in-place sort가 아님 : 정렬할 데이터의 크기 이외로 계산할 공간이 더 필요.

 

퀵 정렬

• 기준pivot값을 정하고 두개의 인덱스를 사용함. 
• 두 인덱스는 양쪽 끝에서 출발해, 왼쪽출발 인덱스는 pivot보다 큰 값을 만나면 멈춤. 오른쪽인덱스는 pivot보다 큰 값. 왼쪽인덱스가 오른쪽인덱스보다 작으면 두 값을 교환함. 반복. 왼쪽인덱스가 오른쪽인덱스보다 커지면 반복을 멈추고 현재의 오른쪽 인덱스 위치의 값과 pivot값을 교환함
•  -> 그럼 pivot값을 기준으로 pivot값 왼쪽엔 pivot보다 작은 값, 오른쪽엔 pivot보다 큰 값들만 위치함
• pivot값을 기준으로 양 옆 각각에 대해 위 작업을 다시 수행함
• 평균 O(nlogn), 최악 O(n^2)

 

힙 정렬

• 힙 : 부모노드의 원소값이 항상 자식보다 큰 이진트리(max heap. 반대이면 min heap)
• 힙을 구성한 후, 루트노드에 있는 값을 계속 삭제(꺼냄)하며 값을 정렬함.
• 삽입 : 마지막 level의 마지막 노드 위치에 삽입 후 힙 재구성
• 삭제 : 삭제할 노드를 마지막 level의 마지막 노드 위치 노드와 교환하고 힙 재구성, 원하는 값 삭제
• 평균, 최악 O(nlogn)
• 재구성 시간 O(h) **h는 트리의 깊이

 

정렬 요약

• 정렬에 드는 최적의 시간 : O(nlogn)