Testing Sort Array Methods

Question

I'm writing a program that tests if a sort function sorts a program properly. I have to have it test the quick sort and merge sort methods. Also it must ask the user which method they would like to test and make an array of random objects. Why won't my program run properly? It just spits out the same array for the quick sort and it randomly re arranges them for the merge sort. Is the problem my sorting methods or my tester method? Someone please help.

import java.util.Random;
import java.util.Scanner;

public class sortArrays {
    public static void main (String[] args)
    {
        Random gen = new Random();
        int[] a = new int[20];
        Scanner reader = new Scanner(System.in);
        String choice;
        int left = a[0];
        int right = a[19];
        int[] buffer = new int [a.length];

        for (int i = 0; i < a.length; i++)
            a[i] = gen.nextInt(100);

        printArray(a);

        System.out.println("Type quick to test the quick sort method.");
        System.out.println("Type merge to test the merge sort method.");
        choice = reader.nextLine();

        if (choice.equals("quick"))
            quickSort(a, left, right);
        else if (choice.equals("merge"))
            mergeSort(a, buffer, 0, 9, 19);

        printArray(a);

    }


    private static void printArray(int[] a)
    {
        for(int i : a)
            System.out.print(i + " ");
        System.out.println("");
    }


    private static void quickSort (int[] a, int left, int right)
    {
        if (left >= right) return;

        int i = left;
        int j = right;
        int pivotValue = a[(left + right) / 2];

        while (i < j)
        {
            while (a[i] < pivotValue) i++;
            while (pivotValue < a[j]) j--;
            if (i <= j)
            {
                int temp = a[i];
                a[i] = a[j];
                a[j] = temp;
                i++;
                j--;
            }
        }
        quickSort(a, left, j);
        quickSort(a, i, right);
    }


    private static void mergeSort(int[] a, int[] copyBuffer, int low, int middle, int high)
    {
        int i1 = low, i2 = middle + 1;

        for(int i = low; i <= high; i++)
        {
            if(i1 > middle)
                copyBuffer [i] = a[i2++];
            else if(i2 > high)
                copyBuffer[i] = a[i1++];
            else if(a[i1] < a[i2])
                copyBuffer[i] = a[i1++];
            else
                copyBuffer[i] = a[i2++];
        }

        for(int i = low; i <= high; i++)
            a[i] = copyBuffer[i];
    }


}

Answer 1

Well, your printArray() looks OK, but one thing stands out right away:

The initial parameters you are passing to quickSort() are incorrect. You have:

int[] a = new int[20];
...
int left = a[0];
int right = a[19];
...
quickSort(a, left, right);

You are initializing left and right to 0, and thus you end up calling quickSort(a, 0, 0) (not what you want). You probably mean to do this instead, as left and right hold the index:

int left = 0;
int right = 19;

Or simply:

quickSort(a, 0, 19);

As for your mergeSort(), the implementation is simply incomplete. It appears you have implemented the "merge" operation (an essential piece of the algorithm), but not the "merge sort" overall algorithm. You may want to check out Mergesort in Java (for examples) or Merge Sort (for general overview).

By the way, you may wish to specify a.length - 1 instead of 19, that way you can change the size of a without having to modify other code (same would go for the 9 you pass to mergeSort(), but that is moot as you will see it is unnecessary once you implement the algorithm fully).