Main Site Documentation

Snippet - ArrayList FastQuickSort


#1

ArrayList FastQuickSort

Add an Object to an ArrayList and Sort that list using FastQuickSort Algorithm.


#2

@ Jay Jay - Cheers, I used your FastQuickSort as a starting point for a sort routine I needed in TinyFileSystem.


#3

I’m glad you found it useful… i have implemented other algorithms which I’ll share later once i clean up the code…


#4

could you post the Comparer.Compare function?


#5

just declare it as a variable:


 private IComparer Comparer;


#6

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);

#7

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;
            }

        }



    }
}