// Quicksort: carries out quicksort
public class Quicksort {




   public void quicksort(double[] A, int p, int r) {

      if (p < r) {
         int q = partition(A,p, r);
         quicksort(A,p, q-1);
         quicksort(A,q+1, r);
       }
   }

   private int partition(double[] A, int p, int r) {

      double x = A[r];
      int i = p - 1;

      for (int j = p; j < r; j++) {
         if (A[j] <= x) {
            i++;
            exchange(A,i, j);
         }
      }
      exchange(A, i+1, r);
      return i + 1;
   }

   private void exchange(double[] A, int i, int j) {
      double temp = A[i];
      A[i] = A[j];
      A[j] = temp;
   }


   public boolean isSorted(double[] A) {
      for (int i = 0; i < A.length - 1; i++)
         if (A[i] >= A[i+1]) return false;
      return true;
   }
}
// QuicksortTest.java:
import java.util.*;
public class QuicksortTest {
   private int size;
   private double A[];
   private Quicksort q;
   private Random r;

   public QuicksortTest(int s) {
      size = s;
      A = new double[size];
      q = new Quicksort();
      r = new Random(314159265);
   }

   public void randomTest() {
      long startTime = System.currentTimeMillis();
      System.out.println("Number of items: " + size);
      for (int i = 0; i < A.length; i++)
         A[i] = r.nextDouble();
      elapsedTime(startTime, "After generating, ");
      q.quicksort(A, 0, A.length - 1);
      elapsedTime(startTime, "After sorting, ");
      System.out.println("isSorted = "+q.isSorted(A));
   }

   private void elapsedTime(long startTime, String s){
      long stopTime = System.currentTimeMillis();
      double elapsedTime = ((double)(stopTime -
         startTime))/1000.0;
      System.out.println(s + "elapsed time: " +
         elapsedTime + " sec");
   }

   public static void main(String[] args) {
      final int SIZE = 5120000;
      QuicksortTest qt = new QuicksortTest(SIZE);
      qt.randomTest();
   }
}

// quicksort.h
void quicksort(double[] , int , int );
int issorted(double[], int );
// quicksort.c: C separate file for ADT
#include <stdio.h>
#include "quicksort.h"

// "static"  means "private"
static int partition(double[], int, int );
 
void quicksort(double A[], int p, int r) {
   int q;
   if (p < r) {
      q = partition(A, p, r);
      quicksort(A, p, q-1);
      quicksort(A, q+1, r);
   }
}

static int partition(double A[], int p,
      int r) {
   double x = A[r];
   int i = p - 1;
   int j;
   for (j = p; j < r; j++) {
      if (A[j] <= x) {
         i++;
         exchange(A, i, j);
      }
   }
   exchange(A, i+1, r);
   return i + 1;
}

static void exchange(double A[], int i,
      int j) {
   double temp = A[i];
   A[i] = A[j];
   A[j] = temp;
}

int issorted(double A[], int len) {
   int i;
   for (i = 0; i < len - 1; i++)
      if (A[i] >= A[i+1]) return 0;
   return 1;
}
// quicksorttest.c
#include <stdio.h>
#include <math.h> // for floor
#include "quicksort.h"
#define SIZE 640000

double seed = 11111.0;
double rand();

int main() {
   double A[SIZE];
   int i;
   printf("Number of items: %i\n", SIZE);
   for (i = 0; i < SIZE; i++) {
      A[i] = rand();
   }
   quicksort(A, 0, SIZE - 1);
   printf("issorted=%i\n",
      issorted(A, SIZE ));
}

double rand() {
   double a = 16807.0,
          m = 2147483647.0;
   double q;
   seed = a*seed;
   q = floor(seed/m);
   seed = seed - q*m;
   return(seed/m);
}

Number of items: 80000
After generating, elapsed time: 0.031 sec
After sorting, elapsed time: 0.062 sec
isSorted = true
Number of items: 160000
After generating, elapsed time: 0.053 sec
After sorting, elapsed time: 0.113 sec
Number of items: 320000
After generating, elapsed time: 0.095 sec
After sorting, elapsed time: 0.206 sec
Number of items: 640000
After generating, elapsed time: 0.183 sec
After sorting, elapsed time: 0.422 sec
Number of items: 1280000
After generating, elapsed time: 0.36 sec
After sorting, elapsed time: 0.834 sec
Number of items: 2560000
After generating, elapsed time: 0.717 sec
After sorting, elapsed time: 1.678 sec
Number of items: 5120000
After generating, elapsed time: 1.406 sec
After sorting, elapsed time: 3.44 sec