quicksort

Insert this script in the first frame of your movie to add the new and faster quicksort command to the array objects. function quicksort(){ function sort(a, l,r){ var i=l, j=r, w, x=a[int((l+r)/2)]; do { while(a[i] < x) i++; while(x < a[j]) j--; if(i<=j){ w = a[i]; a[i++] = a[j]; a[j--] = w; } } while(i <= j); if(l < j) sort(a, l,j); if(i < r) sort(a, i, r); } sort(this, 0, this.length-1); } Array.prototype.quicksort = quicksort; //usage a = [4,2,5,78,0]; a.quicksort(); trace(a);
Adam Date: 22/07/2002
Nice. Im a 2nd year compsci student and ive been wondering about doing this sort of stuff in flash. It would be interesting to do ADTs visually in flash..
Adam Date: 22/07/2002
Nice. Im a 2nd year compsci student and ive been wondering about doing this sort of stuff in flash. It would be interesting to do ADTs visually in flash..
Wimpyburger Date: 01/04/2003
hi there, wonderful function u have there! I can really use this one, my home-made sorting function consists of many ifs and fors and elses :D Thanks again!
Cruiser Date: 04/05/2004
How do I do a sort ascending or descending? Thanks Cruiser
benoit Date: 06/12/2004
Hi Adam, your function is really nice, really fast. But as Cruiser I need to sort my array in reverse order. So, I've just modified a bit your function to allow a user to use a function to compare the values in the Array. function quicksort( compareFunction ){ function sort(a, l,r){ var i=l, j=r, w, x=a[int((l+r)/2)]; do { while( compareFunction( a[i], x ) < 0 ) i++; while( compareFunction( x, a[j] ) < 0 ) j--; if(i<=j){ w = a[i]; a[i++] = a[j]; a[j--] = w; } } while(i <= j); if(l < j) sort(a, l,j, compareFunction); if(i < r) sort(a, i, r, compareFunction); } sort(this, 0, this.length-1, compareFunction); } Where compareFunction is a standard function to compare object: function myCompareFunction( a, b ) { }
benoit Date: 06/12/2004
Oups, sorry... the form has been post to quickly ;) So the compareFunction is something like that: function myCompareFunction( a, b ) { if ( a < b ) return -1; else if ( a > b ) return 1; else return 0; } When you want to use this function, just do: var myArray = [/* your values */]; myArray.quicksort( myCompareFunction ); For a reverse order sorting just use the reversedCompare function function reversedCompare( a, b ) { if ( a > b ) return -1; else if ( a < b ) return 1; else return 0; } That's all! hope it will help ;) Bye, Benoit
sven Date: 21/01/2005
I tried to understand the code, but found it quite difficult; this is complicated stuff! So I wrote my own function; much simpler to understand at least. I don't know anything about performance, but can it get any simpler than this?: function sort_Array (arr) { var i = arr.length; var temp = new Array (); while (i--) { temp[arr[i]] = arr[i]; } var sorted = new Array (); i = 0; while (i < temp.length) { if (temp[i] != undefined) { sorted.push (temp[i]); } i++; } return sorted; } // test: a = [4, 2, 5, 78, 0]; b = sort_Array (a); Sven
hady Date: 12/04/2007
I think that this quick sort is better than all those posted it quick, public class quickSort { public static void main (String []args) { int a[],size; System.out.println("Enter the order of the array "); size=SavitchIn.readLineInt(); a=new int[size]; initialize(a); quicksort(a,0,size-1); display(a); } public static void quicksort(int a[],int lo,int hi) { int pivot; if(hi>lo) { pivot=partition(a,lo,hi); quicksort(a,lo,pivot-1); quicksort(a,pivot+1,hi); } } public static int partition(int a[] , int lo, int hi) { int i,x,j; x=a[hi]; i=lo-1; for(j=lo;j<hi;j++) { if(a[j]<=x) { i++; swap(a,i,j); } } swap(a,i+1,hi); return i+1; } public static void display(int a[]) { int i; System.out.println(); for(i=0;i<a.length;i++) System.out.print(a[i]+"-"); } public static void initialize(int a[]) { int i; System.out.println("Enter the numbers"); for(i=0;i<a.length;i++) a[i]=SavitchIn.readLineInt(); } public static void swap (int a[], int i, int j) { int temp; temp=a[i]; a[i]=a[j]; a[j]=temp; } }
Add comment
Home