Shuffle algorithm

  • Thread starter Thread starter 2G
  • Start date Start date
2

2G

Hi,

Does anyone know a good/fast shuffle algorithm to shuffle a array ?
I've written a class to sort my listviews using quicksort but it tends to
get very slow on columns that are already sorted.

Thanks in advance.
 
that's is not really a surprise. quicksort has a worse case scenario of O(n^2) and average of O(n*log n). put in your number 10000 for n, you can see that worse case is <b>2500</b> times worse than the average. that's why your 60ms performance jumped to 22s on sorted list. (did you send an attachment? i can't view attachment) my guess is that you picked either the first or last element of a range as the pivot point. that essentially guaranttees you that running quicksort on a sorted (or partially sorted, which is quite often the case) list will give you the worse case scenario. best solution is to pick a better pivot point, like from the middle of the list


----- 2G wrote: ----

It's just that when I sort an unsorted array of 10000 records, it take
about 60 ms (sorted on strings) to sort it
But when I sort a sorted array of 10000 records again , then it takes abou
22 seconds which by me is not acceptable ;

I've included the clas

Grt

what are you trying to do? shuffle your sorted list so you can re-sort i
Click to expand...
again? doesn't seem like a sound solution to me. whatever you save on th
quicksort will probably be offset by the shuffle. you might end up wher
you started againpicking the pivot either as the first or last element of the segment. i
your sorted list case, you are doing the equivalent work of a linear sort
without actually sorting since it's already sorted. the best solution woul
be change how you pick the pivot
 
This is the code:

public enum ColumnType{

DateTime,

Int,

String,

}

public sealed class Sorter

{

public static void Sort(ref ArrayList tabel, SortOrder s, ColumnType t, int
colomn)

{

QuickSort(ref tabel, ref s, ref t, ref colomn, 0, tabel.Count - 1);

}

private static void QuickSort (ref ArrayList szArray, ref SortOrder s, ref
ColumnType t, ref int column, int nLower, int nUpper)

{

if (nLower < nUpper)

{

int nSplit = Partition (ref szArray, ref s, ref t, ref column, nLower,
nUpper);

QuickSort (ref szArray, ref s, ref t, ref column, nLower, nSplit - 1);

QuickSort (ref szArray, ref s, ref t, ref column, nSplit + 1, nUpper);

}

}

private static int Partition (ref ArrayList szArray, ref SortOrder s, ref
ColumnType t, ref int column, int nLower, int nUpper)

{

int nLeft = nLower + 1;

string[] szPivot = (string[]) szArray[nLower];

int nRight = nUpper;

string[] szSwap;

while (nLeft <= nRight)

{

switch(t)

{

case ColumnType.String:

#region "string"

switch(s)

{

case SortOrder.Ascending:

while (nLeft <= nRight)

{

if ( ((string[])szArray[nLeft])[column].CompareTo (szPivot[column]) > 0)

break;

nLeft = nLeft + 1;

}

while (nLeft <= nRight)

{

if ( ((string[])szArray[nRight])[column].CompareTo (szPivot[column]) <= 0)

break;

nRight = nRight - 1;

}

break;

case SortOrder.Descending:

while (nLeft <= nRight)

{

if ( ((string[])szArray[nLeft])[column].CompareTo (szPivot[column]) <= 0)

break;

nLeft = nLeft + 1;

}

while (nLeft <= nRight)

{

if ( ((string[])szArray[nRight])[column].CompareTo (szPivot[column]) > 0)

break;

nRight = nRight - 1;

}

break;

}

break;

#endregion

case ColumnType.Int:

#region "int"

switch(s)

{

case SortOrder.Ascending:

while (nLeft <= nRight)

{

string[] tmp = (string[])szArray[nLeft];

if (
Convert.ToInt32(tmp[column]).CompareTo(Convert.ToInt32(szPivot[column])) >
0)

break;

nLeft = nLeft + 1;

}

while (nLeft <= nRight)

{

string[] tmp = (string[])szArray[nRight];

if (Convert.ToInt32(tmp[column]).CompareTo(Convert.ToInt32(szPivot[column]))
<= 0)

break;

nRight = nRight - 1;

}

break;

case SortOrder.Descending:

while (nLeft <= nRight)

{

string[] tmp = (string[])szArray[nLeft];

if (
Convert.ToInt32(tmp[column]).CompareTo(Convert.ToInt32(szPivot[column])) <=
0)

break;

nLeft = nLeft + 1;

}

while (nLeft <= nRight)

{

string[] tmp = (string[])szArray[nRight];

if (Convert.ToInt32(tmp[column]).CompareTo(Convert.ToInt32(szPivot[column]))
0)
Click to expand...

break;

nRight = nRight - 1;

}

break;

}

break;

#endregion

case ColumnType.DateTime:

#region "DateTime"

switch(s)

{

case SortOrder.Ascending:

while (nLeft <= nRight)

{

string[] tmp = (string[])szArray[nLeft];

if (
Convert.ToDateTime(tmp[column]).CompareTo(Convert.ToDateTime(szPivot[column]
)) > 0)

break;

nLeft = nLeft + 1;

}

while (nLeft <= nRight)

{

string[] tmp = (string[])szArray[nRight];

if
(Convert.ToDateTime(tmp[column]).CompareTo(Convert.ToDateTime(szPivot[column
])) <= 0)

break;

nRight = nRight - 1;

}

break;

case SortOrder.Descending:

while (nLeft <= nRight)

{

string[] tmp = (string[])szArray[nLeft];

if (
Convert.ToDateTime(tmp[column]).CompareTo(Convert.ToDateTime(szPivot[column]
)) <= 0)

break;

nLeft = nLeft + 1;

}

while (nLeft <= nRight)

{

string[] tmp = (string[])szArray[nRight];

if
(Convert.ToDateTime(tmp[column]).CompareTo(Convert.ToDateTime(szPivot[column
])) > 0)

break;

nRight = nRight - 1;

}

break;

}

break;

#endregion

}

// Swap values if necessary

if (nLeft < nRight)

{

szSwap = (string[]) szArray[nLeft];

szArray[nLeft] = szArray[nRight];

szArray[nRight] = szSwap;

nLeft = nLeft + 1;

nRight = nRight - 1;

}

}

// Move pivot element

szSwap = (string[]) szArray[nLower];

szArray[nLower] = szArray[nRight];

szArray[nRight] = szSwap;

return nRight;

}

}





Grtz
 
like I said before, you are using the first item in the array as your pivot. You should use something else like the middle item instead, that will solve your performance problem with already sorted list.
 
ListView already has a sort method doesn't it? ArrayList certainly does. Is
there a reason you're writing your own sort method?
 
Back
Top