fork(54) download
copy 
  1. #include <iostream>
  2. #include <algorithm>
  3.  
  4. void print(int *a, int n)
  5. {
  6.     int i = 0;
  7.     while(i < n){
  8.         std::cout << a[i] << ",";
  9.         i++;
  10.     }
  11.     std::cout << "\n";
  12. }
  13.  
  14. int partition(int *arr, const int left, const int right) {
  15.     const int mid = left + (right - left) / 2;
  16.     const int pivot = arr[mid];
  17.     // move the mid point value to the front.
  18.     std::swap(arr[mid],arr[left]);
  19.     int i = left + 1;
  20.     int j = right;
  21.     while (i <= j) {
  22.         while(i <= j && arr[i] <= pivot) {
  23.             i++;
  24.         }
  25.  
  26.         while(i <= j && arr[j] > pivot) {
  27.             j--;
  28.         }
  29.  
  30.         if (i < j) {
  31.             std::swap(arr[i], arr[j]);
  32.         }
  33.     }
  34.     std::swap(arr[i - 1],arr[left]);
  35.     return i - 1;
  36. }
  37.  
  38. void quicksort(int *arr, const int left, const int right, const int sz){
  39.  
  40.     if (left >= right) {
  41.         return;
  42.     }
  43.  
  44.  
  45.     int part = partition(arr, left, right);
  46.     std::cout << "QSC:" << left << "," << right << " part=" << part << "\n";
  47.     print (arr, sz);
  48.  
  49.     quicksort(arr, left, part - 1, sz);
  50.     quicksort(arr, part + 1, right, sz);
  51. }
  52.  
  53. int main() {
  54.     int arr[8] = {110, 5, 10,3 ,22, 100, 1, 23};
  55.     int sz = sizeof(arr)/sizeof(arr[0]);
  56.     print(arr, sz);
  57.     quicksort(arr, 0, sz - 1, sz);
  58.     print(arr, sz);
  59.     return 0;
  60. }
  61.  
Success #stdin #stdout 0s 3140KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
110,5,10,3,22,100,1,23,
QSC:0,7 part=1
1,3,10,110,22,100,5,23,
QSC:2,7 part=4
1,3,10,5,22,100,110,23,
QSC:2,3 part=3
1,3,5,10,22,100,110,23,
QSC:5,7 part=7
1,3,5,10,22,23,100,110,
QSC:5,6 part=5
1,3,5,10,22,23,100,110,
1,3,5,10,22,23,100,110,
https://ideone.com/ImMUH4
language:
C++14 (gcc 8.3)
created:
9 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!