C++

알고리즘 - 정렬 정리

Posted by Kyung Jun Cha on 2019-11-01

정렬 (Sorting)

정렬 공간 복잡도 시간 복잡도(최선) 시간 복잡도(평균) 시간 복잡도(최악)
선택 정렬 n n2 n2 n2
버블 정렬 n n2 n2 n2
삽입 정렬 n n n2 n2
병합 정렬 2n nlog2n nlog2n nlog2n
빠른 정렬 n nlog2n nlog2n n2
힙 정렬 n nlog2n nlog2n nlog2n

오름차 순 정렬을 기준으로 설명

1. 선택 정렬(Selection Sort)

  1. 정렬된 부분과 정렬 되지 않은 부분으로 나뉜다.
  2. 정렬 되지 않은 값 중 가장 작은 값을 구해 현재 인덱스와 교체한다.
  3. 다음 인덱스에 같은 과정을 반복합니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
void selectionSort(vector<int>& v)
{
  for(int i=0; i<v.size(); i++)
  {
    for(int j = i+1; j<v.size(); j++)
    {
      if(v[j] < v[i])
      {
        swap(v[j], v[i]);
      }
    }
  }
}

2. 버블 정렬(Bubble Sort)

  1. 매번 연속된 자료를 비교하여 교환하면서 자료를 정렬한다.
  2. 위 과정을 통해 맨 마지막에는 가장 큰 값이 저장 된다.
  3. 매번 마지막을 제외한 배열에 위 과정을 반복한다.
1
2
3
4
5
6
7
8
9
10
11
void bubbleSort(vector<int>& v)
{
  for(int i=1; i<v.size(); i++)
  {
    for(int j=0; j<v.size()-i; j++)
    {
      if(v[j] > v[j+1])
        swap(v[j], v[j+1]);
    }
  }
}

3. 삽입 정렬(Insertion Sort)

  1. 두 번쨰 인덱스부터 시작한다.
  2. 앞의 값들과 비교하여 삽입할 위치를 지정한 후 자료를 뒤로 옮기고 지정한 자리에 자료를 삽입한다.
  3. 위 과정을 반복한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
void insertionSort(vector<int>& v)
{
  for(int i=1; i<v.size(); i++)
  {
    int key = v[i];
    for(int j=0; j<=i; j++)
    {
      if(key < v[j])
      {
        swap(key, v[j]);
      }
    }
  }
}

4. 합병 정렬(Merge Sort)

  1. 분할 정복(Divide and conquer) 방식
  2. 배열의 크기가 1보다 작거나 같을 떄까지 분할한다.
  3. 두 개의 배열을 비교하여 정렬되고 합병된 배열을 만든다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
void merge(vector<int>& v, int s, int e, int m)
{
  vector<int> ret;
  int i = s, j = m + 1, copy =0;

  while(i <= m && j <= e)
  {
    if(v[i] < v[j])
      ret.push_back(v[i++]);
    else
      ret.push_back(v[j++]);
  }

  while(i <= m)
    ret.push_back(v[i++]);
  while(j <= e)
    ret.push_back(v[j++]);

  for(int k=s; k<=e; k++)
  {
    v[k] = ret[copy++];
  }
}

void mergeSort(vector<int>& v, int s, int e)
{
  if(s<e)
  {
    int m = (s+e)/2;
    //divide
    mergeSort(v, s, m);
    mergeSort(v. m+1, e);
    //conquer
    merge(v, s, e, m);
  }
}

다중 스레드를 사용할 때에는 병합 정렬이 유리합니다. 배열을 나눈 다음 병합할 때 이것은 별도의 스레드에서 수행할 수 있습니다. 하지만 빠른 정렬은 피벗을 사용해 정렬을 수행하므로 스레드간에 문제를 효율적으로 구분하는 것이 어렵습니다.

5. 빠른 정렬(Quick Sort)

  1. 분할 정복(Divide and conquer)
  2. 리스트를 피벗(pivot)을 기준으로 작은 값은 왼쪽 큰 값은 오른쪽으로 옮기는 방식으로 정렬한다.
  3. 분할된 양쪽 리스트에 위 과정을 반복한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
int partition(vector<int>& v, int left, int right)
{
  int pivot = v[left];
  int low = left, high = right+1;

  do{
    do{
      low++
    } while(low <= right && v[low] < pivot);

    do{
      high--;
    } while( high >= left && v[high] > pivot);

    if(low<high)
      swap(v[low],v[high]);

  } while(low < high);

  swap(v[left], high);

  return high;
}

void quickSort(vector<int>& v, int left, int right)
{
  if(left < right)
  {
    int pivot_index = partition(v, left, right);

    partition(v, left, pivot_index-1);
    partition(v, pivot_index+1, right);
  }
}

정렬된 리스에 대해서 퀵 정렬의 불균형 분할에 의해 오히려 수행시간이 더 많이 걸린다.
분할 과정이 최대 n번 반복될 수 있다.
시간 복잡도 : O(n2)

6. 힙 정렬(Heap Sort)

  1. 정렬해야 할 n개의 요소들로 최대 힙을 구성한다.
  2. 힙에서 최소 값을 하나씨 꺼내서 배열의 뒤부터 채운다.
1
2
3
4
5
6
7
8
#include <algorithm> //힙 사용
void heapSort(vector<int>& v)
{
  std::make_heap(v.begin(), v.end()); //init max heap

  for(int i=0; i<v.size(); i++)
    std::pop_heap(v.begin(), v.end()-i); // move max value to back  
}
FEATURED TAGS
C++
FRIENDS