I am attempting to initialize an int[] array of 10 random numbers. Then choose a pivot value from the array. I then place this value in the first position of the array. Then call quicksort on the array, which will call a partition method. This method returns the final index of the pivot. Then quicksort is recursively called on both pieces of the array.

My partition method works, at least for the first call. But somewhere there is a mistake, and the final array ends up only partially sorted. I have added lots of print statements to make it easier to debug, but I cant figure it out. Any idea? And occasionally I get a arrayOutOfBound exception, but it is a random event and I think it has something to do with choosePivot.

import java.io.IOException;
import java.util.*;

public class test {

    public static void main (String[] args) throws IOException{
 		//create inital random array, then print it   
    	int[] myarray=randomArray(10);
    	
    	System.out.println("original arrray:");
    	for (int i=0; i<myarray.length; i++)
    		System.out.print(myarray[i]+" ");
    	System.out.println("");
    	
    	//move the pivot to the first position, then print again
    	swap(myarray, 0, choosePivot(myarray, 0, 9));	
    	
    	System.out.println("Swapped arrray:");
    	for (int i=0; i<myarray.length; i++)
    		System.out.print(myarray[i]+" ");
    	System.out.println("");
    	
    	//call quicksort on full array
    	QuickSort(myarray, 0, 9);
    	
    	//final array prints here
    	System.out.println("final arrray:");
    	for (int i=0; i<myarray.length; i++)
    		System.out.print(myarray[i]+" ");
    	System.out.println("");
    }
    
    
    public static void QuickSort(int[] array, int left, int right){
    	if (right-left <= 1)
    		return;
    	if (right>left){
    			
    		int index=partition(array, left, right);
    		QuickSort(array, left, index-1);
    		QuickSort(array, index+1, right);
    	}
    }
    
    public static int partition(int[] array, int left, int right){
    	int i = left+1, j = right;
    	//start from each end of the array checking values.
    	//compares values to array[0] which holds the pivot. 
    	//swap them as necessary
    	while (i<=j){
    		while (array[i]<array[left]){
    			i++;
    		}
    		
    		while (array[j]>array[left]){
    			j--;
    		}
    		
    		if (i<=j){
    			swap (array, i, j);
    			i++;
    			j--;
    		} 
    	}
    	//i and j crossed, so move the pivot into it's proper spot.
    	if (i>j) {
    		swap (array, 0, j);
    		//prints parted array each interation, and index of pivot
    		System.out.println("Parted array:");
    			for (int k=left; k<=right; k++)
    		System.out.print(array[k]+" ");
    		System.out.println("j="+j);
    		//the pivot must be chosen and moved to first position again before quicksort
    		swap (array, left, choosePivot(array, left, j-1));
    		swap (array, j+1,  choosePivot(array, j+1, right));
    		
    	}
    	//prints array that will be used in recursive call
    	System.out.println("calling this array, all elements before j belong to first sub array. all elements after j are in second subarray:");
    	for (int k=left; k<=right; k++)
    		System.out.print(array[k]+" ");
    	System.out.println("j="+j);
    	return j;
    }
	
	//ARRAY INDEX SWAP
	//simple array index swap method
	public static void swap(int[] intArray, int dex1, int dex2) {
    int temp = intArray[dex1];
    intArray[dex1] = intArray[dex2];
    intArray[dex2] = temp;
  }    
    //RANDOM ARRAY
    //method to create random int array of size n.
     public static int[] randomArray (int n) {
      Random randNumGenerator = new Random();
      int[] array = new int[n];
        for (int i = 0; i<array.length; i++) {
          array[i] = (randNumGenerator.nextInt(100));
        }
    return array;
    }
   
    //CHOOSE PIVOT
    //compare the first, last, and middle elements of the array.  Return the index of the median value of these three
    //this is the pivot
     public static int choosePivot (int[] array, int first, int last){
    	
    	int mid = (first + last ) / 2;
    	
    	if (array[first]>array[mid]&&array[mid]>array[last])
    		return mid;
    	if (array[mid]>array[first]&&array[first]>array[last])
    		return first;
    	if (array[mid]>array[last]&&array[last]>array[first])
    		return last;
    	if (array[first]<array[mid]&&array[mid]<array[last])
    		return mid;
    	if (array[mid]<array[first]&&array[first]<array[last])
    		return first;
    	if (array[mid]<array[last]&&array[last]<array[first])
    		return last;
    	if (array[first]==array[last] || array[first]==array[mid] || array[mid]==array[last])
    		return mid;
    	
    	return -1;
    	}
}

After further debugging, I think the problem occurs somewhere after the recursive call on the right part of the array. Everything up to here works, then this is called and is screws up the sorted part.

not sure am really bad at this but we have been doing quicksort

we use QuickSort.sort(etc etc) it works and so guess it is part of the util library?? should probably shut up as am real bad novice

was looking at your argument though in QuickSort and not sure it holds enough water

line 35
if (right-left <= 1) return; // if lower or equal to one
if (right>left){ // if right higher than left but could be higher by one so you got a bit of a fight going on or maybe you got that covered elsewhere

also excuse my ignorance is the swap() thing being declared anywhere or is that another util thing?

Thanks for taking a shot at it. I ended up redoing my partition method a different way and it works now. I had to use some psuedocode to get it right, but this code here was from my head, so I would still like to know where I went wrong.

This article has been dead for over six months. Start a new discussion instead.