QuickSort with Random and median

Question

I am working on an assignment with QuickSort to show how fast the algorithm when using different methods for getting the Pivot like random or median of three. so far when using random or median I get different outputs and none of them is sorted, I couldn't figure out what my mistakes are. I went every where on the internet. Can someone looks at it and tell me what I'm doing wrong here?

Here is the QuickSort code:

import java.util.*;
public class QuickSort {

  public static void main(String[] args) { 
    int[] arr = {5, -32, 12, 43, 88, 19, 113, 62, -11, 2};
    System.out.println(Arrays.toString(arr));
    quickSort(arr);
    System.out.println(Arrays.toString(arr));
  }

  public static void quickSort(int[] arr) {
    quickSort1(arr, 0, arr.length -1);
  }

  private static void quickSort1(int[] list, int first, int last) {
    if (first < last) {
      int pivotLocation = partition(list, first, last);
      quickSort1(list, first, pivotLocation - 1);
      quickSort1(list, pivotLocation + 1, last);
    }
  }

  private static int partition(int[] list, int first, int last) {
    int pivot;
    int smallIndex;
    Random rand = new Random();
    int num = rand.nextInt(list.length);
    swap(list, first, (first + last) / 2);   
    pivot = list[first];
    //pivot = medianOfThree(list, first, last);
    //pivot = list[num];
    smallIndex = first;
    for (int index = first + 1; index <= last; index++) {

       if (list[index] < pivot) {
          smallIndex++;
          swap(list, smallIndex, index);        // Should we limit to if(smallIndex != index)
       }
    }
    swap(list, first, smallIndex);
    return smallIndex;
 }

 private static void swap(int[] list, int first, int second) {
    int temp;
    temp = list[first];
    list[first] = list[second];
    list[second] = temp;
 } 

 private static int medianOfThree(int[] arr, int first, int last) {
    int f = arr[first], l = arr[last], m = arr[(last + first)/2];
    if(l <= f && l >= m || l >= f && l <= m)
      return l;
    else if (m <= f && m >= l || m >= f && m <= l)
      return m;
    return f;
 }

}

I tried using while() it was faster but I have to test the speed of the sort with looping 100+ times which gave mejava.lang.StackOverflowError. Any piece of advice will be helpful.

Edit: I have fixed the median method and the random, thanks for the help.

I was working on the while loop and I figured how to make it work and sort properly. The problem now is, whenever I try to make large array to test the speed of the sorting it gets stack and I'm not sure (by large I mean 10,000 elements).

I call the class from another program but it's still not working as expected.

here is the partition method, the class is the same:

private static int partition(int[] list, int first, int last) {
  Random rand = new Random();

  int pivot = 0;
  int num = first + rand.nextInt(last - first + 1);// generates random index 
  pivot = medianOfThree(list, first, last);        //finding median of three numbers
  //pivot = list[first];                           //using the first data as pivot
  //pivot = list[num];                            //Random index value is used as pivot

  int leftPointer= first  ;
  int rightPointer = last ;
  //swap(list, last, (first+last)/2);
  while(true) {

  while (list[leftPointer] < pivot)
    leftPointer++;
  while (rightPointer > 0 && list[rightPointer] > pivot)
    rightPointer--;
  if(leftPointer >=rightPointer)
    break;
  swap(list, leftPointer, rightPointer);
  //count++;
  //System.out.println(Arrays.toString(list)+ "switch"+ count );
}

//System.out.println(Arrays.toString(list));
//swap(list, last, leftPointer);
//System.out.println(leftPointer);
return leftPointer;
}

Edit:

this is the Test code I'm using to test sorting efficiency and the QuickSort using whileloop is still not working as it should, am I doing something wrong?

Test code:

import java.util.*;
public class Test {

  public static final int ARRAYSIZE = 50000;        // Test array element count
  public static final int ELEMENTSIZE = 10000;      // Test array element size
  public static final int LOOPS = 1000;

  public static void main(String[] args) { 
    long t1=0,t2=0,t3=0;
    long c1=0,c2=0;  // Counters
    for(int test = 1; test <= LOOPS; test++) {
     System.out.print(test + "..");
     Random rand = new Random();
     int[] arr1 = new int[ARRAYSIZE];

     for(int i = 0; i < ARRAYSIZE; i++)             // Generate a random array with ARRAYSIZE elements
       arr1[i] = rand.nextInt(ELEMENTSIZE);        

     int[] arr2 = Arrays.copyOf(arr1, arr1.length); // Use an exact array copy for each sorting test
     int[] arr3 = Arrays.copyOf(arr1, arr1.length);


     t1 = System.currentTimeMillis();
     QuickSort.quickSort(arr1);                //Run & Time Quick Sort
     t2 = System.currentTimeMillis();
     Arrays.sort(arr3);                         //Run & Time Arrays.sort
     t3 = System.currentTimeMillis();

     c1 += t2-t1; 
     c2+=t3-t2; 


   }
    System.out.println();
    System.out.println("Quick Sort took: " + c1/LOOPS + " milliseconds");
    System.out.println("Arrays.sort took:    " + c2/LOOPS + " milliseconds");

  }

  /* ADD YOUR CODE HERE */

}

Answer 1

I spotted at least two mistakes, there are probably others. For the selection of a random element you should use something like:

int num = first + rand.nextInt(last - first + 1);

For the median of three the middle element is:

int m = arr[(last + first)/2];

I suggest you run the program with a debugger and convince yourself after each step that the correct thing was done.

Answer 2

I have found the problem with the code, Whenever it compare the exact same Value, it keeps switching and compare them again... so I made a condition to break the loop whenever that occurs. I used :

if(leftPointer >=rightPointer || list[leftPointer]==  list[rightPointer])
  break;
else 
  swap(list, leftPointer, rightPointer);

instead of:

if(leftPointer >=rightPointer)
  break;
else 
  swap(list, leftPointer, rightPointer);

The sort works fine.

-Thanks