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\$
  • \$\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 '16 at 13:33
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\$
  • 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\$ – ratchet freak Mar 4 '16 at 16:31
  • \$\begingroup\$ @ratchetfreak what thread communication and what overhead do you mean? \$\endgroup\$ – Andriy Kryvtsun Mar 4 '16 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\$ – ratchet freak Mar 4 '16 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 '16 at 17:11
  • \$\begingroup\$ Good point about the swap. Got it right! Thanks! \$\endgroup\$ – Dadelante Mar 4 '16 at 17:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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