Created
September 7, 2017 10:42
-
-
Save thinkphp/93b955d3d73fe3a0f1963f2865a52099 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* Adrian Statescu <mergesortv@gmail.com> | |
* StoogeSort implemented in c++. | |
*/ | |
#include <iostream> | |
#include <fstream> | |
#include <vector> | |
#define FIN "algsort.in" | |
#define FOUT "algsort.out" | |
#define pb push_back | |
using namespace std; | |
class Container { | |
public: | |
Container(vector<int> _arr):arr(_arr){n = arr.size();} | |
void sort() { | |
_stoogesort(0, n - 1); | |
}; | |
void print() { | |
ofstream fout(FOUT); | |
for(auto v:arr) fout<<v<<" "; | |
}; | |
private: | |
vector<int> arr; | |
int n; | |
void _stoogesort(int lo, int hi) { | |
if(lo>=hi) return; | |
if(arr[lo] > arr[hi]) { | |
int tmp = arr[lo]; | |
arr[lo] = arr[hi]; | |
arr[hi] = tmp; | |
} | |
if((hi - lo + 1) > 2) { | |
int t = (hi - lo + 1) / 3; | |
_stoogesort(lo, hi - t); | |
_stoogesort(lo + t, hi); | |
_stoogesort(lo, hi - t); | |
} | |
} | |
}; | |
int main() { | |
vector<int> arr; | |
int elem, n; | |
ifstream fin(FIN); | |
fin>>n; | |
for(int i = 0; i < n; ++i) fin>>elem, arr.pb(elem); | |
Container container(arr); | |
container.sort(); | |
container.print(); | |
return(0); | |
}; |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment