# samples of seven sort algorithms

Email
 Submitted on: 1/3/2015 6:39:00 AM By: Erik Minkin (from psc cd) Level: Beginner User Rating: By 5 Users Compatibility: C++ (general) Views: 3761

Clear examples of: insertion, selection, shellsort, quicksort, mergesort, badsort Please let me know if anything wrong with it and please rate it.

code:
Can't Copy and Paste this?
 ``` //************************************** // Name: samples of seven sort algorithms // Description:Clear examples of: insertion, selection, shellsort, quicksort, mergesort, badsort Please let me know if anything wrong with it and please rate it. // By: Erik Minkin (from psc cd) // // Inputs:input is hardwired, but you can change global variable SIZE in order to change v.size(). // // Returns:returns initial and sorted vector // // Assumes:Example can execute only one algorithm at a time, to see different one simply uncomment one that you would like to experiment with // // Side Effects:badsort can cause system to freeze,so set SIZE >= 5 //************************************** #include #include #include #include using namespace std; //introduces namespace std const int SIZE = 20; void fill_vector(vector & v); ostream & operator<<(ostream & out , const vector & v); void selection(vector & v); void insertion(vector & v); void shellsort( vector & v ); void quicksort( vector & v, int low, int high); void mergesort( vector & v, int low, int high); void merge( vector & v, int low, int middle, int high); void badsort( vector & v); bool sorted(const vector & v); //void swap( int & a,int & b); int main ( void ) { vector v; fill_vector(v); cout << v << endl << "This is a test of sort\n"; //insertion (v); //selection (v); //sort(v.begin(), v.end()); // STL //shellsort(v); quicksort(v , 0, v.size()-1); // mergesort(v, 0, v.size() - 1); //badsort(v); cout << v << endl; return 0; } void fill_vector(vector & v) { srand(time(0)); for (int i = 0; i < SIZE;i++) v.push_back(rand() % 1000); } /* already in STL void swap( int & a,int & b) {int tem = a; a = b; b = tem; } */ void selection(vector & v) { int low; for (int i = 0; i < v.size() - 1; i++) { low = i; for (int j = i+1; j v[j]) low = j; if ( low != i) swap (v[i] , v[low]); } } void insertion(vector & v) {int j; for (int i = 1; i < v.size(); i++) { int tem = v[i]; for ( j = i ; j > 0 && v[j - 1] > tem; j--) v[j] = v[j-1]; if (j != i) v[j] = tem; } } void shellsort( vector & v ) { int j; for( int gap = v.size( ) / 2; gap > 0; gap = gap == 2 ? 1 : gap / 2.2 ) for( int i = gap; i < v.size( ); i++ ) { int tmp = v[ i ]; for( j = i; j >= gap && tmp < v[ j - gap ]; j -= gap ) v[ j ] = v[ j - gap ]; v[ j ] = tmp; } } void quicksort( vector & v, int low, int high) { if ( low < high) { // choose pivot as median of v[low],v[middle],v[high] int i , j; int middle = (low + high) / 2; cout << "initially low and high " << low << " " << high << endl; for (i=low; i <= high; i++) cout << v[i] << " "; if(v[low] > v[middle]) swap (v[low] ,v[middle]); if (v[low] > v[high]) swap(v[low] , v[high]); if (v[middle] > v[high]) swap( v[middle], v[high]); int pivot = v[middle]; swap (v[middle] , v[high-1]); //partition cout << "\nafter picking pivot = " << pivot << endl; for (i=low; i <= high; i++) cout << v[i] << " "; if (high -low > 2 ) { for (i = low , j = high -1; ;) { while (v[++i] < pivot ); while (j > 0 && v[--j] > pivot); if ( i < j) swap (v[i], v[j]); else break; } swap(v[i], v[high-1]); cout << "\nafter partition " << endl; for (int k=low; k <= high; k++) cout << v[k] << " "; quicksort(v , low, i-1); quicksort(v , i+1, high); } } } void mergesort( vector & v, int low, int high) { if (low < high) { int middle = (low + high) / 2; mergesort(v, low,middle); mergesort(v, middle+1,high); merge( v , low , middle,high); } } void merge( vector & v, int low, int middle, int high) { cout << "merge with low = " << low << " and high = " << high << endl; for (int i=low; i<=high;i++) cout << v[i] << " "; vector tem(high-low+1); int lowin = low, highin = middle + 1, temin = 0; while (lowin <= middle && highin <= high) { if (v[lowin] < v[highin]) tem[temin++] = v[lowin++]; else tem[temin++] = v[highin++]; } while (lowin <= middle) { tem[temin++] = v[lowin++]; } while ( highin <= high) { tem[temin++] = v[highin++]; } for (int i=0; i < high-low+1; i++) v[low+i] = tem[i]; for (int i=low; i<=high;i++) cout << v[i] << " "; cin.get(); } void badsort( vector & v) { while (!sorted(v)) next_permutation(v.begin(), v.end()); // random_shuffle(v.begin(),v.end()); } bool sorted(const vector & v) {static int counter = 0; cout << "counter = " << counter++ << endl; bool ok = true; for (int i=1; ok && i v[i]) ok = false; return ok; } ostream & operator<<(ostream & out , const vector & v) { for (int i=0 ; i< v.size(); i++) out << (i%5? ' ' : '\n') << setw(8) << v[i] ; return out; } ```

Use this form to tell us if this entry should be deleted (i.e contains no code, is a virus, etc.).
This submission should be removed because:

What do you think of this code (in the Beginner category)?
(The code with your highest vote will win this month's coding contest!)
Excellent  Good  Average  Below Average  Poor (See voting log ...)