fork download
copy 
  1. #include <iostream>
  2. #include <algorithm>
  3. using namespace std;
  4.  
  5.  
  6.  
  7.  
  8. //**********************************************************
  9. // partition selects the value in the middle of the *
  10. // array set as the pivot. The list is rearranged so *
  11. // all the values less than the pivot are on its left *
  12. // and all the values greater than pivot are on its right. *
  13. //**********************************************************
  14.  
  15. template <class T1>
  16. int partition(T1 set[], int start, int end) {
  17.     int pivotValue, pivotIndex, mid;
  18.  
  19.     mid = (start + end) / 2;
  20.     swap(set[start], set[mid]);
  21.     pivotIndex = start;
  22.     pivotValue = set[start];
  23.     for (int scan = start + 1; scan <= end; scan++) {
  24.         if (set[scan] < pivotValue) {
  25.             pivotIndex++;
  26.             swap(set[pivotIndex], set[scan]);
  27.         }
  28.     }
  29.     swap(set[start], set[pivotIndex]);
  30.     return pivotIndex;
  31. }
  32.  
  33. //************************************************
  34. // quickSort uses the quicksort algorithm to *
  35. // sort set, from set[start] through set[end]. *
  36. //************************************************
  37.  
  38. template <class T>
  39. void quickSort(T set[], int start, int end) {
  40.     T pivotPoint;
  41.  
  42.     if (start < end) {
  43. // Get the pivot point.
  44.         pivotPoint = partition(set, start, end);
  45. // Sort the first sub list.
  46.         quickSort(set, start, pivotPoint - 1);
  47. // Sort the second sub list.
  48.         quickSort(set, pivotPoint + 1, end);
  49.     }
  50. }
  51. //**********************************************
  52. // swap simply exchanges the contents of *
  53. // value1 and value2. *
  54. //**********************************************
  55.  
  56. template <class T>
  57. void swap(T &value1, T &value2) {
  58.     int temp = value1;
  59.  
  60.     value1 = value2;
  61.     value2 = temp;
  62. }
  63.  
  64. int main() {
  65.     const int SIZE = 10; // Array size
  66.     int count; // Loop counter
  67.  
  68. // need to override the [] function?
  69.     int array[SIZE] = {7, 3, 9, 2, 0, 1, 8, 4, 6, 5};
  70.  
  71. // Display the array contents.
  72.     for (count = 0; count < SIZE; count++)
  73.         cout << array[count] << " ";
  74.     cout << endl;
  75.  
  76. // Sort the array.
  77.     quickSort(array, 0, SIZE - 1);
  78.  
  79. // Display the array contents.
  80.     for (count = 0; count < SIZE; count++)
  81.         cout << array[count] << " ";
  82.     cout << endl;
  83.     return 0;
  84. }
  85.  
  86.  
  87.  
Success #stdin #stdout 0s 2896KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
7 3 9 2 0 1 8 4 6 5 
0 1 2 3 4 5 6 7 8 9
https://ideone.com/Ce9BEw
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!