codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
/// Find median of 5 numbers /// Result: /// Function Algorithm Swap(min, max): average Comparision(min, max): average /// Algo1 Stl nth_element Swap (0, 3): 1.566 Comp (11, 23): 14.5832 /// Algo2 Heap Swap (0, 5): 2.9146 Comp (4, 8): 6.7076 /// Algo33 Merge Swap (0, 0): 0 Comp (6, 6): 6 /// Algo4 Insertion Swap (0, 0): 0 Comp (5, 7): 6.2573 #include <iostream> #include <cstdlib> #include <ctime> #include <algorithm> #include <cassert> #include <vector> using namespace std; class Int { public: Int(int i) : i(i) {} operator int() { return i; } friend ostream &operator<<(ostream &stream, const Int &i); friend bool operator< (const Int &i1, const Int &i2); static void Reset() { nSwap = nCom = 0; } void swap(Int &i2) { ++Int::nSwap; const int temp = i; i = i2.i; i2.i = temp; } static int nSwap, nCom; private: int i; }; ostream &operator<<(ostream &stream, const Int &i) { stream << i.i;; return stream; } bool operator< (const Int &i1, const Int &i2) { ++Int::nCom; return i1.i < i2.i; } namespace std { template <> void swap<Int>(Int &i1, Int &i2) { i1.swap(i2); } } Int &min(Int &i1, Int &i2) { return (i1 < i2) ? i1 : i2; } #define INDEX i_##__LINE__ #define rep(n) for(int INDEX = 0; INDEX < n; ++INDEX) int Int::nCom, Int::nSwap; // ----------------------------------------------------------- // Swap (0, 3): 1.566 // Comp (11, 23): 14.5832 int Algo1(Int *a) { nth_element(a, a+2, a + 5); return a[2]; } // ----------------------------------------------------------- // Swap (0, 5): 2.9146 // Comp (4, 8): 6.7076 void BalanceHeap2(Int *a) { if(a[1] < a[2]) { if(a[1] < a[0]) swap(a[0], a[1]); } else { if(a[2] < a[0]) swap(a[0], a[2]); } } void InsertInHeap2(Int *a, Int &num) { if(a[0] < num) { swap(num, a[0]); // Actually a[0] = num; swapped for calculation management BalanceHeap2(a); } } int Algo2(Int *a) { BalanceHeap2(a); InsertInHeap2(a, a[3]); InsertInHeap2(a, a[4]); return a[0]; } // ----------------------------------------------------------- int min3(Int &a, Int &b, Int &c) { if(a < b) { if(a < c) return a; else return c; } else { if(b < c) return b; else return c; } } int mid3(Int &a, Int &b, Int &c) { if(a < b) { if(a < c) { if(b < c) return c; else return b; } else return a; } else { if(a < c) return a; else { if(b < c) return b; else return c; } } } //Swap (0, 0): 0 //Comp (6, 6): 6 int Algo33(Int *a) { return a[1] < a[0] ? a[3] < a[2] ? a[1] < a[3] ? a[0] < a[4] ? a[0] < a[3] ? min(a[4],a[3]) : min(a[2],a[0]) : a[4] < a[3] ? min(a[0],a[3]) : min(a[2],a[4]) : a[2] < a[4] ? a[1] < a[2] ? min(a[0],a[2]) : min(a[4],a[1]) : a[1] < a[4] ? min(a[0],a[4]) : min(a[2],a[1]) : a[1] < a[2] ? a[0] < a[4] ? a[0] < a[2] ? min(a[4],a[2]) : min(a[3],a[0]) : a[4] < a[2] ? min(a[0],a[2]) : min(a[3],a[4]) : a[3] < a[4] ? a[1] < a[3] ? min(a[0],a[3]) : min(a[4],a[1]) : a[1] < a[4] ? min(a[0],a[4]) : min(a[3],a[1]) : a[3] < a[2] ? a[0] < a[3] ? a[1] < a[4] ? a[1] < a[3] ? min(a[4],a[3]) : min(a[2],a[1]) : a[4] < a[3] ? min(a[1],a[3]) : min(a[2],a[4]) : a[2] < a[4] ? a[0] < a[2] ? min(a[1],a[2]) : min(a[4],a[0]) : a[0] < a[4] ? min(a[1],a[4]) : min(a[2],a[0]) : a[0] < a[2] ? a[1] < a[4] ? a[1] < a[2] ? min(a[4],a[2]) : min(a[3],a[1]) : a[4] < a[2] ? min(a[1],a[2]) : min(a[3],a[4]) : a[3] < a[4] ? a[0] < a[3] ? min(a[1],a[3]) : min(a[4],a[0]) : a[0] < a[4] ? min(a[1],a[4]) : min(a[3],a[0]); } // ----------------------------------------------------------- // Insertion sort // Swap (0, 0): 0 // Comp (5, 7): 6.2658 int step4(Int &a, Int &b, Int &c, Int &d, Int &e) { // a < b < c < d if(e < b) { return b; } else { if(e < c) return e; else return c; } } int step3(Int &a, Int &b, Int &c, Int &d, Int &e) { // a < b < c if(d < b) { if(d < a) return step4(d, a, b, c, e); else return step4(a, d, b, c, e); } else { if(d < c) return step4(a, b, d, c, e); else return step4(a, b, c, d, e); } } int step2(Int &a, Int &b, Int &c, Int &d, Int &e) { // a < b if(b < c) { // a < b < c return step3(a, b, c, d, e); } else { if(a < c) return step3(a, c, b, d, e); else return step3(c, a, b, d, e); } } int step1(Int &a, Int &b, Int &c, Int &d, Int &e) { if(a < b) return step2(a, b, c, d, e); else return step2(b, a, c, d, e); } int Algo4(Int *a) { // I used only < or >, but refer them also as <= and >= return step1(a[0], a[1], a[2], a[3], a[4]); } // ----------------------------------------------------------- int main () { int minc = 100, mins = 100; int maxc = 0, maxs = 0; int totc = 0, tots = 0; srand ( (unsigned int)time(NULL) ); const int repCount = 10000; //1000000; // may take up to 50 sec rep(repCount) { Int::Reset(); const int num5Array[] = { rand(), rand(), rand(), rand(), rand() }; //random_shuffle(num5Array, num5Array + 5); //rep(5) cout << num5Array[INDEX] << '\t'; cout << endl; vector<int> arr(num5Array, num5Array + 5); nth_element( arr.begin(), arr.begin()+2, arr.end() ); const int expected = arr[2]; vector<Int> Arr(num5Array, num5Array + 5); const int median = Algo33(&Arr[0]); assert(median == expected); minc = min(minc, Int::nCom); mins = min(mins, Int::nSwap); maxc = max(maxc, Int::nCom); maxs = max(maxs, Int::nSwap); totc += Int::nCom; tots += Int::nSwap; } cout << "Swap (" << mins << ',' << ' ' << maxs << "): " << tots * 1.0 / repCount << endl; cout << "Comp (" << minc << ',' << ' ' << maxc << "): " << totc * 1.0 / repCount << endl; return 0; }
Private
[
?
]
Run code
Submit