Juyong Jeong

💻Game Programmer

Bubble Sort

post_thumbnail

void bubble_sort(vector<int>& v)
{
  int size = static_cast<int>(v.size());

  for (int i = 0; i < size - 1; ++i)
  {
    bool swapped = false;

    // 매번 탐색한 범위에서 가장 큰 element를 맨 뒤로 밀어냄
    // => 비교할 범위를 줄임
    for (int j = 0; j < size - i - 1; ++j)
    {
      if (v[j] > v[j + 1])
      {
        swapped = true;
        swap(v[j], v[j + 1]);
      }
    }
    
    // done sorting
    if (!swapped)
      break;
  }
}

Selection Sort

post_thumbnail

void selection_sort(vector<int>& v)
{
  // 탐색한 범위 중 가장 작은 element를 맨 앞으로 보냄
  int size = static_cast<int>(v.size());

  for (int i = 0; i < size - 1; ++i)
  {
    int min = i;
    // 가장 작은 원소의 index 찾음
    for (int j = i; j < size; ++j)
    {
      if (v[min] > v[j])
        min = j;
    }

    // 맨 앞서부터 가장 작은 원소의 index와 swap
    if (min != i)
      swap(v[min], v[i]);
  }
}

Insertion Sort

post_thumbnail

// 가상의 sorted와 unsorted로 구간을 나누어 정렬
void insertion_sort(vector<int>& v)
{
  int size = static_cast<int>(v.size());

  for (int i = 1; i < size ; ++i)
  {
    // 선택한 원소가 적정 위치에 갈 때까지 체크하고 swap
    for (int j = i ; j > 0; --j)
    {
      if (v[j] < v[j - 1])
        swap(v[j], v[j - 1]);
    }

    // 비교가 끝나면 다음 i로 옮겨 반복...
  }
}

Merge Sort

post_thumbnail

// divide를 먼저 실행한 뒤 -> conquer하는 과정에 sorting
void merge_sort(vector<int>& v, int l, int r)
{
  if (l < r)
  {
    int mid = (l + r) / 2;

    // divide
    merge_sort(v, l, mid);
    merge_sort(v, mid + 1, r);

    // conquer
    int i = 0, j = 0, k = l,
      n1 = mid - l, n2 = r - (mid + 1);

    // 두 갈래로 나누어 복사
    vector<int> left(v.begin() + l, v.begin() + mid + 1),
      right(v.begin() + mid + 1, v.begin() + r + 1);

    // left와 right의 원소를 순서대로 비교하며 배열 v로 값 복사
    while (i <= n1 && j <= n2)
    {
      if (left[i] < right[j])
        v[k++] = left[i++];

      else
        v[k++] = right[j++];
    }

    // 위 과정에서 한쪽 배열이 먼저 끝날 경우,
    // 나머지 배열을 복사
    while (i <= n1)
      v[k++] = left[i++];

    while (j <= n2)
      v[k++] = right[j++];
  }
}

Quick Sort

post_thumbnail

// divide 하는 과정에서 pivot을 기준으로 swap을 통해 sorting
void quick_sort(vector<int>& v, int l, int r)
{
  int i = l, j = r;
  // 축을 정하고 그를 기점으로 swap
  int mid = v[(l + r) / 2];

  while (i <= j)
  {
    while (v[i] < mid)
      ++i;

    while (mid < v[j])
      --j;

    if (i <= j)
    {
      swap(v[i], v[j]);
      ++i, --j;
    }
  }

  if (l < j) quick_sort(v, l, j);
  if (i < r) quick_sort(v, i, r);
}

Locality (지역성)

  • CPU가 짧은 시간 범위 내에 일정 구간의 메모리 영역을 반복적으로 엑세스하는 경향
    • 메모리 정보를 균일하게 엑세스 하는 것이 아님
    • 짧은 시간 내에 특정 부분을 집중적으로 참조
  • 함수 설계 및 사용처를 보고 특정 메모리를 캐시에 올려 재사용할 수 있음
    • 현재 프로세스의 실행 패턴을 보고 가까운 미래에 프로세스의 코드와 데이터를 합리적으로 사용하도록 예측
    • 자주 사용되는 페이지를 물리 메모리와 캐시 메모리에 둠
  • 지역성의 정도가 떨어지면 캐시에 접근하지 않고 메인 메모리로 접근
    • = 캐시 미스

quick sort vs. merge sort

merge sort post_thumbnail

quick sort post_thumbnail

  • merge sort는 정렬할 전 구간에 걸쳐 엑세스
  • quick sort는 divide한 구간을 차례로 반복적으로 엑세스
  • 참조의 지역성
    • 대부분의 프로그램들은 모두 단시간에 반복적으로 접근하는 데이터가 존재
    • 이 과정을 효율적으로 수행하기 위해 캐시 사용
  • quick sort이 merge sort보다 더 참조의 지역성 성질을 띰
    • 캐시의 도움을 더 받음

Quick Sort의 Worst Case

  • Quick sort는 피벗을 기준으로 left와 right로 divide 하는 로직
  • divide를 총 원소의 개수만큼 하는 경우
    • 이미 정렬이 되어있는 경우

Radix Sort 기수 정렬

post_thumbnail

  • 낮은 자리 수(digit) 부터 정렬하는 알고리즘
  • 비교 연산을 하지 않고, 정렬 속도가 빠르나 메모리가 더 많이 필요함
  • 시간 복잡도는 O(dn)
  • 자리수가 고정되어 있어서 안정성이 있는 정렬 방식
void radix_sort(int array[], int size){

  vector<queue<int>> queues;
  queues.emplace_back(10);

  int max = array[0];
  int digit = 0;
  int factor = 1;

  // 최대 자리수 계산
  for(int i=1; i<size; i++)
  {
    if(max<array[i]) 
      max = array[i];
  }
  for(int i=max; i>0;i/=10)
  {
    digit++;
  }

  // 정렬해야할 원소 중 최대 자리수까지 반복
  for(int i =0; i<digit; i++)
  {
    // 0~9까지 돌아가며 반복
    for(int j=0; j<10; j++) 
    { 
      // 원소들을 돌아가며 반복
      for(int k=0; k<size; k++)
      {
        // 자리수가 동일한 원소를 찾으면 put
        if((array[k] / factor) % 10 == j)
        {
          q[j].push(array[k]);
        }
      }
    }
    factor *=10;

    // 자리수 별 queue에 들어가 있는 원소들을 차례대로 정렬
    for (auto& q: queues)
    {
      int qSize = q.size();
      for(int i=0; i < qSize; i++){
        array[i] = q.pop();
      }
    }
  }
}

Shell Sorting 쉘 정렬

post_thumbnail

  • Insertion Sorting의 확장 버전
  • Insertion이 이웃한 원소끼리 비교를 하는데 비해, Shell은 일정 간격끼리 비교
  • 시간 복잡도는 O(n)
    • 평균의 경우 O(n^1.5)
    • 최악의 경우 O(n^2)
void shell_sort(int a[], int size) {
    int i, j, temp;

  // 간격 세팅
    int gap = size / 2;

    while( gap > 0 ) {
        for( i=gap; i<size; i++ ) {

      temp = a[i];
            j = i;
      // 일정 간격뒤에 떨어진 원소와 비교
            while( j>=gap && a[j-gap]>temp ) {
        // 앞쪽 원소가 더 크다면 swap
                a[j] = a[j-gap];
                j -= gap;
            }
            a[j] = temp;
        }
    // 더 작은 간격으로 gap 업데이트
        gap /= 2;
    }
}

int main() {
    int arr[] = {9,1,22,4,0,-1,1,22,100,10};
    int size = sizeof(arr)/sizeof(int);
    shell_sort(arr, size);
    for(int x: arr) std::cout << x << " ";
    // -1 0 1 1 4 9 10 22 22 100 
}

Heap Sorting 힙 정렬

post_thumbnail

  • 최소 힙 또는 최대 힙을 구현해 정렬
  • 최대, 혹은 최소 값을 차례대로 삭제하면서 pop 되는 원소들을 차례대로 정렬
  • 힙 설명

정렬 별 장단점

post_thumbnail

정렬 별 시간 / 공간 복잡도

post_thumbnail

출처

Categories: ,

Updated: