[정렬-NlogN] 합병, 힙 정렬

log N 넘 어려운 짱구

와 정말 정렬 log N !!! 너무 많이 나옵니다 이게 진짜에요 !!! 이거  이게 !! 너무 많이나와서 기본적으로 무조건 무조건 ~~~~~ 알아야합니다. 여러분들 log N 어려운거 하나도없어요 1,2,3.....N까지 하는게 N이라면 log N은 쉽게 N/2, N/4 , N/8 ... 생각하시면됩니다. 자 이제 평균, 최선, 최악 시간복잡도 logN인 정렬을 한번 알아볼까요??????

 

❤ 합병정렬 이거 도대체 merge? 

개그좀 쳐봤습니다 히히  합병정렬은 대부분 배열 쪼개기라고 생각하시면 됩니다. 정렬을하는데 왜 배열을 쪼갤까 생각도 드시겠죠? 길이 N짜리 배열을 정렬하기위해 N/2 길이의 배열 2개를 정렬해야한다는 의미입니다. 

자연스러운 재귀적인 사고를 활용하여 두 배열에 대해서 동일한 정렬 방식을 시도해야합니다. 

결국

1. 재귀적인 쪼개기

2. 쪼갠 배열을 다시 합친다

3. 합치는과정에서 정렬된 배열로 만든다  

라는 과정을 거치게 될텐데 한번 그림으로 보시죠 

합병정렬의 그림.

 

그림으로 얼추 어떤식으로 이해가 됐으면 사실 코드를 분석해야겠죠? 

void merge_sort(arr, low, high){
	if(low < high){
    	int mid = (low+high)/2;
        merge_sort(arr,low,mid);
        merge_sort(arr,mid+1,high);
        merge(arr,low,mid,high);
        };

int[] merge(arr,low,mid,high){
	int i= low;
    int j= mid+1;
    
    //1번째 while
    while(i<=mid && j<=high){
    	if(arr[i]<=arr[j]){
        	merged_arr[k] = arr[i];
            i++;
            k++;
       	}else{
        	merged_arr[k]=arr[j];
            j++;
            k++;
        }
    //2번째 while
    while (i<=mid){
    	merged_arr[k]=arr[i];
        k++;
        i++;
    }
    //3번째 while
    while(j<=high){
    	merged_arr[k]=arr[j];
		k++;
        j++;
    }
    
    for(int q=0; q<arr.length; q++){
    	arr[q]=merged_arr[q];
    }

 

쉽습니다 정말 쉬워요

 

1.merge_sort 함수 

logN이 적용이 되는 부분입니다.  N/2씩 계속 잘리는 부분이죠 

mid = (low+high)/2 부분을 통해서 재귀함수를 계속 호출하는 부분입니다. 

초반 자르는 부분은 배열의 길이를 1씩까지 자르는 역할을 하고있습니다. 

1씩까지 다 잘랐다면 이제 N의 길이만큼 붙이는 역할로 넘어가겠죠?

 

2.merge 함수

이제는 N의 길이만큼 계속 붙이는 역할을 하는 함수입니다. 

i는 당연히 제일 왼쪽끝, j는 중앙에서 +1 을 하는 역할입니다. 왜이렇게 하는지 무조건 궁금해하실겁니다. 

붙이는 부분

6와 5가 길이가 각각 1인 상황에서 merge_sort 기준으론 6과 5가 같이있는 길이가 2인 함수를 호출합니다. 

길이가 1씩까지 잘랐다면서 길이가 2인 배열이 어디있습니까? 할수도있습니다. 제가 1씩 잘랐다는건 배열을 잘랐다는게 아닌 low, mid. high를 통해서 임의로 1씩 잘랐다고 이야기를하는겁니다. 길이가 2이지만 절반씩 나눈 길이가 된다는것이죠. 

즉 길이가 N이지만 임의로 N/2으로 나눈 배열을 붙이겠다 라는 의미입니다.

 

1번째 while문은 i<=mid && j<= high입니다.

i나 j 둘다 N/2 또는 N의 범위안에 존재할때 둘값을 비교하여 값을 집어넣는행위입니다. 둘중 하나라도 범위를 벗어나게된다면 오류가 나기때문이죠 

그렇다면 0~ N/2 와 N/2+1 ~ N 범위의 값을 서로 비교하며 값을 집어넣는 행위가 되지않을까요?

맞습니다. 바로 그렇게 하는것이죠 ! 그렇다면 N/2+1 ~N 범위가 항상 0~ N/2보다 값이 작아서 먼저 값을 다채워버린다면 어떻게해야할까요? 

 

그렇기에 2번째 while문 , 3번째 while문이 존재하는것입니다.

 

2번째 while문은 1번째  while문에서 N/2+1 ~ N 범위를 먼저 다채워서 j 범위값에서 벗어날때

3번째 while문은 1번째 while문에서 0~ N/2 범위를 먼저 다채워서 i 범위값에서 벗어날때 입니다. 이렇게된다면 아마도 

우리가 생각한 병합정렬이 만들어지게됩니다.

병합정렬은 큰것을 나누어 작은것으로 만든다음 다시 작은것에서 큰것을 만드는 정렬이라고 생각하시면됩니다.

 

❤ 힙정렬~! 

Heap 정렬 어디서 많이 들어보시지않으셨나요? Max Heap 정렬, Min Heap 정렬 ~~~~ 이 2개만 기억하시면될거같습니다.

Heap이란 완전 이진 트리를 사용하는 정렬 알고리즘이라고 생각하시면됩니다. 트리를 사용하는것이죠 Max Heap 정렬과 Min Heap 정렬은 완전 이진트리를 사용하여 부모노드가 높은값인지 낮은값인지 생각하면  됩니다. 완전 이진 트리를 사용하니 당연히 logN 의 비용이 들고 N만큼의 크기를 비교해야하니 NlogN 시간복잡도가 사용됩니다. 

 

heapify 을 사용하여 정렬하는 과정

1. 완전 이진트리라는 기준하에 N /2 번째 원소부터 거꾸로 1번째 원소까지 순서대로 heapify 라는 과정을 거칩니다.

2. heapify라는 과정은 현재 노드를 기준으로 이 노드가 heap 특성에 맞을때 까지 계속 밑으로 내려주는 과정을 일컫습니다.

Heapify 과정

A. 현재 노드 위치를 i라고 가정하고 i와 i/2, i/2+1 노드들의 값을 서로 비교합니다. i값이 제일 크다면 i-1 노드로 바로 갑니다. (제일 큰 값을 largest라고 가정하겠습니다.)

B. i값이 제일크지 않고 i/2 또는 i/2+1 노드가 크다면  i노드와 서로 Swap합니다. largest가 있던위치에서 다시 heapify 과정을 거칩니다.

C. largest가 있던 위치에서 자식노드가 없다면 skip

 

3. heapify 과정을 거쳐 max-heap 또는 min-heap을 만들었다면 루트노드의 값을 N번째 노드와 swap 시킵니다.

4. 루트노드였던 값은 배열에 저장한후 ( 최대값 혹은 최솟값이라) 연결을 끊습니다.

5. 현 루트노드는 다시 Heapify 과정을 거칩니다. 이때  Heapify 과정은 루트노드에서부터 진행합니다 (거진 1번)

 

다루는 내용이 많으니 Heapify 과정을 그림으로 간략하게 보여드리겠습니다.

 

Heapify 과정을 끝냈으니 이제 정렬을 해야겠죠? 

1번과 7번노드를 서로 교환 후, 7번노드는 건들지 않은채 1번부터 다시 Heapify 과정을  6번노드까지 할수있게끔 진행합니다. 6번노드까지 쭉하는것이 아닌 heapify 과정에서 7번 노드를 건들지않는다는것이 중요합니다. 

 

이제 한번 코드를 볼까요??? 

 

힙정렬 코드 

void heapify(arr[], n, i)
  int largest = i
  int l = i * 2
  int r = i * 2 + 1

  if (l <= n && arr[l] > arr[largest]){
    largest = l;
    }

  if (r <= n && arr[r] > arr[largest]){
    largest = r;
	}

  if (largest != i){
    swap(arr[i], arr[largest])
    heapify(arr, n, largest)
	}
    
void heap_sort(arr[], n)
  for(int i= n/2; i>0; i--;){
    heapify(arr, n, i)
	}
  for(int i=n; i>0; i--){
	swap(arr[1], arr[i])
    heapify(arr, i - 1, 1)
    }

 

 코드...어려워보이죠? 쉽습니다 !

 

1. heap_sort 함수 첫번째 for문

heapify과정을 거치기위해서 n/2 노드부터 1까지 heapify 과정을 거칩니다.

 

2. heapify 함수 

largest 는 i로 고정, l과 r은 자식노드를 의미합니다. 

첫번째과 두번째 if문은 왼쪽 혹은 오른쪽 자식노드가 존재하는지의 여부와 i노드의 값보다 큰지 비교합니다. 크다면 largest가 바뀌어야하지않을까요? 

 

세번째 if문은 larget!=i 즉, 기존에 설정했던 largest가 왼쪽 혹은 오른쪽 노드에 의해서 바뀐다면 

i번째 노드와 i번째 왼쪽 혹은 오른쪽 노드와 값을 바꾼다음, 해당 왼쪽 혹은 오른쪽 노드에 대해서 다시 heapify를 진행합니다. 다시 heapify를 진행하는 이유는 더 높은값을 root노드로 끌어올리기위해서 입니다.

 

2. heap_sort함수 두번째 for문

모든 heapify를 과정을 거친후 오름차순 혹은 내림차순으로 정렬을 하기위해서는 루트노드와 n번째 노드와 교차시킵니다. 루트노드였던 n번째 노드는 건들지 않는선에서 다시 heapify 과정을 통해 다음 최고값을 찾는 for문 입니다.

 

❤ 정렬들을 마무리지으면서...

자 이렇게 우리는 nlogn 정렬들을 알아봤습니다. 정렬은 확실히 내가 원하는 상황에서 사용하는것이 좋습니다. 여러분들도 이렇게 정렬들을 한번 쓱 정리하시면서 내가 원하는 상황에서 원하는 정렬을 사용할수있도록 최선을 다하여 정리를 해보시길 바랍니다. 한번의 경험은 좋은 경험으로 이루어질수있습니다. 여러분들 어렵다고 생각하지마시고 천천히 즐겁게 알고리즘을 즐겨주시길 바랍니다.!