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

Play multiple different notification sounds from app

android ios cordova push-notification

Is it possible for an iOS or android app to launch a system notification. And have the sound played by the notification change depending on some criteria?

get cpu usage in a script in osx

ruby osx system cpu-usage

On linux, I can get the current CPU usage out of /proc/stat; is there an equivalent for OSX? Or some utility that returns easy-to-parse and consistent output? I need it in a Ruby program.

About UNIX Resources Network

Original, collect and organize Developers related documents, information and materials, contains jQuery, Html, CSS, MySQL, .NET, ASP.NET, SQL, objective-c, iPhone, Ruby on Rails, C, SQL Server, Ruby, Arrays, Regex, ASP.NET MVC, WPF, XML, Ajax, DataBase, and so on.