정렬 알고리즘 - O(logN) - 퀵 / 병합/ 힙

 

평균 수행 시간이 O(logN)인 알고리즘

• 한번 수행될 때마다 정렬되어야 하는 수의 범위가 1/2로 줄어드는 경우
• 퀵 정렬 이외의 다른 알고리즘은 추가적인 메모리가 필요함

 

 

퀵 정렬(Quick Sort), 병합 정렬(Merge Sort), 힙 정렬(Heap Sort)

 

Merge Sort

• 병합 정렬은 메모리를 가지고 있다. 처음에 엘리먼트들을 분배. 다시 병합을 하면서 처음에는 2개짜리로 2개 2개를 - 4개짜리로 4개 4개를 8개짜리로 병합하면서 정렬 

 

Heap Sort

• 실제 구현은 배열로 많이 한다. 추상적으로 나타낼 때는 밑에 이미지처럼 나타낸다.
• 가장 작은 값 맨 위로 하면 min heap <-> 반대는 max heap
• EX) 우선순위 가장 높은 애 먼저 할 때 maxheap 우선순위 해서 사용 가능
• Heap 은 complete BT이다.  - complete BinaryTree ->
• h-1까지는 fully 바이너리 트리 / 그다음 h라인에서는 왼쪽부터 채워나가는 
• minHeap에서는 parents가 자기 child 보다 무조건 작다. 옆에 애들이랑은 상관 X 

 

 

---

 

Heap Sort 구현해보기

 

 

min heap

 

 

complete BT 상태에서 추상적으로 이미지 표현 

실제로는 배열로 구현한다 

10 - 30 - 20 - 50 - 60 - 70 - 40 - 80 -ㅁ - ㅁ - ㅁ 

 

 

---

 

min Heap - 새로운 요소 7을 삽입하려고 할 경우 개념

 

 

0번 자리는 안 쓴다. - 위치 찾을 때 x2 /2 연산해야 하므로. 

 

1. 새로운 요소 7을 넣으려고 할 때 일단은 80 옆자리 ( 배열 끝 부분 size )에 들어간다고 가정 
2. 삽입하려는 요소의 부모 위치 노드와 비교 - 부모 위치 = child/2의 위치 - completeBT이기 때문에   
3. 부모인 50과 삽입하려는 7 비교 -> 50>7 -> size 자리에 부모 50 값 주고 부모 위치로 포인터 이동 후 다시 비교

 

 

9번에 들어갈까? -> 부모가 더 크다 -> 부모를 9번 자리에 주고 -> 4번 자리에 들어갈까? 하면서 4번 자리의 부모랑 비교 -> 부모인 30이 더 크니까 30을 4번 자리에 주고 -> 2번 자리에 들어갈까? 하면서 부모인 1번 자리 10과 비교 -> 10보다도 작으므로 2번 자리에 10 주고 1번 자리에 7들어갈까 비교 -> 1번 자리까지 오면 비교할 애 없음 -> 그대로 1번 자리에 입력되도록 해준다. 

 

 

 

 

---

 

minheap - 삭제할 경우의 개념 - 루트에 있는 애를 꺼낸다

 

minHeap의 경우 루트에 가장 작은애가 있다.

 

 

 

1. 루트에 있는애를 꺼내고
2. 배열 맨 마지막애(size 위치에 있는 애)를 루트 자리에 간다고 가정
3. child 위치에 있는 2개 중 더 작은 값과 부모 위치에 있는 애 비교! - 자식 위치 = parent * 2의 위치 
4. 비교해서 부모> 자식 - 자식이 더 작으면 부모 위치에 자식 값 주고 자식 위치로 포인터 이동
5. 이동한 위치가 이제 부모 위치가 되고 다시 그 위치의 자식 2개 중 더 작은 값과 부모 비교
6. 비교해서 부모 <자식 - 부모가 더 작으면 부모 위치에 복사해놓은 배열 맨 마지막이었던 size애 대입!  

 

 

10을 꺼내고 size 위치의 80 복사해 놓은 다음 - 루트 자리에 간다고 가정

자식인 30과 20중 더 작은 20과 비교 : 80>20 이므로 부모 자리에 20 주고 20이 있던 3번 자리로 포인터 이동

3번 자리의 자식인 70과 40중 더 작은 40과 비교 : 80>40 이므로 부모 3번 자리에 40을 주고 7번 자리로 이동

7번 자리의 자식들이 없다. size를 넘어간다. chile > size 일 경우 그대로 그 위치 7번 자리에 복사해놓은 80 대입

 

 

 

---

 

 

 

하나하나씩 꺼내면 작은 수부터 나옴!

 

 

 

while문의 목적은 - 복사해놓은 temp가 들어갈 위치 찾는 것! - temp는 parent자리에 들어간다.

 

1번 자리에 넣을까 하고 자식 2/3번 중에 작은 값과 비교

결국 deleteHeap() 메서드의 return 은 루프 위치에 있는 data이다.

data 꺼내지면 재 정렬하기 위해 while 문으로 temp 위치 찾아서 정렬해주는 것!

 

 

---

전체 코드  확인

 

 

HeapSort 생성

 

• HeapSort() 생성자 생성
• 추가 - insertHeap() 메서드,
• getHeapSize()  생성
• 삭제 - deleteHeap() 메서드.
• printHeap() 생성 

 

 

 

 

 

 

---

 

출력 TEST

인스턴스 생성 후 입력 / 출력 / 삭제 -- 출력 Test

 

 

 

 

 

---

 

 

review

평균 수행 시간이 - O(logN) - 퀵 정렬 / 병합 정렬 / 힙 정렬
한번 수행될 때마다 정렬되어야 하는 수의 범위가 1/2로 줄어드는 정렬
그중 Heap Sort - 힙 정렬에 대해 실습해 보았다.
추상적인 개념으로 이미지를 표현하는 법과 실제 구현하는 배열로 어떻게 이루어져 있는지를 보았다.
그다음 minHeap으로 정렬한 상태에서 요소를 추가할 경우와 삭제할 경우 개념과 방법도 실습해 보았다.

내가 생각한 중요 체크 포인트는
부모와 자식 -  추상적 위치와 실제 배열의 위치에 대한 이해 
삽입할 때 - 부모와 비교, 부모 위치 찾기
삭제할 때 - size 위치에 있는 애 루트로 간다고 가정 , 자식 2개 중 더 작은 값과 비교 후 재정렬,
결국 반환 값은 루트에 있는 애

정렬에 대해 배워보았는데 여러 가지 상황이 많은 만큼 정렬의 방법도 다양한 것 같다.
정렬의 개념뿐 아니라 어느 상황에 사용하면 효율적 인지도 체크해 놓아야 되겠다.
나머지 퀵 정렬과 병합 정렬에 관한 개념과 알고리즘 문제도 찾아서 실습해봐야겠다.