0

This is a quick sort as you know and I want to optimize it in itself arrayList and don't want to use another array or using linkedList. Suppose that the half numbers of array was sorted in ascending order and others are in among them.I mean optimization is less swap in code that depends on where does choose a pivot or change the partition function.if you know how I should optimize it please help me.total of count variable is a number of swap if I write it true. Thanks!

public class Quick {  
    public static void main(String[] args) {  
        int[] a = {4,6,0,7,1,12,2,18,4,9,4,13,5,6};  
        sort(a,0,a.length - 1);

        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + " ");
        }
    }

    static void sort(int[] a, int lo, int hi){
        if(lo < hi){
            int j = partiton(a ,lo ,hi);
            sort(a, lo ,j - 1);
            sort(a, j + 1, hi);
        }
    }

    static int partiton(int[] a, int lo, int hi){
        int i = lo; int j = hi + 1;
        int v = a[lo];
        int count = 0;

        while(true){
            while(a[++i] <  v){
                if (i == hi)
                    break;
            }

            while(v < a[--j]){
                if (j == lo)
                    break;
            }

            if (i >= j){
                break;
            }
            swap(a, i, j);
            count = count + 1;
        }
        swap(a, lo, j);
        count = count + 1;
        System.out.println("swap : " + count);

        return j;


    }

    static void swap(int[] a, int i, int j){
        int temp = 0;
        temp = a[j];
        a[j] = a[i];
        a[i] = temp;
    }

}
David Duponchel
  • 3,959
  • 3
  • 28
  • 36
Samin
  • 9
  • 1
  • What you want to do is quick sort in place, Please check these answers: http://stackoverflow.com/questions/29609909/inplace-quicksort-in-java?noredirect=1&lq=1 and http://stackoverflow.com/questions/29609909/inplace-quicksort-in-java – dbustosp Feb 26 '17 at 21:41
  • Quick sort is normally in place and doesn't use an auxiliary array, but it does use stack space, O(n) worst case or O(log(n)) by only using recursion on the smaller partition and looping for the larger partition. The issue with somewhat sorted data is choosing a pivot, and I'm not aware of an optimizing algorithm for this. Using median of 3 helps, but worst case time complexity is still O(n^2). Using median of medians helps worst case time complexity, but the typical case is slower. – rcgldr Feb 26 '17 at 22:00

0 Answers0