성장하고 싶은 신입 개발자

병합 정렬

- 분할 정복(Divide & Conquer) 방법을 사용하는 알고리즘

- 알고리즘을 구현함에 있어서 추가적인 임시 배열이 필요 ( 다른 정렬 알고리즘보다 메모리를 더 잡아먹음 )

시간 복잡도

O(N * logN) 

퀵 정렬 vs 병합 정렬

• 퀵 정렬은 최악의 경우 O(N * logN) 을 보장하지 못함 ( 최악의 경우 => O(N^2) )
• 병합 정렬은 최악의 경우에도 O(N * logN)을 보장함
• 둘 다 O(N*logN)만큼 걸리더라도 보통 병합 정렬보다 퀵 정렬이 더 빠름

병합 정렬의 동작 원리

1.  분할 ( 가장 작은 단위까지 분할 )   :   하나의 list를 두 개의 균등한 크기로 분할
2.  정렬 ( 가장 작은 단위부터 정렬 )   :   분할된 부분 list를 정렬

          =>  위 1,2 과정을 정렬이 완료될 때까지 반복 ( 재귀호출 )

분할된 부분 list를 정렬병합하는 과정

       (1) 각 요소의 첫번째 원소끼리 비교 시작

       (2) 비교한 후 작은 수를 임시 배열에 넣고 i++

       (3) 어느 한 쪽이 범위를 넘어가면 멈추고 남은 list의 값들을 뒤에 그대로 집어넣는다(정렬이 되어 있으므로)

병합정렬 알고리즘 구현

#include<iostream>
using namespace std;

int arr[10] = {1,3,5,7,9,2,4,6,8,10};
int* arr2;

void merge(int start, int end){
  int mid = (start + end) / 2;

  int i = start;
  int j = mid + 1;
  int temp = start;

  while(i <= mid && j <= end){
    if(arr[i] <= arr[j]){
      arr2[temp++] = arr[i++];
    }else{
      arr2[temp++] = arr[j++];
    }
  }

  int remain_idx = i > mid ? j : i;
  while(temp <= end){
    arr2[temp++] = arr[remain_idx++];
  }

  for(int i = start; i <= end; i++){
    arr[i] = arr2[i];
  }
}

void mergeSort(int start, int end){
  int mid;
  if(start < end){
    mid = (start + end) / 2;
    mergeSort(start,mid);
    mergeSort(mid+1,end);
    merge(start,end);
  }
}

int main(){
  arr2 = new int[10];
  mergeSort(0,9);

  for(int i = 0;i < 10; i++){
    printf("%d ",arr[i]);
  }

  delete[] arr2;
}

버블 정렬

- 바로 옆에 있는 값과 비교하면서 비교할 때마다 값을 스위칭하면서 이동

- 선택 정렬과 시간 복잡도는 같지만 실제 수행시간이 가장 느림
   => 버블 정렬 : 매번 비교할 때마다 값을 스위칭
   => 선택 정렬 : 전체 원소를 비교해서 최솟값을 찾은 후 가장 마지막에만 값을 스위칭

시간 복잡도

- O(N^2)

#include<stdio.h>
#include<iostream>

int main(){
  int data[] = {1,5,9,8,2,5,6,3,7,10};
  int i,j;

  for(i = 0; i < 10; i++){
    for(j = 0; j < 9 - i; j++){ //인덱스를 넘어가지 않도록 마지막 인덱스 전까지만 돔
      if(data[j] > data[j+1]) std::swap(data[j],data[j+1]);
    }
  }

  for(i=0;i<10;i++){
    printf("%d ",data[i]);
  }
}

삽입 정렬

• 적절한 위치에 삽입한다.
• 버블 정렬, 선택 정렬보다 빠르다.
• 삽입 정렬은 옆의 값과 비교해서 더 클 때만 스위칭하기 때문에 더 빠르다.

• 특정한 경우에 굉장히 빠르게 작용할 수 있다. ( 예 : 거의 정렬되어 있는 데이터일 때 )

시간 복잡도    =>    O(N^2)

동작 원리

- 특정한 위치에서 앞의 원소들과 비교해서 적당한 위치에 들어간다.

ex) 1 5 6 7 8 10 4 3 2 9   

     => 4가 적절한 위치에 들어갈 때 이미 앞 부분은 다 정렬이 되어 있기 때문에 4만 앞의 원소들과 하나씩
          비교해가며 들어가면 되기 때문에 매번 비교할 때마다 선택이나 버블처럼 교환하지 않아도 된다.
   

     1 5 6 7 8 4 10 3 2 9  ->  4와 8 비교해서 자리 바꿈
     1 5 6 7 4 8 10 3 2 9  ->  4와 7 비교해서 자리 바꿈
     1 5 6 4 7 8 10 3 2 9  ->  4와 6 비교해서 자리 바꿈
     1 5 4 6 7 8 10 3 2 9  ->  4와 5 비교해서 자리 바꿈
     1 4 5 6 7 8 10 3 2 9  ->  1과 4 비교해서 4가 더 크므로 여기서 정지 ( 멈출 때에 정지할 수 있다는게 장점 )
  

삽입 정렬 코드

#include<stdio.h>

int main(){
  int i,j,temp;
  int array[10]={1,10,5,8,6,5,4,3,2,9};
  for(i = 0;i < 9; i++){
    j = i;
    while(array[j] > array[j+1]){
      temp = array[j];
      array[j] =  array[j+1];
      array[j+1] = temp;
      j--;
    }
    printf("\n");
  }

}

퀵 정렬

• 데이터의 갯수가 적을 때는 괜찮지만 데이터의 갯수가 10만 개만 넘어가도 보통의 상황에서
  선택,버블,삽입 정렬 알고리즘을 사용하기가 힘들다. 이런 경우 퀵 정렬을 사용한다면
  아무리 많은 양의 데이터라도 빠르게 정렬을 할 수 있다.
• 대표적인 분할 정복 알고리즘
• c 라이브러리로 제공하는 sort() 함수가 퀵 정렬을 기반으로 구현되어 있다.
• 이미 정렬이 되어있거나 거의 정렬되어 있는 데이터에 사용할 때는 성능이 매우 떨어짐

퀵 정렬의 시간 복잡도

평균  :  O(N * logN)    -> 반씩 쪼개서 정렬하기 떄문에 logN인 것이다.

최악  :  O(N^2)

퀵 정렬이 최악인 경우에도 O(N * logN)을 보장하는 방법

- STL 라이브러리에서 제공하는 sort() 함수는 퀵 정렬을 기반으로 하되 별도의 처리를 거쳐
  최악의 경우에도 O(N * logN)을 보장한다.

퀵 정렬 동작 방식

1. 데이터들 중 특정한 값을 피벗(Pivot)으로 정한다.  =>     기준값 설정

2. 피벗을 기준으로 왼쪽에는 피벗보다 작은 값들 오른쪽에는 피벗보다 큰 값들이 모이도록 한다.

3. 왼쪽과 오른쪽을 각각 퀵 정렬을 수행한다.           =>      재귀 호출

4. 최종적으로 전체 값들이 정렬된다.  

배열의 중앙을 피벗(Pivot)으로 잡고 하는 법

  (1)  left, right, pivot 설정

(2) left : pivot보다 큰 값을 찾을 때까지 이동(left++) / right : pivot보다 작은 값을 찾을 때까지 이동(right--)

   - pivot보다 큰 값(left)과 작은 값(right)을 찾고, 서로의 값을 교환

   - 교환한 후 left++ , right--

(3) 위와 같은 과정을 반복해서 피봇보다 큰 값(left)과 작은 값(right) 찾아서 교환

    - 교환한 후 left++, right--;

(4) 값을 교환한 후 left와 right가 엇갈림 ( ☆☆☆☆☆ )

- left와 right가 엇갈려 left가 더 커지게 된 경우 

   => right와 left 두 부분으로 분할해서 따로 퀵 정렬 수행!!

(5) 분할된 두 부분을 각각 퀵 정렬 수행 ( 재귀 호출 )

퀵 정렬 구현 코드

#include<iostream>
using namespace std;

int data[] = {5,1,6,3,4,2,7};

void quickSort(int start, int end){
	if(start >= end) return;
    
    int left = start;
    int right = end;
    int pivot = (start + end) / 2;
    
    while(left < right){
    	while(data[left] < data[pivot]) left++;
        while(data[right] > data[pivot]) right--;
        
        if(left <= right){
        	swap(data[left], data[right]);
            left++;
            right--;
        }
    }
	
    quickSort(start,right);
    quickSort(left,end);
}

int main(){
	int i;
    quickSort(0,6);
    for(i = 0; i < 7; i++){
    	printf("%d ",data[i]);	
    }    
}