정렬 알고리즘 정리

선택 정렬

• 가장 큰 값을 찾아 맨 마지막의 원소와 swap
• O(N^2)

int arr[10] = {2, 53, 76, 4, 5, 3, 13, 32, 88, 25};
int n=10;
for(int i=n-1;i>0;i--){
    swap(*max_element(arr, arr+i+1), arr[i]);
}

버블 정렬

• 앞에서부터 인접한 두 원소를 비교하여 큰 값을 뒤로 보냄 -> 점차 가장 큰 값은 오른쪽으로 가게 됨
• O(N^2)

int arr[5] = {-2, 2, 4, 6, 13};
int n=5;
for(int i=0;i<n;i++){
    for(int j=0;j<n-1-i;j++){
        if(arr[j]>arr[j+1) swap(arr[j], arr[j+1]);
    }
}

Merge Sort

• 배열을 이등분하여 원소가 하나가 될 때 까지 나눈 후, 두 배열씩 합치면서 정렬
• Stable Sort
• O(NlgN)

#include <bits/stdc++.h>
using namespace std;
int n;
int arr[1000001];
int tmp[1000001];

void merge(int st, int en){
    int mid=(st+en)/2;
    int idx1=st, idx2=mid;
    for(int i=st;i<en;i++){
        if(idx1==mid) tmp[i]=arr[idx2++];
        else if(idx2==en) tmp[i]=arr[idx1++];
        else if(arr[idx1]<=arr[idx2]) tmp[i]=arr[idx1++];
        else tmp[i]=arr[idx2++];
    }
    for(int i=st;i<en;i++) arr[i]=tmp[i];
}

void merge_sort(int st, int en){
    if(en-1==st) return;
    int mid=(st+en)/2;
    merge_sort(st, mid);
    merge_sort(mid, en);
    merge(st, en);
}

int main(void){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin>>n;
    for(int i=0;i<n;i++) cin>>arr[i];
    merge_sort(0,n);
    for(int i=0;i<n;i++) cout<<arr[i]<<"\n";
}

Quick Sort

• pivot값을 기준으로 pivot보다 작은 수를 pivot의 왼쪽에, pivot보다 큰 수를 pivot의 오른쪽에 저장
• 배열 안에서의 자리바꿈만으로 처리되어 높은 cache hit rate -> 빠른 속도로 처리 가능
• 추가적인 공간을 사용하지 않는 정렬(In-Place Sort)
• O(NlgN), 최악의 경우에는 O(N^2)

void quick_sort(int st, int en) { // arr[st to en-1] 정렬
  if(en <= st+1) return; // 수열의 길이가 1 이하이면 함수 종료.(base condition)
  int pivot = arr[st]; // 맨앞 원소를 pivot으로 잡음
  int l = st+1; // 포인터 l
  int r = en-1; // 포인터 r
  while(1){
    while(l <= r && arr[l] <= pivot) l++;
    while(l <= r && arr[r] >= pivot) r--;
    if(l > r) break; // l과 r이 역전되는 그 즉시 탈출
    swap(arr[l], arr[r]);
  }
  swap(arr[st], arr[r]); //pivot과 r 값 변경 -> pivot 왼쪽은 pivot보다 작은값, 오른쪽은 큰 값으로 정렬
  quick_sort(st, r);
  quick_sort(r+1, en);
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  quick_sort(0, n);
  for(int i = 0; i < n; i++) cout << arr[i] << ' ';
}

 

 

출처: https://blog.encrypted.gg/955