【AOJ ALDS1_6】C: Sort II - Quick Sort
問題
Quick Sort | Aizu Online Judge
方針
- クイックソートはの高速なソートであるが, すべての要素がすでに整列済みの場合など最悪の計算量はである.
- それを解するため, しきい値(pivot)をランダムに取る, データ列の中央値を取るなどの工夫が必要.
- 分割統治法に基づいたアルゴリズムであるが, マージソートと違いインプレースソートである.
コード
#include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<ctime> #include<cctype> #include<climits> #include<iostream> #include<string> #include<vector> #include<map> #include<list> #include<queue> #include<deque> #include<algorithm> #include<numeric> #include<utility> #include<complex> #include<memory> #include<functional> #define rep(i, n) REP(i, 0, n) #define REP(i, a, n) for(int i = a ; i < (int)n ; i++) #define INF 1e9 #define MAX_N 100001 using namespace std; struct Card{ char c; int num; }; int n; Card A[100001], B[100001]; int comp; Card l[MAX_N/2+2]; Card r[MAX_N/2+2]; void merge(int left, int right, int mid){ rep(i, mid-left){ l[i] = B[left + i]; } rep(i, right-mid){ r[i] = B[mid + i]; } l[mid-left].num = r[right-mid].num = INF; int left_idx, right_idx; left_idx = right_idx = 0; REP(i,left,right){ comp++; if(l[left_idx].num <= r[right_idx].num){ B[i] = l[left_idx]; left_idx++; }else{ B[i] = r[right_idx]; right_idx++; } } } void mergeSort(int left, int right){ if(right - left > 1){ int mid = (right + left)/2; mergeSort(left, mid); // 左 mergeSort(mid, right); // 右 merge(left, right, mid); // マージ } } int partition(int p, int r){ int i; i = p-1; REP(j, p, r){ if(A[j].num <= A[r].num){ i++; swap(A[i], A[j]); } } swap(A[i+1], A[r]); return i+1; } void quickSort(int p, int r){ if(r - p > 0){ int ret = partition(p, r); quickSort(p, ret-1); quickSort(ret+1, r); } } bool compare(Card l, Card r){ return (l.num <= r.num); } signed main(){ cin >> n; rep(i, n){ cin >> A[i].c >> A[i].num; B[i].c = A[i].c; B[i].num = A[i].num; } quickSort(0, n-1); mergeSort(0, n); bool flag = false; rep(i, n){ if(A[i].c != B[i].c) flag = true; } if(flag) cout << "Not stable" << endl; else cout << "Stable" << endl; rep(i, n){ cout << A[i].c << " " << A[i].num << endl; } }