// ------------------------------------------------------------------------
  // This program is complementary material for the book:
  //
  // Frank Nielsen
  //
  // Visual Computing: Geometry, Graphics, and Vision
  //
  // ISBN: 1-58450-427-7
  //
  // Charles River Media, Inc.
  //
  //
  // All programs are available at www.charlesriver.com/visualcomputing/
  //
  // You may use this program for ACADEMIC and PERSONAL purposes ONLY. 
  //
  //
  // The use of this program in a commercial product requires EXPLICITLY
  // written permission from the author. The author is NOT responsible or 
  // liable for damage or loss that may be caused by the use of this program. 
  //
  // Copyright (c) 2005. Frank Nielsen. All rights reserved.
  // ------------------------------------------------------------------------
   
  // ------------------------------------------------------------------------
  // File: linkedlist.cpp
  // 
  // Description: Simple templated linked list class
  // ------------------------------------------------------------------------
  
  include <stdafx.h>
  include <fstream>
  
  using namespace std;
  
  template <class item> int PartitionInPlace(item array[], int left, int key, int right);
  
  template <class item> inline void Swap(item &a, item &b)
  {
  item tmp;
  
  tmp=a;
  a=b;
  b=tmp;
  }
  
  template <class item> item SelectElement(item *array, int left, int right, int k)
  {
  int e,key;
  
  if(right > left) 
    {// Uniform random key
          key=left+(rand()%(right-left+1)); 
          e=PartitionInPlace(array,left,key,right);
          
          // Recursion
          if (k<=e) return SelectElement(array,left,e,k);
          else
                  SelectElement(array,e+1,right,k);
    }
          else // right=left
                  return array[left];
  }
  
  define N 20000
  template <class item> void QuickSortRandom(item array[], int n);
  
  int _tmain(int argc, _TCHAR* argv[])
  {
          int *array, *arrays;
          int kth,k;
  
          
  cout<<"Visual Computing: Geometry, Graphics, and Vision (ISBN:1-58450-427-7)"<<endl;
  cout<<"Demo program\n\n"<<endl;
  
          cout<<"Randomized Algorithm: Select"<<endl;
  
          array=new int[N];
          arrays=new int[N];
  
          for(int i=0;i<N;i++) {array[i]=rand();arrays[i]=array[i];}
  
          for(int round=0;round<30;round++)
          {
  
          k=1+(rand()%(N-1));
  kth=SelectElement(array,0,N-1,k-1);
  
  cout <<"The "<<k<<"th smallest element is "<<kth<<endl;
  
  QuickSortRandom(arrays,N);
  
  cout <<"I check that "<<kth<<" = " << arrays[k-1]<<endl;
  
  char line[256];
  cout<<"Press Return key"<<endl;
  gets(line);
          }
  
  delete [] array;
  delete [] arrays;
  
  cout<<"Press a key + <Return>"<<endl;
  char toto;cin>>toto;
  
          return 0;
  }
  
  template <class item> int PartitionInPlace(item array[], int left, int key, int right)
  {
  item pivot;
  int i,j;
  
  Swap(array[right],array[key]);
  pivot = array[right]; 
  i = left-1; 
  j = right;
      for(;;) 
            {
        while(array[++i] < pivot);
        while(array[--j] > pivot);
        if(i >= j) break;
        Swap(array[i], array[j]);
            }
      Swap(array[i],array[right]);
  
  return i;
  }
  
  template <class item> void QuickSort(item array[], int left, int right)
  {
    int e,key;
  
    if(right > left) 
    {
          // Uniform random key
          key=left+(rand()%(right-left+1)); 
          e= PartitionInPlace(array,left,key,right);
  
          // Recursive calls
      QuickSort(array,left,e-1);
      QuickSort(array,e+1,right);
    }
  }
  
  template <class item> void RandomPermutation(item array[], int n)
  {
          int i,j;
          item tmp;
  
          for(i=1;i<n;i++)
          {
          j=rand()\%i; // uniform random integer from 0 to i (included)
          Swap(array[i],array[j]);
          }
  }
  
  template <class item> void QuickSortRandom(item a[], int n)
  {
  RandomPermutation(a,n);
  QuickSort(a,0,n-1);
  }