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);
}

Need Your Help

Convert hex string to long

objective-c cocoa string hex

Are there any Cocoa classes that will help me convert a hex value in a NSString like 0x12FA to a long or NSNumber? It doesn't look like any of the classes like NSNumberFormatter support hex number...