3
\$\begingroup\$

I'm trying to make my QuickSort faster than it is and I have got no more ideas about how to make it more efficient for all types of arrays but mostly very big arrays. It uses random to create the Pivot and it uses InsertionSort when the array is less than 15 elements. What do you think guys? I appreciate for any help here to make the code run faster.

public class QuickSort
    private static Random rand = new Random();
    public void sort(int[] v){

        QuickSort(v, 0, v.length-1);
    }

    private void QuickSort (int[] v, int first, int last) {

        if (first >= last)
            return;
        else {
            if (last - first < 15) {
                InsertionSort(v, first, last);
                return;
            }
            int[] pivotLoc = partitionArray(v, first, last, makePivot(v,first,last));
            QuickSort(v, first, pivotLoc[1]);
            QuickSort(v, pivotLoc[0], last);
        }

    }

    private int[] partitionArray (int[] v, int first, int last, int pivot) {

        while(last => first) {

            while(v[first] < pivot) first++;
            while(v[last] > pivot) last--;
            if (first > last) break;
            swap(v, first, last);
            first++;
            last--;
        }
        return new int[] {first, last};
    }

    private void swap(int[] v, int first, int last) {
        int temp = v[first];
        v[first] = v[last];
        v[last] = temp;
    }

    public void InsertionSort(int[] v, int first, int last) {
        int temp;
        for (int i=first + 1; i <= last; i++) {
            int j = i;
            while (j > 0 && v[j-1] > (v[j]) ) {
                temp = v[j];
                v[j] = v[j-1]; 
                v[j-1] = temp; 
                j--;
            }
        }
    }

    private int makePivot (int[] v, int first, int last){
        return v[rand.nextInt(last-first+1)+first];
    }

}
\$\endgroup\$
1
  • \$\begingroup\$ (1) Your implementation runs into stack overflow. (2) You omitted { after public class QuickSort. (3) There is no => in Java. \$\endgroup\$
    – coderodde
    Mar 5, 2016 at 13:33

1 Answer 1

1
\$\begingroup\$

As quick sort is a divide and conquer algorithm you can do these steps

QuickSort(v, first, pivotLoc[1]);
QuickSort(v, pivotLoc[0], last);

in parallel. Here is a good start point for this area.

PS also method swap may be reused in your InsertionSort method.

\$\endgroup\$
9
  • 2
    \$\begingroup\$ But there is a point where the overhead of the thread communication will make it slower than just throwing a single thread at it. \$\endgroup\$ Mar 4, 2016 at 16:31
  • \$\begingroup\$ @ratchetfreak what thread communication and what overhead do you mean? \$\endgroup\$ Mar 4, 2016 at 16:39
  • \$\begingroup\$ Allocating the Jobs, pushing them to a thread-safe queue, spinning up new threads if needed (which need to pull from that thread-safe queue), waiting on and collecting the "done" signals from the jobs. Only use parallelism when the individual jobs are big enough to warrant all that. \$\endgroup\$ Mar 4, 2016 at 16:53
  • \$\begingroup\$ I have heard about doing it in parallell but where I use this class doesn't allow it. \$\endgroup\$
    – Dadelante
    Mar 4, 2016 at 17:11
  • \$\begingroup\$ Good point about the swap. Got it right! Thanks! \$\endgroup\$
    – Dadelante
    Mar 4, 2016 at 17:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.