2
\$\begingroup\$

I've heard of this implementation of quick sort (in pseudocode):

TAIL-RECURSIVE-QUICKSORT(A, p, r)
  while p < r
     q = PARTITION(A, p, r)
     if q < (p + (r-p)/2)
        TAIL-RECURSIVE-QUICKSORT(A, p, q-1)
        p = q+1
     else
        TAIL-RECURSIVE-QUICKSORT(A, q+1, p)
        r = q-1

Here it is partially implemented.

private static void quickSort(int[] arr, int lo, int hi){
  if(lo >= hi) return;

  int p = partition(arr, lo, hi);

  // modified to choose small partition first

  if((p - lo )<=(hi-p)){
    System.out.println(String.format("Sorting left first %d %d %d",lo,p,hi)) ;
    quickSort(arr, lo, p);
    quickSort(arr, p+1, hi);
  }else {
    System.out.println(String.format("Sorting right first %d %d %d",lo,p,hi));
    quickSort(arr, p+1, hi);
    quickSort(arr, lo, p);
  }
}

Can it be made any faster? FWIW I profiled the above code against regular (recursive) quicksort and it was usually faster (tested on randomly generated arrays).

screenshot
(full size)

Here is partition and a method for swapping

private static int partition(int[] a, int p, int r) {

    int x = a[p];
    int i = p-1 ;
    int j = r+1 ;

    while (true) {
        i++;
        while ( i< r && a[i] < x)
            i++;
        j--;
        while (j>p && a[j] > x)
            j--;

        if (i < j)
            swap(a, i, j);
        else
            return j;
    }
}

private static void swap(int[] a, int i, int j) {
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}
\$\endgroup\$
  • \$\begingroup\$ Java just doesn't do tail-call optimization, period. Not even when the code is structured to be tail-call friendly. \$\endgroup\$ – 200_success Aug 22 '14 at 22:50
  • \$\begingroup\$ Your implementation doesn't match the pseudocode. \$\endgroup\$ – 200_success Aug 22 '14 at 23:01
  • \$\begingroup\$ @200_success that's what I wast trying to explain, the pseudocode has a bug in it, but my code doesn't (so that's why it doesn't match). \$\endgroup\$ – Celeritas Aug 22 '14 at 23:16
6
\$\begingroup\$
private static void quickSort(int[] arr, int lo, int hi){

Spell variable names out! There is nothing gained with abbreviating variable names, especially so short ones, it only makes the code harder to read.


int p = partition(arr, lo, hi);

Same here.


System.out.println(String.format("Sorting left first %d %d %d",lo,p,hi)) ;

Here is one simple rule:

Whenever you want to interact with the screen, may it be printing to the console or redrawing any graphical element, it is going to be expensive.

You want to profile your code without these printlns.


private static int partition(int[] a, int p, int r) {

Same here. I know that it is mostly done this way, but code is easier to read when you gave stuff actual names. Example?

while (j>p && a[j] > x)
        j--;

Quick, what does this code do?


int x = a[p];

x is a bad variable name for one simple reason, x is a dimension. You should avoid using x, y and z as names unless you're dealing with dimensions.


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

Same here, long variable names would make this make it better to read by a long shot.

\$\endgroup\$

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.