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\$
3
  • \$\begingroup\$ Java just doesn't do tail-call optimization, period. Not even when the code is structured to be tail-call friendly. \$\endgroup\$ Aug 22, 2014 at 22:50
  • \$\begingroup\$ Your implementation doesn't match the pseudocode. \$\endgroup\$ Aug 22, 2014 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, 2014 at 23:16

1 Answer 1

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 and acknowledge you have read our privacy policy.

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