// File: kthSmallest.cpp
// Recursive find kth smallest element in an unordered array

#include <iostream>
#include <algorithm>

using namespace std;

void  choosePivot(int a[ ],int first,int last )
{  int  pivotIndex,   
        mid = (first + last) / 2;
   // set pivotIndex to the index of the middle value of
   //  a[ first ],  a[ mid ],  and  a[ last ]
   if( a[ first ] <= a[ mid ] )
     {  if( a[ mid ] <= a[ last ] )  pivotIndex = mid;
        else  pivotIndex = ( a[ first ] <= a[ last ] ? last : first );
     }
   else if( a[ last ] <= a[ mid ] )  pivotIndex = mid;
   else  pivotIndex = ( a[ first ] <= a[ last ] ? first : last );
   swap( a[ first ],  a[ pivotIndex ] );
}


void  partition(int a[ ],int first,int last,int &pivotIndex )
{  // select a pivot and place it in a[ first ]
    choosePivot( a,  first,  last );
    int pivot = a[ first ];
    int  lastS1 = first,   firstUnknown = first + 1;
    for(  ;  firstUnknown  <=  last;   firstUnknown++ )
        if( a[ firstUnknown ]  <  pivot )
        {  lastS1++;	 // swap a[ firstUnknown ] with first S2
            swap( a[ firstUnknown ],  a[ lastS1 ] );
        }
    swap( a[first], a[lastS1] );
    pivotIndex = lastS1;
}

void printList(int list[],int first,int last)
{ for (int idx=first;idx<=last;idx++)
    cout << list[idx] << " ";
}

int kthSmallest(int  k,int  a[ ],int first,int last )
{   int  pivotIndex;
    // select pivotIndex,  and partition a[first .. last] so that each
    //  element in a[first .. pivotIndex - 1]  <  a[pivotIndex],  and
    //  each element in a[pivotIndex + 1 .. last]  >=  a[pivotIndex]
    partition(a, first, last, pivotIndex);
    cout << "Pivot index is " << pivotIndex << " list is ";
    printList(a,first,last);
    cout << endl;
    int  sizeS1 = pivotIndex - first;
    if( k <= sizeS1 )
      return  kthSmallest( k,  a,  first,  pivotIndex - 1 );
    if( k == sizeS1 + 1) {
      cout << "Done...";  
      return a[ pivotIndex ];
    }
    return  kthSmallest( k - (sizeS1 + 1),  a,  pivotIndex + 1,  last );
}


int main()
{ int list[]={31,17,3,9,22,5};
  cout << "Enter k >";
  int k;
  cin >> k;
  cout << k <<"th smallest item is " << kthSmallest(k,list,0,5);
}