데이터 구조 16 ( Selection , Quick , Heap , Merge sort)

Selection Sort

--> 매 사이클마다, 범위에서 [ 가장 작은 값의 위치 ] 와 해당 사이클 [ 가장 앞 원소 위치 ]  와 와 교환
 가장 작은 놈 찾아서 제일 앞으로 보냄

 

 

 

void selection_sort(s_record a[], int n){

 

for (int j = 0 ; j<n ; i++){            // 해당 사이클의 첫 원소를 최솟값이라고 해놓고 비교 시작

int min =j;

  for(int i = j+1 ; i <n ; i ++){           // 각 리스트들을 돌면서 가장 작은 값 찾기

   if( a[i] < a[j] )

   min = i; 

}
s_recore tmp = a[min];
a[min] = a[i];

a[i] = tmp

}

}

 

 

---

Quick sort 

 

시작 : 첫 원소를 기준(pivot)으로 잡는다
--> while 왼쪽 ( 작은 쪽 i )에서 전진하다가 pivot보다 큰 값이 나오면 멈춘다.
   + while 오른쪽 ( 큰 쪽 j ) 에서 후진하다가 pivot보다 작은 값이 나오면 멈춘다. 

--> 둘 다 멈춰서 밑으로 나왔을 때, (i<j)이면 (= i와j가 교차하지 않았으면) swap( a[i] , a[j] ) 
                                (i>j) 이면 (=교차했으면) while을 탈출했을거고 swap( a[left], a[j] ) 한 뒤에

     오른쪽 왼쪽 파트에서 Quick sort 진행.

 

 

: Worst case 

이미 sort가 되어있는 array면 효율은 최악이다.

--> 매 사이클마다 큰 쪽 / 작은 쪽이 아니라. 그냥 끝만 숭덩숭덩 썰고 있기 때문에

검색 대상이 왼쪽으로 잘려야 일이 빨리빨리 줄어드는데, 오른쪽이면 곤란..

▶ 개선 방법 : 1. 중간 위치의 원소를 pivot으로 
                       2. 처음, 중간,  끝 원소 중에서 중간값을 pivot으로 선택한다. = median left 
                           (물론 처음중간끝 3개보단 5개,7개가 낫긴한데 그럼 배보다 배꼽이 커짐)
                       

-->  비교 + 교환 의 과정을 거치는 sort에서 최적의 Time complexity는 O( n log n) 이다.  

---

Heap sort

 

 

힙의 특성을 이용한 sort.

 

가장 위(앞 인덱스) = 가장 큰 값인 걸 이용하여 푼다.

 

개념은 이렇다.

해당 사이클에서 , size =  k 일 때, 가장 앞인 h[1]에 있는 값을 h[size] 로 (가장 뒤로) 보낸다.

이 사이클의 결과로는 가장 큰 값이 배열의 가장 뒤쪽으로 간다.

사이클이 마치면 size --; 를 한다.  (이건 i가 감소하는 반복문으로 해줘도 됨)
그리고 가장 작은 값이 첫번째 원소가 되었으므로 adjust를 해준다.

 

그 다음 사이클은 이전 사이클 크기에서 1이 줄었기 때문에 마지막 인덱스는 건들 일이 없으므로 똑같이 반복해주면 된다.

 

 
+ 주의할 점 : 원소의 개수가 n 배열을 받으면,  0 ~ n-1 인 배열을 받기 때문에 계산하기 편하도록

1~ n까지인 배열로 옮겨준다.

---

Merge sort