georgekosmidis/basicalgorithms

Basic algorithms implementations in C#

basicalgorithms's Issues

QuickSort

I was comparing your QuckSort algorithm with the implementation gotten out of the coursera algorithms course and for sequential data it doesn't seem to work optimally. For a list of sorted numbers 1 - 100 passed to the quicksort there are 5049 swaps and 4950 comparisons compared to the Princeton algorithm which has 99 swaps and 5149 comparisons. Another thing is that you probably want to test whether you are trying to swap the same index. If i reverse the list i get 2549 swaps with the same number of compares. I modified the code a little to support generic types but its essentially the same

        private int Partition<T>(IList<T> data, int start, int end) where T : IComparable<T>
        {
            //loop partition and swap with last of partition (last as pivot)
            for (var i = start; i < end; i++)
            {
                Comparisions++;
                if (data[i].CompareTo(data[end]) <= 0)
                {
                    Swap(data, start, i);
                    start++;//move new pivot
                }
            }


            Swap(data, start, end);

            return start;
        }

        private void Swap<T>(IList<T> list, int i, int j)
        {
            Swaps++;
            Console.WriteLine($"Swapping {list[i]} with {list[j]}");
            if (i == j)
            {
                return;
            }
            T temp = list[i];
            list[i] = list[j];
            list[j] = temp;
            
        }

Cousera's partition function

        private int Partition<T>(IList<T> list, int start, int end) where T : IComparable<T>
        {
            int i = start;
            int j = end + 1;
            while (true)
            {
                while (list[++i].CompareTo(list[start]) < 0)
                {
                    Comparisions++;
                    if (i == end)
                    {
                        break;
                    }
                }
                Comparisions++;

                while (list[start].CompareTo(list[--j]) < 0)
                {
                    Comparisions++;
                    if (j == start)
                    {
                        break;
                    }
                }
                Comparisions++;

                if (i >= j)
                {
                    break;
                }
                Swap(list, i, j);
            }

            Swap(list, start, j);

            return j;
        }