C++ 알고리즘:: 정렬 알고리즘 정리 (버블 정렬, 선택 정렬, 삽입 정렬, 퀵 정렬, 병합 정렬)

Sorting Algorithm 정렬 알고리즘

Big O는 알고리즘의 퍼포먼스를 이해하기 쉽고 효율적으로 작성하는 방법이다.

그러나 Big O가 모든 알고리즘을 완벽하게 설명하는 것은 아니다.

알고리즘이 같은 Big O지만 각 퍼포먼스가 다르기 때문이다.

 

정렬이란 무엇을 정리하는 것이다.

이진 검색에서 빠른 알고리즘을 사용하려면 배열 정렬을 해야한다.

 

 

 

1. Bubble Sorting 버블 정렬

https://gmlwjd9405.github.io/2018/05/06/algorithm-bubble-sort.html

버블은 그렇게 좋은 알고리즘은 아니다. 그러나 이해하기 쉬운 알고리즘이다.

정렬의 입문으로 좋은 토픽이다.

 

배열의 2개의 아이템을 선택하고, 비교한다.

왼쪽이 오른쪽보다 크면 swap하며 바꾸는 방식이다. 

비교하고 swap하며 반복하고, 값이 큰 아이템이 끝까지 bubble로 이동하는 것이다.

 

 

# include <stdio.h>
# define MAX_SIZE 5

// 버블 정렬
void bubble_sort(int list[], int n){
  int i, j, temp;

  for(i=n-1; i>0; i--){
    // 0 ~ (i-1)까지 반복
    for(j=0; j<i; j++){
      // j번째와 j+1번째의 요소가 크기 순이 아니면 교환
      if(list[j]<list[j+1]){
        temp = list[j];
        list[j] = list[j+1];
        list[j+1] = temp;
      }
    }
  }
}

void main() {
  int i;
  int n = MAX_SIZE;
  int list[n] = {7, 4, 5, 1, 3};

  // 버블 정렬 수행
  bubble_sort(list, n);

  // 정렬 결과 출력
  for(i=0; i<n; i++){
    printf("%d\n", list[i]);
  }
}

//https://gmlwjd9405.github.io/2018/05/06/algorithm-bubble-sort.html

 

버블 정렬의 시간복잡도?

https://gmlwjd9405.github.io/2018/05/06/algorithm-bubble-sort.html

버블 정렬은 배열의 N-1번을 반복을 하는 것이다.

최악의 경우는 모든 아이템을 스왑해야 한다. 

즉, 모든 사이클마다 아이템을 교환해야 하기 때문에 시간 복잡도는 O(n^2)이다.

때문에 그닥 좋은 알고리즘은 아닌 것이다.

 

 

 

2. Selection Sorting 선택 정렬

https://gmlwjd9405.github.io/2018/05/06/algorithm-selection-sort.html

배열을 가지고 비교를 할 때, 가장 작은 아이템의 위치를 변수에 저장한다.

계속 체크를 하다가, 가장 작은 수에 도착하면 해당 위치를 지정하고 마무리한다.

그 다음 swap을 한다.

가장 작은 숫자를 고르고, 첫 순서와 바꾼다.

1은 정렬된 파트이므로, 정렬된 1을 제외하고 정렬되지 않은 수중에 가장 작은 숫자를 찾는다. 

다음 작은 숫자인 2를 찾는데 올바른 위치라면 스왑하지 않는다.

 

# include <stdio.h>
# define SWAP(x, y, temp) ( (temp)=(x), (x)=(y), (y)=(temp) )
# define MAX_SIZE 5

// 선택 정렬
void selection_sort(int list[], int n){
  int i, j, least, temp;

  // 마지막 숫자는 자동으로 정렬되기 때문에 (숫자 개수-1) 만큼 반복한다.
  for(i=0; i<n-1; i++){
    least = i;

    // 최솟값을 탐색한다.
    for(j=i+1; j<n; j++){
      if(list[j]<list[least])
        least = j;
    }

    // 최솟값이 자기 자신이면 자료 이동을 하지 않는다.
    if(i != least){
        SWAP(list[i], list[least], temp);
    }
  }
}

void main(){
  int i;
  int n = MAX_SIZE;
  int list[n] = {9, 6, 7, 3, 5};

  // 선택 정렬 수행
  selection_sort(list, n);

  // 정렬 결과 출력
  for(i=0; i<n; i++){
    printf("%d\n", list[i]);
  }
}

// 출처 : https://gmlwjd9405.github.io/2018/05/06/algorithm-selection-sort.html

 

선택 정렬의 시간 복잡도

버블과 유사하게 스왑, 비교도 있다.

정렬되지 않은 배열에서 가장 작은 숫자를 찾으므로 N-1비교를 한다.

이것은 버블과 같지만, 버블과 다르게 N번의 스왑을 하지는 않는다.

 

선택 정렬에서는 매번 사이클마다 한 번의 스왑만 하면 된다.

버블보다는 좋을 수 있다.

그러나, 선택 정렬의 시간 복잡도도 O(n^2)이다.

 

 

 

3. Insertion Sort 삽입 정렬

https://gmlwjd9405.github.io/2018/05/06/algorithm-insertion-sort.html

동일한 배열을 삽입 정렬로 정리해보자.

인덱스 1번부터 시작을 한다. (실제로는 2번째)

왼쪽이 1번보다 크면 바꾼다. 또 인덱스 1을 기준으로 바꾼다.

순서가 맞다면 다시 비교를 하고 바꾼다.

또 1로 작업을 하는데 1보다 크면 다 이동을 하고, 최종적으로 1을 앞에 둔다.

삽입 정렬은 필요한 아이템만 스캔을 하므로 선택정렬보다 빠르다. (선택 정렬은 모두를 스캔함)

 

# include <stdio.h>
# define MAX_SIZE 5

// 삽입 정렬
void insertion_sort(int list[], int n){
  int i, j, key;

  // 인텍스 0은 이미 정렬된 것으로 볼 수 있다.
  for(i=1; i<n; i++){
    key = list[i]; // 현재 삽입될 숫자인 i번째 정수를 key 변수로 복사

    // 현재 정렬된 배열은 i-1까지이므로 i-1번째부터 역순으로 조사한다.
    // j 값은 음수가 아니어야 되고
    // key 값보다 정렬된 배열에 있는 값이 크면 j번째를 j+1번째로 이동
    for(j=i-1; j>=0 && list[j]>key; j--){
      list[j+1] = list[j]; // 레코드의 오른쪽으로 이동
    }

    list[j+1] = key;
  }
}

void main(){
  int i;
  int n = MAX_SIZE;
  int list[n] = {8, 5, 6, 2, 4};

  // 삽입 정렬 수행
  insertion_sort(list, n);

  // 정렬 결과 출력
  for(i=0; i<n; i++){
    printf("%d\n", list[i]);
  }
}

// 출처 : https://gmlwjd9405.github.io/2018/05/06/algorithm-insertion-sort.html

 

삽입 정렬 알고리즘의 특징

장점
- 안정된 정렬 방법
- 레코드의 수가 적을 경우 알고리즘 자체가 매우 간단하므로 다른 복잡한 정렬 방법보다 유리할 수 있다.
- 대부분위 레코드가 이미 정렬되어 있는 경우에 매우 효율적일 수 있다.

단점
- 비교적 많은 레코드들의 이동을 포함한다.
- 레코드 수가 많고 레코드 크기가 클 경우에 적합하지 않다.

 

삽입 정렬 알고리즘의 시간 복잡도

그러나, 삽입 정렬의 시간복잡도는 동일하게 O(n^2)이다.

이렇게 다양한 알고리즘이 있고, 매우 다른데 시간 복잡도는 동일하다.

따라서 최악이 아닌 평균의 시나리오를 봐야 한다.

 

삽입 정렬, 선택 정렬 모두 최악의 경우에 O(n^2) 최고의 경우에 O(n)이다.

따라서 디테일이 매우 중요하다. 

삽입, 선택 정렬은 작은 DB기준으로 훌륭한 알고리즘이다.

 

위 세 정렬은 시간 복잡도가 높기 때문에 비효율적이라 인기는 없다. 그러나 배우기 쉽다.

 

 

 

4. Quick Sorting 퀵 정렬 

퀵정렬은 대표적으로 분할 정복 알고리즘을 사용한다

특정 배열이 있을때 원소를 나누어서 더 빠르다. 평균 속도는 O(N*logN)이다.

logN은 거의 상수라고 할 정도로 작은 숫자이다.

 

퀵정렬이란 특정한 값을 기준으로 큰 숫자와 작은 숫자룰 나누면 어떨까? 라는 것이다.

퀵정렬은 기준 값, 즉 피봇(pivot)을 기준으로 왼쪽과 오른쪽을 나누는 알고리즘이다.

분할 정복이라고 할 수 있다.

 

퀵정렬 알고리즘의 개념

- 분할(Divide): 입력 배열을 피벗을 기준으로 비균등하게 2개의 부분 배열(피벗을 중심으로 왼쪽: 피벗보다 작은 요소들, 오른쪽: 피벗보다 큰 요소들)로 분할한다.
- 정복(Conquer): 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용하여 다시 분할 정복 방법을 적용한다.
- 결합(Combine): 정렬된 부분 배열들을 하나의 배열에 합병한다.

 

순환 호출이 한번 진행될 때마다 최소한 하나의 원소(피벗)는 최종적으로 위치가 정해지므로, 

이 알고리즘은 반드시 끝난다는 것을 보장할 수 있다.

 

 

https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html

배열이 있을 때 주로 가장 앞의 값을 피봇으로 설정한다.

왼쪽에서 오른쪽, 오른쪽에서 왼쪽으로 보며 선택을 한다.

피봇보다 큰 값과, 피봇보다 작은 값을 각각 선택하고 그 값들을 바꾼다.

만약 엇갈린 상황이 온다면, 왼쪽값과 피봇의 값을 바꾼다.

한번 분할을 하면 왼쪽 집합은 기준점보다 작고, 오른쪽은 기준점보다 크다.

또 피봇을 다시 설정한다. 엇갈리면 다시 설정한다.

 

# include <stdio.h>
# define MAX_SIZE 9
# define SWAP(x, y, temp) ( (temp)=(x), (x)=(y), (y)=(temp) )

// 1. 피벗을 기준으로 2개의 부분 리스트로 나눈다.
// 2. 피벗보다 작은 값은 모두 왼쪽 부분 리스트로, 큰 값은 오른쪽 부분 리스트로 옮긴다.
/* 2개의 비균등 배열 list[left...pivot-1]와 list[pivot+1...right]의 합병 과정 */
/* (실제로 숫자들이 정렬되는 과정) */
int partition(int list[], int left, int right){
  int pivot, temp;
  int low, high;

  low = left;
  high = right + 1;
  pivot = list[left]; // 정렬할 리스트의 가장 왼쪽 데이터를 피벗으로 선택(임의의 값을 피벗으로 선택)

  /* low와 high가 교차할 때까지 반복(low<high) */
  do{
    /* list[low]가 피벗보다 작으면 계속 low를 증가 */
    do {
      low++; // low는 left+1 에서 시작
    } while (low<=right && list[low]<pivot);

    /* list[high]가 피벗보다 크면 계속 high를 감소 */
    do {
      high--; //high는 right 에서 시작
    } while (high>=left && list[high]>pivot);

    // 만약 low와 high가 교차하지 않았으면 list[low]를 list[high] 교환
    if(low<high){
      SWAP(list[low], list[high], temp);
    }
  } while (low<high);

  // low와 high가 교차했으면 반복문을 빠져나와 list[left]와 list[high]를 교환
  SWAP(list[left], list[high], temp);

  // 피벗의 위치인 high를 반환
  return high;
}

// 퀵 정렬
void quick_sort(int list[], int left, int right){

  /* 정렬할 범위가 2개 이상의 데이터이면(리스트의 크기가 0이나 1이 아니면) */
  if(left<right){
    // partition 함수를 호출하여 피벗을 기준으로 리스트를 비균등 분할 -분할(Divide)
    int q = partition(list, left, right); // q: 피벗의 위치

    // 피벗은 제외한 2개의 부분 리스트를 대상으로 순환 호출
    quick_sort(list, left, q-1); // (left ~ 피벗 바로 앞) 앞쪽 부분 리스트 정렬 -정복(Conquer)
    quick_sort(list, q+1, right); // (피벗 바로 뒤 ~ right) 뒤쪽 부분 리스트 정렬 -정복(Conquer)
  }

}

void main(){
  int i;
  int n = MAX_SIZE;
  int list[n] = {5, 3, 8, 4, 9, 1, 6, 2, 7};

  // 퀵 정렬 수행(left: 배열의 시작 = 0, right: 배열의 끝 = 8)
  quick_sort(list, 0, n-1);

  // 정렬 결과 출력
  for(i=0; i<n; i++){
    printf("%d\n", list[i]);
  }
}

// 출처 : https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html

 

퀵 정렬 알고리즘의 특징

장점
- 속도가 빠르다. (시간 복잡도가 O(nlog₂n)를 가지는 다른 정렬 알고리즘과 비교했을 때도 가장 빠르다.)
- 추가 메모리 공간을 필요로 하지 않는다. (퀵 정렬은 O(log n)만큼의 메모리를 필요로 한다.)

단점
- 정렬된 리스트에 대해서는 퀵 정렬의 불균형 분할에 의해 오히려 수행시간이 더 많이 걸린다.

퀵 정렬의 불균형 분할을 방지하기 위하여 피벗을 선택할 때 더욱 리스트를 균등하게 분할할 수 있는 데이터를 선택한다.
ex) 리스트 내의 몇 개의 데이터 중에서 크기순으로 중간 값(medium)을 피벗으로 선택한다.

 

 

퀵 정렬은 한 번 정렬을 했을 때, 왼쪽과 오른쪽이 나누어진다는 특징이 있다.

이렇게 빠른 이유는? 잘게 쪼개고 합쳐서 연산수가 작아지기 때문이다.

데이터의 개수가 N이고 logN만큼 된다는 것이다.

 

큰 데이터의 개수도 퀵정렬은 빠르게 수행한다는 것이 특징이다.

 

 

 

5. Merge Sorting 병합 정렬

퀵정렬은 피벗값에 따라 편향하게 분할되면 최악의 경우 O(N^2)이다.

그러나 병합은 최악의 경우가 없어서 O(N*logN)을 보장한다.

일단 반으로 나누고 나중에 합쳐서 정렬한다는 것이 병합정렬이다.

 

병합 정렬 알고리즘의 개념

- 분할(Divide): 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다.
- 정복(Conquer): 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용하여 다시 분할 정복 방법을 적용한다.
- 결합(Combine): 정렬된 부분 배열들을 하나의 배열에 합병한다.

 

각각 두 개의 배열 안에서만 정렬이 된 것이다

기본적으로 정렬이 된 상태에서 새로 정렬을 한 상태이다.

또 그 배열을 합쳐서 비교한다.

결과적으로 각각 정렬이 된 상태로 유지가 된다.

그것을 또 합쳐서 최종 배열을 만든다.

 

# include <stdio.h>
# define MAX_SIZE 8
int sorted[MAX_SIZE] // 추가적인 공간이 필요

// i: 정렬된 왼쪽 리스트에 대한 인덱스
// j: 정렬된 오른쪽 리스트에 대한 인덱스
// k: 정렬될 리스트에 대한 인덱스
/* 2개의 인접한 배열 list[left...mid]와 list[mid+1...right]의 합병 과정 */
/* (실제로 숫자들이 정렬되는 과정) */
void merge(int list[], int left, int mid, int right){
  int i, j, k, l;
  i = left;
  j = mid+1;
  k = left;

  /* 분할 정렬된 list의 합병 */
  while(i<=mid && j<=right){
    if(list[i]<=list[j])
      sorted[k++] = list[i++];
    else
      sorted[k++] = list[j++];
  }

  // 남아 있는 값들을 일괄 복사
  if(i>mid){
    for(l=j; l<=right; l++)
      sorted[k++] = list[l];
  }
  // 남아 있는 값들을 일괄 복사
  else{
    for(l=i; l<=mid; l++)
      sorted[k++] = list[l];
  }

  // 배열 sorted[](임시 배열)의 리스트를 배열 list[]로 재복사
  for(l=left; l<=right; l++){
    list[l] = sorted[l];
  }
}

// 합병 정렬
void merge_sort(int list[], int left, int right){
  int mid;

  if(left<right){
    mid = (left+right)/2 // 중간 위치를 계산하여 리스트를 균등 분할 -분할(Divide)
    merge_sort(list, left, mid); // 앞쪽 부분 리스트 정렬 -정복(Conquer)
    merge_sort(list, mid+1, right); // 뒤쪽 부분 리스트 정렬 -정복(Conquer)
    merge(list, left, mid, right); // 정렬된 2개의 부분 배열을 합병하는 과정 -결합(Combine)
  }
}

void main(){
  int i;
  int n = MAX_SIZE;
  int list[n] = {21, 10, 12, 20, 25, 13, 15, 22};

  // 합병 정렬 수행(left: 배열의 시작 = 0, right: 배열의 끝 = 7)
  merge_sort(list, 0, n-1);

  // 정렬 결과 출력
  for(i=0; i<n; i++){
    printf("%d\n", list[i]);
  }
}

// 출처 : https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html

너비가 N이고, 높이는 log28로 3이된다.

지수적으로 증가하므로 조금만 내려가도 전체 데이터를 모두 확인할 수 있다.

합치는 순간에 정렬을 해야 한다.

두 개의 부분집합을 합쳐서 한 개의 집합을 만드는 과정은 N밖 에 안된다.

i, j중에 더 작은 부분을 넣는다. 데이터개수 N개만 확인을 하면 된다. 4개의 값은 4개만 비교하면 된다. 

 

합병 정렬 알고리즘의 특징

단점
- 만약 레코드를 배열(Array)로 구성하면, 임시 배열이 필요하다. 제자리 정렬(in-place sorting)이 아니다.
- 레코드들의 크기가 큰 경우에는 이동 횟수가 많으므로 매우 큰 시간적 낭비를 초래한다.

장점
- 안정적인 정렬 방법. 데이터의 분포에 영향을 덜 받는다. 즉, 입력 데이터가 무엇이든 간에 정렬되는 시간은 동일하다. (O(nlog₂n)로 동일)

 

병합정렬은 퀵정렬의 한계점을 보완할 수 있다.

평균적으로 퀵보단 빠르지 않지만 보장을 한다는 점이다.

 

또한, 정렬 배열은 반드시 전역 변수로 선언한다.

메모리 활용이 비효율적이지만, 결과적으로 시간복잡도가 N*logN이 보장된다.

 

 

 

 

 

출처 : https://www.youtube.com/watch?v=Bor_CRWEIXo&list=PLGE_T7WI9LMrkrMTTJJAMgS_ATWwqvtkm

https://www.youtube.com/watch?v=O-O-90zX-U4&t=3s 

https://www.youtube.com/watch?v=ctkuGoJPmAE&t=5s 

https://gmlwjd9405.github.io/2018/05/06/algorithm-bubble-sort.html

 

[알고리즘] 버블 정렬(bubble sort)이란 - Heee's Development Blog

 

https://gmlwjd9405.github.io/2018/05/06/algorithm-selection-sort.html

 

[알고리즘] 선택 정렬(selection sort)이란 - Heee's Development Blog

https://gmlwjd9405.github.io/2018/05/06/algorithm-insertion-sort.html

[알고리즘] 삽입 정렬(insertion sort)이란 - Heee's Development Blog

https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html

[알고리즘] 퀵 정렬(quick sort)이란 - Heee's Development Blog

https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html

[알고리즘] 합병 정렬(merge sort)이란 - Heee's Development Blog