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