fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int arr[] = {14,4,5,21,1,33,23},
  6.  
  7.     n = sizeof( arr )/sizeof( arr[ 0 ] );
  8.  
  9. int partition(int lo, int hi) {
  10.  
  11.     int j = lo - 1;
  12.     int pivot = arr[hi];
  13.     for(int i = lo; i <= hi; ++i) {
  14.         if(arr[i]<=pivot) {
  15.           j++;
  16.           int temp = arr[j];
  17.           arr[j]=arr[i];
  18.           arr[i] = temp;
  19.         }
  20.     }
  21.  
  22.     return j;
  23. }
  24.  
  25. void quicksort(int lo, int hi) {
  26.      int piv = partition(lo, hi);
  27.      if(lo<piv-1) quicksort(lo, piv-1);
  28.      if(piv+1<hi) quicksort(piv+1,hi);
  29. }
  30.  
  31. int select(int kmin, int lo, int hi) {
  32.  
  33.     int pivot = partition(lo, hi);
  34.  
  35.     if(pivot == kmin-1) {
  36.  
  37.        return arr[pivot];
  38.  
  39.     } else if(kmin-1 > pivot)
  40.  
  41.       return select(kmin,pivot+1,hi);
  42.  
  43.       return select(kmin, lo, pivot-1);
  44.  
  45.  
  46. }
  47.  
  48. int main(int argc, char const *argv[]) {
  49.  
  50.   for(int i = 0; i < n; ++i) cout<<arr[i]<<" ";
  51.  
  52.   cout<<endl;
  53.  
  54.   quicksort(0, n-1);
  55.  
  56.   for(int i = 0; i < n; ++i) cout<<arr[i]<<" ";
  57.  
  58.   cout<<"\n"<<select(5, 0, n - 1);
  59.  
  60.   return 0;
  61. }
Success #stdin #stdout 0.01s 5472KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
14 4 5 21 1 33 23 
1 4 5 14 21 23 33 
21
https://ideone.com/Yd0kPv
Quicksort with partitions and select K min
language:
C++ (gcc 8.3)
created:
1 year ago
visibility:
secret

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!