QuickSort Algorithm naive implementation..but why doesn't it work?

Question

I am very new to programming and java so please don't laugh at this :). now..i looked over the net for the right implementation of the QuickSort algorithm and i am aware of that. but i tried to implement it myself in the very innocent,basic way i could think of. actually creating two seperate arrays(left,right) and continue to sort them and so on...

this is the code:

package excercise;

public class MyQuickSort {


    public static int list[] = {6,5,3,1,8,7,2,4};


    public static int[] addNumberToArray(int array[],int num){
        int newArray[] = new int[array.length+1];
        for(int i = 0;i<array.length;i++){
            newArray[i] = array[i];
        }
        newArray[newArray.length-1] = num;
        array = newArray;
        return array;
    }


    public static int[] partition(int arr[]){

        while(arr.length>1){
            int pivotIndex = (int)(arr.length/2);
            int left[] = new int[0];
            int right[] = new int[0];

            for(int i = 0;i<arr.length;i++){
                if(i==pivotIndex){
                    continue;
                }

                else if(arr[i]<=arr[pivotIndex]){
                    left = addNumberToArray(left,arr[i]);
                }
                else{
                    right = addNumberToArray(right,arr[i]);
                }
            }
            int origPivot = arr[pivotIndex];
            int k = 0;
            while(k<left.length){
                arr[k] = left[k];
                k++;
            }
            arr[k] = origPivot;
            k++;
            while(k<arr.length){
                arr[k] = right[k-(left.length+1)];
            }


            if(left.length>1){
            partition(left);
            }

            if(right.length>1){
            partition(right);
            }

        }

            return arr;
    }




    public static void main(String[]args){
            list = partition(list);
            for(int i = 0;i<list.length;i++){
                System.out.print(list[i]+" ");
            }

        }
    }

but why this is getting stick in a loop and don't work? i don't understand what is wrong with this code..except that this is not very efficient (to say the least)! but i am stubborn and want to try and make it work anyway..if you have any advices it will be great! thx in advance

ok,this is the new code,after debugging everything seems to work fine,but when i want to print the new sorted arr,it still prints me the original unsorted array. the recursion turn the whole thing back to where it starts. how can i make it "save the steps"? where should i put a "return" call and what should i return?

public class MyQuickSort {

    public static int list[] = {6,5,3,1,8,7,2,4};
    public static boolean sorted;
    public static int[] addNumberToArray(int arr[],int num){
        int newArr[] = new int[arr.length+1];
        for(int i = 0;i<arr.length;i++){
            newArr[i] = arr[i];
        }
        newArr[newArr.length-1] = num;
        arr = newArr;
        return arr;

    }


    public static void partition(int arr[]){

        while(!sorted){
            int pivotIndex = (int)(arr.length/2);
            int left[] = new int[0];
            int right[] = new int[0];

            for(int i = 0;i<arr.length;i++){
                if(i==pivotIndex){
                    continue;
                }
                else if(arr[i]<=arr[pivotIndex]){
                    left = addNumberToArray(left,arr[i]);
                }
                else{
                    right = addNumberToArray(right,arr[i]);
                }
            }
            int origPivot = arr[pivotIndex];
            int k = 0;
            while(k<left.length){
                arr[k] = left[k];
                k++;
            }
            arr[k] = origPivot;
            k++;
            while(k<arr.length){
                arr[k] = right[arr.length-arr.length-(left.length+1)+k];
                k++;
            }


            if(left.length>1){
                partition(left);
            }


            if(right.length>1){
                partition(right);
            }

            if(left.length<=1&&right.length<=1){
                sorted = true;

            }

        }



    }








    public static void main(String[] args) {
        partition(list);
        for(int i = 0;i<list.length;i++){
            System.out.print(list[i]+" ");
        }


    }

}

Answer 1

Cool! your implementation seem logically depicting quicksort. However, please note that quicksort is not to be implemented using additional buffers. It should be sorted in its own main array, recursing the call passing just the start and end bounds. Your implementation is more of a mergesort style, using quicksort logic. And yes, you missed the k++ as stated by the commenter above.

Answer 2

your algorithm gets stuck in this loop

while(k<arr.length){
    arr[k] = right[k-(left.length+1)];
}

the reason is that you don't increment your k.

try

while(k<arr.length){
    arr[k] = right[k-(left.length+1)];
    k++;
}