Programming C, C++, Java, PHP, Ruby, Turing, VB
Computer Science Canada 
Programming C, C++, Java, PHP, Ruby, Turing, VB  

Username:   Password: 
 RegisterRegister   
 Inplace Quicksort Implementation
Index -> Programming, Java -> Java Submissions
View previous topic Printable versionDownload TopicRate TopicSubscribe to this topicPrivate MessagesRefresh page View next topic
Author Message
Cervantes




PostPosted: Tue Apr 17, 2007 5:16 pm   Post subject: Inplace Quicksort Implementation

My first attempt at implementing quicksort in Java. I did it completely in place, which is nice.

Java:

public class Sort {
  public static void quick(int[] arr) {
    quickAux(arr, 0, arr.length - 1);
  }
 
  private static void quickAux(int[] arr, int start, int end) {
    if (start < end) {
      int pivot = arr[end];
      int i = start;
      int j = end;
      while (i != j) {
        if (arr[i] < pivot) {
          i = i + 1;
        }
        else {
          arr[j] = arr[i];
          arr[i] = arr[j-1];
          j = j - 1;
        }
      }
      arr[j] = pivot;
      quickAux(arr, start, j-1);
      quickAux(arr, j+1, end);
    }
  }
 
  public static void printArr(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
      System.out.print(arr[i] + "|");
    }
    System.out.println("");
  }
 
  public static void main(String[] args) {
    int[] a = {4,8,6,7,3,1,3,13,2,5,-4};
    quick(a);
    printArr(a);
  }
}


While doing this, I questioned why the code in the main method there works, but
Java:

quick({4,8,6,7,3,1,3,13,2,5,-4});

fails.
Sponsor
Sponsor
Sponsor
sponsor
bugzpodder




PostPosted: Tue Apr 17, 2007 5:32 pm   Post subject: RE:Inplace Quicksort Implementation

most quicksorts are in place... try a inplace merge sort
Cervantes




PostPosted: Tue Apr 17, 2007 6:33 pm   Post subject: RE:Inplace Quicksort Implementation

I did. It wasn't loads of fun.
wtd




PostPosted: Wed Apr 18, 2007 1:22 pm   Post subject: RE:Inplace Quicksort Implementation

The second attempt failed because:

code:
{4,8,6,7,3,1,3,13,2,5,-4}


Is not a Java array literal. It's just an exception in Java's syntax used to make C and C++ programmer's slightly less disgruntled when they have to use Java.

code:
quick(new int[] {4,8,6,7,3,1,3,13,2,5,-4});


Oh, and do try to make it generic. Either by sorting any Comparable object, or by using Java 1.5 generics. Smile
klopyrev




PostPosted: Wed Apr 18, 2007 3:42 pm   Post subject: Re: Inplace Quicksort Implementation

I was thinking about it, but I can't think of anyway to implement Mergesort in place? Any hints?

KL
Cervantes




PostPosted: Wed Apr 18, 2007 10:25 pm   Post subject: RE:Inplace Quicksort Implementation

wtd, thanks for enlightening me on that. Smile Of course it makes sense now. I should have known to include the new int[].

I did this simply with integers simply because this was done to study for my CS exam and we didn't have to know about Comparable or generics for the exam. I know it's nothing more than an excuse, but it was rather necessary, given my time constraints. =/



KL, I thought of a way to do it, but it involved doing some shifting.

The trouble is writing a function that takes your array, and 3 (or 4 if you really want to be general) integers representing start, mid, and end, and sorts it, assuming that the data from start to mid is sorted and the data from mid+1 to end is sorted.

Here's an example. I hope you can pick up on the syntax convention I'll use:

[6 8 | 7 9] (compare 6 and 7)
6 [8 | 7 9] (compare 8 and 7)
6 7 [8 | 9] (compare 8 and 9)
6 7 8 [| 9] (throw in the rest of the second array)
6 7 8 9

Another example:
[3 4 | 1 2] (compare 3 and 1)
1 [3 4 | 2] (compare 3 and 2)
1 2 [3 4|] (throw in the rest of the first array)
1 2 3 4


The second example in particular illustrates that some shifting will need to be done. For example, when you move 1 to the front, you have to shift both the 3 and the 4 one over.

That's why I said this wasn't loads of fun. Maybe there's a better way to do it though.
klopyrev




PostPosted: Thu Apr 19, 2007 7:44 am   Post subject: Re: Inplace Quicksort Implementation

I was thinking about that, but that ruins the runtime of mergesort completely. It leaves you with a runtime of O(N^2logN), which is worse than bubblesort.

KL
Display posts from previous:   
   Index -> Programming, Java -> Java Submissions
View previous topic Tell A FriendPrintable versionDownload TopicRate TopicSubscribe to this topicPrivate MessagesRefresh page View next topic

Page 1 of 1  [ 7 Posts ]
Jump to:   


Style:  
Search: