ArrayList FastQuickSort
Add an Object to an ArrayList and Sort that list using FastQuickSort Algorithm.
1 Like
@ Jay Jay - Cheers, I used your FastQuickSort as a starting point for a sort routine I needed in TinyFileSystem.
I’m glad you found it useful… i have implemented other algorithms which I’ll share later once i clean up the code…
could you post the Comparer.Compare function?
just declare it as a variable:
private IComparer Comparer;
why call these two functions? Don’t they both do the same thing? Can I call only one of them to do a sort?
fastQuickSort(list, 0, list.Count - 1);
InsertionSort(list, 0, list.Count - 1);I tested your code by commenting out the call to InsertionSort(), it seems that fastQuickSort() function does not do any sorting. InsertionSort() does work ok.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;
using System.Diagnostics;
namespace SortTest
{
class CComparer : IComparer
{
/// <summary>
///x Type: System.Object
///The first object to compare.
///y Type: System.Object
///The second object to compare.
///Return Value
///Type: System.Int32
///A signed integer that indicates the relative values of x and y, as shown in the following table.
///Value Meaning
///Less than zero x is less than y.
///Zero x equals y.
///Greater than zero x is greater than y.
/// </summary>
/// <param name="x"></param>
/// <param name="y"></param>
/// <returns></returns>
public int Compare(object x, object y)
{
return string.CompareOrdinal((string)x, (string)y);
}
}
class Program
{
static void Main(string[] args)
{
Comparer = new CComparer();
var myList = new ArrayList();
FastQuickSort(ref myList, "1099");
FastQuickSort(ref myList, "1050");
FastQuickSort(ref myList, "1075");
FastQuickSort(ref myList, "1025");
FastQuickSort(ref myList, "1040");
for (int i = 0; i < myList.Count; i++)
{
Debug.Print(myList[i].ToString());
Console.WriteLine(myList[i].ToString());
}
Console.ReadKey();
}
static CComparer Comparer;
public static void Swap(IList array, int left, int right)
{
object swap = array[left];
array[left] = array[right];
array[right] = swap;
}
public static void FastQuickSort(ref ArrayList list, object Object)
{
list.Add(Object);
fastQuickSort(list, 0, list.Count - 1);
//InsertionSort(list, 0, list.Count - 1);
}
/// <summary>
/// This is a generic version of C.A.R Hoare's Quick Sort
/// algorithm. This will handle arrays that are already
/// sorted, and arrays with duplicate keys.
/// </summary>
/// <remarks>
/// If you think of a one dimensional array as going from
/// the lowest index on the left to the highest index on the right
/// then the parameters to this function are lowest index or
/// left and highest index or right. The first time you call
/// this function it will be with the parameters 0, a.length - 1.
/// </remarks>
/// <param name="list">list to sort</param>
/// <param name="lo0">left boundary of array partition</param>
/// <param name="hi0">right boundary of array partition</param>
internal static void fastQuickSort(ArrayList list, int l, int r)
{
int M = 4;
int i;
int j;
Object v;
if ((r - l) > M)
{
i = (r + l) / 2;
if (Comparer.Compare(list[l], list[i]) > 0)
Swap(list, l, i); // Tri-Median Methode!
if (Comparer.Compare(list[l], list[r]) > 0)
Swap(list, l, r);
if (Comparer.Compare(list[i], list[r]) > 0)
Swap(list, i, r);
j = r - 1;
Swap(list, i, j);
i = l;
v = list[j];
for (; ; )
{
while (Comparer.Compare(list[++i], v) < 0)
{ }
while (Comparer.Compare(list[--j], v) > 0)
{ }
if (j < i)
break;
Swap(list, i, j);
}
Swap(list, i, r - 1);
fastQuickSort(list, l, j);
fastQuickSort(list, i + 1, r);
}
}
internal static void InsertionSort(ArrayList list, int lo0, int hi0)
{
int i;
int j;
Object v;
for (i = lo0 + 1; i <= hi0; i++)
{
v = list[i];
j = i;
while ((j > lo0) && (Comparer.Compare(list[j - 1], v) > 0))
{
list[j] = list[j - 1];
--j;
}
list[j] = v;
}
}
}
}
1 Like