DataSection95

// Guide to Data Structures
// Section 9.5
// Copyright 2018, by J.T. Streib and T. Soma

import java.util.*;
class QuickSortGeneric {
public static void main(String[] args){
  Scanner scanner;
  scanner = new Scanner(System.in);
  int i,n;
  String str;
  String[] array = new String[20];
  SortClassGeneric<String> sortClassGeneric
     = new SortClassGeneric<String>();
  i=0;
  System.out.println();
  System.out.print("Enter a string or press enter to stop: ");
  str = scanner.nextLine();
  while(str.length() != 0) {
     array[i] = str;
     i++;
     System.out.print("Enter a string or press enter to stop: ");
     str=scanner.nextLine();
  }
  n = i;
  sortClassGeneric.quickSort(array,n);
  System.out.println();
  System.out.println("     Quick Sort");
  System.out.println();
  for(i=0; i<n; i++)
     System.out.println("     " + array[i]);
  System.out.println();
}
}

public class SortClassGeneric<T extends Comparable<T>> {

public SortClassGeneric() {
}

public void quickSort(T[] array, int n) {
  if(n>0)
     quickSort(array,0,n-1);
}

public void swapElements(T[] a, int i, int j){
  T temp;
  temp = a[i];
  a[i] = a[j];
  a[j] = temp;
}

public void sort3(T[] a, int first, int second, int third) {
  if(a[second].compareTo(a[first]) < 0)
     swapElements(a,second,first);
  if(a[third].compareTo(a[first]) < 0)
     swapElements(a,third,first);
  if(a[third].compareTo(a[second]) < 0)
     swapElements(a,third,second);
}

private void quickSort(T[] array, int left, int right) {
  int center = (left + right) / 2;
  sort3(array,left,center,right);
  if(right-left >= 3) {
     int i = left;
     int j = right;
     while(i < j) {
        do {
           i++;
        } while(i <= j && array[i].compareTo(array[center]) <= 0);
        do {
           j--;
        } while(j >= i && array[j].compareTo(array[center]) >= 0);
        if(i < j)
           swapElements(array,i,j);
     }
     int temp;
     if(i < center && j < center)
        temp = i;
     else
        if(i > center && j > center)
           temp = j;
        else
           temp = center;
     swapElements(array,temp,center);
     quickSort(array,left,temp-1);
     quickSort(array,temp+1,right);
  }
}
}