Computer Science Canada Programming C, C++, Java, PHP, Ruby, Turing, VB   Username:   Password: Wiki   Blog   Search   Turing   Chat Room  Members
Inplace Quicksort Implementation
Author Message
Cervantes

Posted: 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.

bugzpodder

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

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

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

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

Posted: 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.
klopyrev

Posted: 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

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

wtd, thanks for enlightening me on that. 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

Posted: 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: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First

Page 1 of 1  [ 7 Posts ]
 Jump to:  Select a forum  CompSci.ca ------------ - Network News - General Discussion     General Forums   -----------------   - Hello World   - Featured Poll   - Contests     Contest Forums   -----------------   - DWITE   - [FP] Contest 2006/2008   - [FP] 2005/2006 Archive   - [FP] 2004/2005 Archive   - Off Topic     Lounges   ---------   - User Lounge   - VIP Lounge     Programming -------------- - General Programming     General Programming Forums   --------------------------------   - Functional Programming   - Logical Programming   - C     C   --   - C Help   - C Tutorials   - C Submissions   - C++     C++   ----   - C++ Help   - C++ Tutorials   - C++ Submissions   - Java     Java   -----   - Java Help   - Java Tutorials   - Java Submissions   - Ruby     Ruby   -----   - Ruby Help   - Ruby Tutorials   - Ruby Submissions   - Turing     Turing   --------   - Turing Help   - Turing Tutorials   - Turing Submissions   - PHP     PHP   ----   - PHP Help   - PHP Tutorials   - PHP Submissions   - Python     Python   --------   - Python Help   - Python Tutorials   - Python Submissions   - Visual Basic and Other Basics     VB   ---   - Visual Basic Help   - Visual Basic Tutorials   - Visual Basic Submissions     Education ----------- - Student Life   Graphics and Design ----------------------- - Web Design     Web Design Forums   ---------------------   - (X)HTML Help   - (X)HTML Tutorials   - Flash MX Help   - Flash MX Tutorials   - Graphics     Graphics Forums   ------------------   - Photoshop Tutorials   - The Showroom   - 2D Graphics   - 3D Graphics     Teams ------ - dTeam Public

 Style: Appalachia blueSilver eMJay subAppalachia subBlue subCanvas subEmjay subGrey subSilver subVereor Search: