How to find median of three points (unsorted) in a generic type of array?

Question

I'm trying to find the median of a[p], a[r], and a[q] where q = r+p/2. My program crashes even though it worked before I created the median method, so I'm assuming there's something wrong. Does anyone know what is wrong?

This is what it shows when I run my program:

Welcome to DrJava.  Working directory is C:\coding
> run QuickSort
[5, 2, 7, 3, 9, 7, 10, 3, 6, 3, 7, 2, 6, 7, 2, 1]
java.lang.StackOverflowError
    at QuickSort.partition(QuickSort.java:39)
    at QuickSort.qSort(QuickSort.java:13)
    at QuickSort.qSort(QuickSort.java:13)
    at QuickSort.qSort(QuickSort.java:13)
    .
    .
    .
    at QuickSort.qSort(QuickSort.java:13)
    at QuickSort.qSort(QuickSort.java:13)
> 

And the last line keeps repeating.

Complete code:

import java.util.*;

public class QuickSort {
public static void main(String[] args) {
  Integer[] vals = new Integer[]{5,2,7,3,9,7,10,3,6,3,7,2,6,7,2,1};
  System.out.println(Arrays.toString(vals));
  qSort(vals,0,vals.length-1);
  System.out.println(Arrays.toString(vals));
}
public static <T extends Comparable<T>> void qSort(T[] a, int p, int r){
  if(p < r){
    int q = partition(a,p,r);
    qSort(a,p,q);
    qSort(a,q+1,r); 
  }
}
public static <T extends Comparable<T>> T median(T[] a, int p, int r){
  int q = r+p/2;
  if (a[p].compareTo(a[q]) > 0){
    if (a[q].compareTo(a[r]) > 0){
      return a[q];
    }
    else if (a[p].compareTo(a[r]) > 0){
      return a[r];
    } else{
      return a[p];
    }
  }else{
    if (a[p].compareTo(a[r]) > 0){
      return a[p];
    } else if (a[q].compareTo(a[r]) > 0){
      return a[r];
    } else{
      return a[q];
    }
  }
}
public static <T extends Comparable<T>> int partition(T[] a, int p, int r){
  T pivot = median(a,p,r);
  int i = p-1;
  int j = r+1;
  while(true){
    do{
      i++;
    }
    while(i<=r && a[i].compareTo(pivot) < 0);
    do{
      j--;
    }
    while(j>=p && a[j].compareTo(pivot) > 0);
    if(i<j){
      swap(a,i,j);
    }
    else{
      return j;
    }
  }
}
public static <T extends Comparable<T>> void swap(T[] a, int i, int j){
  T temp = a[i];
  a[i] = a[j];
  a[j] = temp;
}
}

Answer 1

I believe you meant to say:

  int q = (r+p)/2;