1
\$\begingroup\$

Lately, I've been developing sorting algorithms as a kind of exercise to make better code and I've come accross something curious, even though bubble and cocktail sort are known to perform horribly, I think I might be doing something wrong since it takes a larger amount of time than selection, insertion and merge sort (about 3 times longer than selection sort, about 2 times insertion and merge sort)

Code for Bubble sort

public static class BubbleSort
{
    public static List<long> SortAscending(List<long> unsortedList)
    {
        bool anyElementSwapped = true;
        int elementsPendingToSort = unsortedList.Count;
        while (anyElementSwapped)
        {
            anyElementSwapped = false;
            for (int currentElementIndex = 0; currentElementIndex < elementsPendingToSort; currentElementIndex++)
            {
                if (unsortedList.Count.Equals(currentElementIndex + 1))
                {
                    continue;
                }
                if (unsortedList[currentElementIndex] > unsortedList[currentElementIndex + 1])
                {
                    anyElementSwapped = true;
                    long temporalValueHolder = unsortedList[currentElementIndex];
                    unsortedList[currentElementIndex] = unsortedList[currentElementIndex + 1];
                    unsortedList[currentElementIndex + 1] = temporalValueHolder;
                }
            }
            elementsPendingToSort--;
        }
        return unsortedList;
    }

    public static List<long> SortDescending(List<long> unsortedList)
    {
        bool anyElementSwapped = true;
        int elementsPendingToSort = unsortedList.Count;

        while (anyElementSwapped)
        {
            anyElementSwapped = false;
            for (int currentElementIndex = 0; currentElementIndex < elementsPendingToSort; currentElementIndex++)
            {
                if (unsortedList.Count.Equals(currentElementIndex + 1))
                {
                    continue;
                }
                if (unsortedList[currentElementIndex] < unsortedList[currentElementIndex + 1])
                {
                    anyElementSwapped = true;
                    long temporalValueHolder = unsortedList[currentElementIndex + 1];
                    unsortedList[currentElementIndex + 1] = unsortedList[currentElementIndex];
                    unsortedList[currentElementIndex] = temporalValueHolder;
                }
            }
            elementsPendingToSort--;
        }

        return unsortedList;
    }
}

Code for Cocktail sort

public static class CocktailSort
{
    public static List<long> SortAscending(List<long> unsortedList)
    {
        int lowerSortBound = 0;
        int upperSortBound = unsortedList.Count;
        bool anyElementSwapped = false;

        while (lowerSortBound < upperSortBound)
        {
            anyElementSwapped = false;
            for (int lowerBound = lowerSortBound; lowerBound < upperSortBound; lowerBound++)
            {
                if (unsortedList.Count.Equals(lowerBound + 1))
                {
                    break;
                }
                if (unsortedList[lowerBound] > unsortedList[lowerBound + 1])
                {
                    anyElementSwapped = true;
                    SwapUpwards(unsortedList, lowerBound);
                }
            }
            upperSortBound--;
            if (!anyElementSwapped)
                break;
            anyElementSwapped = false;
            for (int upperBound = upperSortBound; upperBound > lowerSortBound; upperBound--)
            {
                if ((upperBound - 1) <= 0)
                {
                    break;
                }
                if (unsortedList[upperBound] < unsortedList[upperBound - 1])
                {
                    anyElementSwapped = true;
                    SwapDownwards(unsortedList, upperBound);
                }
            }
            lowerSortBound++;
            if (!anyElementSwapped)
                break;
        }
        return unsortedList;
    }

    public static List<long> SortDescending(List<long> unsortedList)
    {
        int lowerSortBound = 0;
        int upperSortBound = unsortedList.Count;
        bool anyElementSwapped = false;

        while (lowerSortBound < upperSortBound)
        {
            anyElementSwapped = false; for (int lowerBound = lowerSortBound; lowerBound < upperSortBound; lowerBound++)
            {
                if (unsortedList.Count.Equals(lowerBound + 1))
                {
                    break;
                }
                if (unsortedList[lowerBound] < unsortedList[lowerBound + 1])
                {
                    anyElementSwapped = true;
                    SwapUpwards(unsortedList, lowerBound);
                }
            }
            upperSortBound--;
            if (!anyElementSwapped)
                break;
            anyElementSwapped = false;
            for (int upperBound = upperSortBound; upperBound > lowerSortBound; upperBound--)
            {
                if ((upperBound - 1) < 0)
                {
                    break;
                }
                if (unsortedList[upperBound] > unsortedList[upperBound - 1])
                {
                    anyElementSwapped = true;
                    SwapDownwards(unsortedList, upperBound);
                }
            }
            lowerSortBound++;
            if (!anyElementSwapped)
                break;
        }
        return unsortedList;
    }

    private static void SwapUpwards(List<long> list, int indexToSwap)
    {
        long temporalValueHolder = list[indexToSwap];
        list[indexToSwap] = list[indexToSwap + 1];
        list[indexToSwap + 1] = temporalValueHolder;
    }

    private static void SwapDownwards(List<long> list, int indexToSwap)
    {
        long temporalValueHolder = list[indexToSwap - 1];
        list[indexToSwap - 1] = list[indexToSwap];
        list[indexToSwap] = temporalValueHolder;
    }
}

Code of the Main Method:

private static void Main(string[] args)
    {
        Console.WriteLine("Initiating sorting algorithms comparison program");
        Dictionary<string, List<double>> sortingTimeResults = new Dictionary<string, List<double>>();

        sortingTimeResults.Add("AscendingCocktailSort", new List<double>());
        sortingTimeResults.Add("DescendingCocktailSort", new List<double>());
        sortingTimeResults.Add("AscendingBubbleSort", new List<double>());
        sortingTimeResults.Add("DescendingBubbleSort", new List<double>());
        sortingTimeResults.Add("AscendingSelectionSort", new List<double>());
        sortingTimeResults.Add("DescendingSelectionSort", new List<double>());
        sortingTimeResults.Add("AscendingInsertionSort", new List<double>());
        sortingTimeResults.Add("DescendingInsertionSort", new List<double>());
        sortingTimeResults.Add("AscendingMergeSort", new List<double>());
        sortingTimeResults.Add("DescendingMergeSort", new List<double>());

        List<long> listToSort = new List<long>();
        listToSort = Enumerable.Range(0, 10000).Select(item => (long)item).ToList();
        Console.WriteLine($"Created list of {listToSort.Count} elements to order");

        int timesToIterate = 10;
        for (int i = 0; i < timesToIterate; i++)
        {
            int n = listToSort.Count;
            Random rng = new Random();

            //Console.WriteLine("Randomizing the list of elements");
            while (n > 1)
            {
                n--;
                int k = rng.Next(n + 1);
                long value = listToSort[k];
                listToSort[k] = listToSort[n];
                listToSort[n] = value;
            }
            //Console.WriteLine("Finished randomizing list");
            Parallel.Invoke(new ParallelOptions() { MaxDegreeOfParallelism = 1 },
            () =>
            {
                Stopwatch sortingStopWatch = new Stopwatch();
                //Console.WriteLine("Starting AscendingCocktailSort algorithm");
                sortingStopWatch.Restart();
                CocktailSort.SortAscending(listToSort.ToList());
                sortingStopWatch.Stop();
                //Console.WriteLine("Ended AscendingCocktailSort algorithm");
                sortingTimeResults["AscendingCocktailSort"].Add(sortingStopWatch.Elapsed.TotalMilliseconds);
            },
            () =>
            {
                Stopwatch sortingStopWatch = new Stopwatch();
                //Console.WriteLine("Starting DescendingCocktailSort algorithm");
                sortingStopWatch.Restart();
                CocktailSort.SortDescending(listToSort.ToList());
                sortingStopWatch.Stop();
                //Console.WriteLine("Ended DescendingCocktailSort algorithm");
                sortingTimeResults["DescendingCocktailSort"].Add(sortingStopWatch.Elapsed.TotalMilliseconds);
            }
            ,
            () =>
            {
                Stopwatch sortingStopWatch = new Stopwatch();
                //Console.WriteLine("Starting AscendingBubbleSort algorithm");
                sortingStopWatch.Restart();
                BubbleSort.SortAscending(listToSort.ToList());
                sortingStopWatch.Stop();
                //Console.WriteLine("Ended AscendingBubbleSort algorithm");
                sortingTimeResults["AscendingBubbleSort"].Add(sortingStopWatch.Elapsed.TotalMilliseconds);
            },
            () =>
            {
                Stopwatch sortingStopWatch = new Stopwatch();
                //Console.WriteLine("Starting DescendingBubbleSort algorithm");
                sortingStopWatch.Restart();
                BubbleSort.SortDescending(listToSort.ToList());
                sortingStopWatch.Stop();
                //Console.WriteLine("Ended DescendingBubbleSort algorithm");
                sortingTimeResults["DescendingBubbleSort"].Add(sortingStopWatch.Elapsed.TotalMilliseconds);
            },
            () =>
            {
                Stopwatch sortingStopWatch = new Stopwatch();
                //Console.WriteLine("Starting AscendingSelectionSort algorithm");
                sortingStopWatch.Restart();
                SelectionSort.Sort(listToSort.ToList(), true);
                sortingStopWatch.Stop();
                //Console.WriteLine("Ended AscendingSelectionSort algorithm");
                sortingTimeResults["AscendingSelectionSort"].Add(sortingStopWatch.Elapsed.TotalMilliseconds);
            },
            () =>
            {
                Stopwatch sortingStopWatch = new Stopwatch();
                //Console.WriteLine("Starting DescendingSelectionSort algorithm");
                sortingStopWatch.Restart();
                SelectionSort.Sort(listToSort.ToList(), false);
                sortingStopWatch.Stop();
                //Console.WriteLine("Ended DescendingSelectionSort algorithm");
                sortingTimeResults["DescendingSelectionSort"].Add(sortingStopWatch.Elapsed.TotalMilliseconds);
            },
            () =>
            {
                Stopwatch sortingStopWatch = new Stopwatch();
                //Console.WriteLine("Starting AscendingInsertionSort algorithm");
                sortingStopWatch.Restart();
                InsertionSort.SortAscending(listToSort.ToList());
                sortingStopWatch.Stop();
                //Console.WriteLine("Ended AscendingInsertionSort algorithm");
                sortingTimeResults["AscendingInsertionSort"].Add(sortingStopWatch.Elapsed.TotalMilliseconds);
            }
            ,
            () =>
            {
                Stopwatch sortingStopWatch = new Stopwatch();
                //Console.WriteLine("Starting DescendingInsertionSort algorithm");
                sortingStopWatch.Restart();
                InsertionSort.SortDescending(listToSort.ToList());
                sortingStopWatch.Stop();
                //Console.WriteLine("Ended DescendingInsertionSort algorithm");
                sortingTimeResults["DescendingInsertionSort"].Add(sortingStopWatch.Elapsed.TotalMilliseconds);
            },
            () =>
            {
                Stopwatch sortingStopWatch = new Stopwatch();
                //Console.WriteLine("Starting AscendingMergeSort algorithm");
                sortingStopWatch.Restart();
                MergeSort.SortAscending(listToSort.ToList());
                sortingStopWatch.Stop();
                //Console.WriteLine("Ended AscendingMergeSort algorithm");
                sortingTimeResults["AscendingMergeSort"].Add(sortingStopWatch.Elapsed.TotalMilliseconds);
            },
            () =>
            {
                Stopwatch sortingStopWatch = new Stopwatch();
                //Console.WriteLine("Starting DescendingMergeSort algorithm");
                sortingStopWatch.Restart();
                MergeSort.SortDescending(listToSort.ToList());
                sortingStopWatch.Stop();
                //Console.WriteLine("Ended DescendingMergeSort algorithm");
                sortingTimeResults["DescendingMergeSort"].Add(sortingStopWatch.Elapsed.TotalMilliseconds);
            }
            );
        }

        Console.WriteLine($"Sorting algorithms comparison for a list with {listToSort.Count} elements has ended,");
        Console.WriteLine("the result for each algorithm be it ascending or descending, are the following, with a sample size of " + timesToIterate);
        sortingTimeResults.ToList().ForEach(result =>
        {
            Console.WriteLine($"  - The mean time taken to sort the list by the {result.Key} algorithm is {result.Value.Sum() / result.Value.Count} miliseconds");
        });

        Console.WriteLine(Environment.NewLine + Environment.NewLine);
        Console.WriteLine("The evaluation has ended, press any key to leave");
        Console.ReadKey();
    }

The Parallel limited to only 1 thread running at once is there because the last computer I ran it on could not handle them ideally and thus giving false samples of the time it takes to perform any of the sorting procedures, I usually run 4 threads at the same time.

A sample of the measurements in debug:

enter image description here

A sample of the measurement in release:

enter image description here

What could I do better in order to reduce the amount of time this code takes?

\$\endgroup\$
  • \$\begingroup\$ Could you add the actual measurements to the question? Also the data you generated or used to test it. \$\endgroup\$ – t3chb0t Oct 16 '18 at 8:56
  • \$\begingroup\$ I am using a list of about a thousand items that I then reorder using a function that relies on the Random C# class to reorder the elements in many ways, I perform a hundred times this list that gets reordered each iteration and then I calculate the mean time of all the calculations \$\endgroup\$ – Oscar Guillamon Oct 16 '18 at 9:08
  • \$\begingroup\$ I see on your screenshot that you are measureing the Debug version. These measurements are wrong as the compiled code is not optimized. You should do this in Release mode with VS detached. I'd be great if you added the Main method doing the measurements too. \$\endgroup\$ – t3chb0t Oct 16 '18 at 11:39
4
\$\begingroup\$

When it comes to performance you do nothing wrong in the algorithm, bubble and cocktail sort are just not efficient per design (O(n^2)).


This

        for (int currentElementIndex = 0; currentElementIndex < elementsPendingToSort; currentElementIndex++)
        {
            if (unsortedList.Count.Equals(currentElementIndex + 1))
            {
                continue;
            }
            ...

... can be simplified to:

        for (int currentElementIndex = 0; currentElementIndex < elementsPendingToSort - 1; currentElementIndex++)
        {
           ...

where the stop condition is: currentElementIndex < elementsPendingToSort - 1 instead of just currentElementIndex < elementsPendingToSort.

And a similar change can be made in CocktailSort.


BubbleSort can be improved slightly in this way:

  public static List<long> SortAscending(List<long> unsortedList)
  {
    int elementsPendingToSort = unsortedList.Count;
    do
    {
      int newStop = 0;
      for (int currentElementIndex = 0; currentElementIndex < elementsPendingToSort - 1; currentElementIndex++)
      {
        if (unsortedList[currentElementIndex] > unsortedList[currentElementIndex + 1])
        {
          newStop = currentElementIndex + 1;
          long temporalValueHolder = unsortedList[currentElementIndex];
          unsortedList[currentElementIndex] = unsortedList[currentElementIndex + 1];
          unsortedList[currentElementIndex + 1] = temporalValueHolder;
        }
      }
      elementsPendingToSort = newStop;
    } while (elementsPendingToSort > 0);
    return unsortedList;
  }
}

Here the anyElementSwapped is replaced by newStop and elementsPendingToSort is set to newStop after the current iteration. This is an optimization when more elements are placed in their right position in the same iteration.


This

          long temporalValueHolder = unsortedList[currentElementIndex];
          unsortedList[currentElementIndex] = unsortedList[currentElementIndex + 1];
          unsortedList[currentElementIndex + 1] = temporalValueHolder;

is candidate for a Swap method that may be generic and made as an extension method:

  public static void Swap<T>(this IList<T> data, int x, int y)
  {
    T tmp = data[x];
    data[x] = data[y];
    data[y] = tmp;
  }

These methods seem superfluous:

  private static void SwapUpwards(List<long> list, int indexToSwap)
  {
    long temporalValueHolder = list[indexToSwap];
    list[indexToSwap] = list[indexToSwap + 1];
    list[indexToSwap + 1] = temporalValueHolder;
  }

  private static void SwapDownwards(List<long> list, int indexToSwap)
  {
    long temporalValueHolder = list[indexToSwap - 1];
    list[indexToSwap - 1] = list[indexToSwap];
    list[indexToSwap] = temporalValueHolder;
  }

as it's just a matter of calling a general Swap function with the right indices.


In my opinion it is wrong to have a static method that takes a list of data, sort it and return a reference to it:

public static List<long> SortAscending(List<long> unsortedList)
{
  ...
  return unsortedList;
}

I would expect the input argument list to be left untouched and that the method returns a new sorted list. The IEnumerable<T>.OrderBy() works like that and on the other hand List<T>.Sort() sorts the current instance, and returns void.

I would choose either to return void and sort the argument list or return a sorted copy of the original list.


It is always a good idea to be precise and descriptive when it comes to naming of variables and methods, and it is always a question of habits and conventions. In my opinion your naming of the variables in these algorithms is too "verbose" and they make two rather uncomplicated algorithms look more complicated than necessary.


Below I've refactored the algorithms in respect to naming, DRY-principle, and I have tried to generalize them as generic extension methods:

public static class SortExtensions
{
  public static void Swap<T>(this IList<T> data, int x, int y)
  {
    T tmp = data[x];
    data[x] = data[y];
    data[y] = tmp;
  }

  public static void BubbleSort<T>(this IList<T> data, bool ascending = true, IComparer<T> comparer = null)
  {
    if (data == null || data.Count < 2) return;

    comparer = comparer ?? Comparer<T>.Default;
    Func<T, T, bool> mustSwap = ascending ? (Func<T, T, bool>)((a, b) => comparer.Compare(a, b) > 0) : ((a, b) => comparer.Compare(a, b) < 0);

    int maxIndex = data.Count;

    do
    {
      int newMaxIndex = 0;

      for (int index = 0; index < maxIndex - 1; index++)
      {
        if (mustSwap(data[index], data[index + 1]))
        {
          data.Swap(index, index + 1);
          newMaxIndex = index + 1;
        }
      }
      maxIndex = newMaxIndex;
    } while (maxIndex > 0);
  }

  public static void CocktailSort<T>(this IList<T> data, bool ascending = true, IComparer<T> comparer = null)
  {
    if (data == null || data.Count < 2) return;

    comparer = comparer ?? Comparer<T>.Default;
    Func<T, T, bool> mustSwap = ascending ? (Func<T, T, bool>)((a, b) => comparer.Compare(a, b) > 0) : ((a, b) => comparer.Compare(a, b) < 0);

    int startIndex = 0;
    int endIndex = data.Count;
    bool swapped = false;

    do
    {
      swapped = false;
      for (int index = startIndex; index < endIndex - 1; index++)
      {
        if (mustSwap(data[index], data[index + 1]))
        {
          swapped = true;
          data.Swap(index, index + 1);
        }
      }

      endIndex--;
      if (!swapped)
        break;

      for (int index = endIndex; index > startIndex; index--)
      {
        if (mustSwap(data[index - 1], data[index]))
        {
          swapped = true;
          data.Swap(index, index - 1);
        }
      }

      startIndex++;
    } while (swapped);
  }
}
\$\endgroup\$
  • 1
    \$\begingroup\$ Thanks for all the insight, this has been really helpful! \$\endgroup\$ – Oscar Guillamon Oct 17 '18 at 8:14
1
\$\begingroup\$

Separate for ascending and descending is a lot of duplicate code. Just pass ascending and descending to a general routine.

if (!anyElementSwapped)
   break;
anyElementSwapped = false;

anyElementSwapped = false; is pointless.

if (unsortedList.Count.Equals(currentElementIndex + 1))
{
   continue;
}

Is pointless and extra processing. Just let the next condition fail.

\$\endgroup\$
  • \$\begingroup\$ Oh, the anyElementSwapped is from a copypaste when bringing the code from bubblesort, thanks for pointing that out \$\endgroup\$ – Oscar Guillamon Oct 16 '18 at 21:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.