Search code examples
c#bubble-sort

Logic behind a bubble sort


I am doing a bubble sort exercise and my feeling is that it is very close to correct. As it is at the moment I am presented with an eternal loop.

Where does the fault lie ?

static void Main(string[] args)
    {
        int[] numbers = { 2, 4, 8, 5, 88, 55, 32, 55, 47, 8, 99, 120, 4, 32 };
        int temporary;
        bool sorted;
        do
        {
            sorted = false;

            for (int i = 0; i < numbers.Length - 1; i++)
            {
                int a = numbers[i];
                int b = numbers[i + 1];
                if (a > b)
                {
                    temporary = a;
                    a = b;
                    b = temporary;

                    sorted = true;

                }
            }
            Console.WriteLine("sorted");
        } while (sorted == true);


        foreach (int i in numbers)
        {
            Console.Write(i + " ");
        }

    }

Solution

  • A better approach in C# is to use a generic bubble sort

    public void BubbleSort<T>(IList<T> list);
    {
        BubbleSort<T>(list, Comparer<T>.Default);
    }
    
    public void BubbleSortImproved<T>(IList<T> list, IComparer<T> comparer)
    {
        bool stillGoing = true;
        int k = 0;
        while (stillGoing)
        {
            stillGoing = false;
            for (int i = 0; i < list.Count - 1 - k; i++)
            {
                T x = list[i];
                T y = list[i + 1];
                if (comparer.Compare(x, y) > 0)
                {
                    list[i] = y;
                    list[i + 1] = x;
                    stillGoing = true;
                }
            }
            k++;
        }
    }
    

    A brief explanation of this algorithm is given by Jon Skeet in his answer here. "It uses an arbitrary comparer, but lets you omit it in which case the default comparer is used for the relevant type. It will sort any (non-readonly) implementation of IList, which includes arrays."

    I hope this helps.