# Quicksorting trouble

I am working on a quicksort but for some reason i end up with the same issues. Somehow even when i copy/paste quicksort code that is supposed to work, I always get a value of 0 inserted somewhere in the array.

public class quicksort { public int[] x; public quicksort(int a[]){ x=a; procedure(0, x.length-1); } public void procedure(int left, int right){ int index=left; int smaller=left+1;//going to sort everything but the first element (the pivot or index) int larger=right; int divider=x[index]; while (smaller <= larger){ for (int z=0; z<x.length-1;z++){//display the array at each pass System.out.print(x[z]+" ,"); } System.out.println("|| "+smaller+" "+divider+" " +larger+" ||"); while(x[larger] > divider ){ //stops at smaller then divider coming from the right larger--; } while(x[smaller] < divider){//stops at bigger then divider coming from the left smaller++; } if (smaller<=larger){//swaps two elements swap(smaller, larger); smaller++; larger--; } } index= smaller + insert(left, smaller);//moves index to its final spot in the array //recursive call, split the array by the position of index and sort each if (index < right-1) procedure(index+1, right); if (index > left+1) procedure(left, index-1); } public void swap(int z, int y){//swaps values between 2 array indexes int temp; temp =x[z]; x[z]=x[y]; x[y]=temp; } public int insert(int z, int y){//inserts a value from one index to the another index in the array, adjusts array as neccessary int it=0; if (x[z]>x[y]){ //if values are the same => easy swap swap(z,y); it=0; } else if (x[z] <= x[y]){ //if trying to insert to a bigger value for (int f =z; f>y-1;f++) //will swap values from the position z to swap(f, f+1); //position y (only works if z<y) it=-1; } return it; } }

I know that I am also overflowing the recursive call, but first i want to find out why the swapping is not taking place accordingly. The output there is just so i can see what is happening to the array after every pass on the while loop. This is a sample debug of a 10 integer array.

24 ,37 ,8 ,41 ,76 ,36 ,1 ,73 ,20 ,|| 1 24 9 || 24 ,0 ,8 ,41 ,76 ,36 ,1 ,73 ,20 ,|| 2 24 8 || 24 ,0 ,8 ,20 ,76 ,36 ,1 ,73 ,41 ,|| 4 24 7 || 24 ,0 ,8 ,20 ,1 ,36 ,76 ,73 ,41 ,|| 5 24 5 ||

## Answers

First of all, this code looks extremely complicated as for a quicksort. It appears you want to implement Lomuto version, but there are at least a few unusual things in your code.

For implementing a quicksort yourself I would strongly recommend reading about Lomuto Quicksort, and see the typical way it is implemented. In such version, you get:

-> function partition (which takes your array, selects a pivot and then **returns an index**, at which your pivot is inserted after all elements <= pivot are to its left and all elements > pivot are to its right).

-> function quicksort which will be called recursively to sort partial-arrays, to the left of the pivot and to the right of the pivot.

Lomuto Quicksort is often considered to be easier to understand than the original one, designed by C.A.R. Hoare. However, you may try to use Hoare's quicksort as well to get even smaller code.

void quickSort(int left, int right, int tab[]){ int i = left; int j = right; int buffer; int pivot = tab[(i+j)/2]; do{ while (tab[i] < pivot) i++; while (tab[j] > pivot) j--; if (i <= j){ buffer = tab[i]; //swap. tab[i] = tab[j]; tab[j] = buffer; i++; j--; } } while (i <= j); if (left < j) qs(left, j, tab); if (i < right) qs(i, right, tab); }