What's the most elegant way to bubble-sort in C#?

Question

Can this be cleaned up?

using System;  
class AscendingBubbleSort 
{     
    public static void Main()
    {
        int i = 0,j = 0,t = 0;
        int []c=new int[20];
        for(i=0;i<20;i++)
        {
            Console.WriteLine("Enter Value p[{0}]:", i);
            c[i]=int.Parse(Console.ReadLine());
        }
        // Sorting: Bubble Sort
        for(i=0;i<20;i++)
        {
            for(j=i+1;j<20;j++)
            {
                if(c[i]>c[j])
                {
                    Console.WriteLine("c[{0}]={1}, c[{2}]={3}", i, c[i], j, c[j]);
                    t=c[i];
                    c[i]=c[j];
                    c[j]=t;
                }
            }
        }
        Console.WriteLine("bubble sorted array:");
        // sorted array output
        for(i=0;i<20;i++)
        {
            Console.WriteLine ("c[{0}]={1}", i, c[i]);
        }
    }
}

Solution 1

What you've pasted there isn't a bubble sort. It's a sort of "brute force" sort but it's not bubble sort. Here's an example of a generic bubble sort. 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<T>, which includes arrays. Read the above link (to Wikipedia) to get more of an idea of how bubble sort is meant to work. Note how on each loop we go through from start to finish, but only compare each item with its neighbour. It's still an O(n²) sort algorithm, but in many cases it will be quicker than the version you've given.

public void BubbleSort<T>(IList<T> list)
{
    BubbleSort<T>(list, Comparer<T>.Default);
}

public void BubbleSort<T>(IList<T> list, IComparer<T> comparer)
{
    bool stillGoing = true;
    while (stillGoing)
    {
        stillGoing = false;
        for (int i = 0; i < list.Count-1; 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;
            }
        }
    }
}

Solution 2

The most elegant way to sort in C# is

Array.Sort( object[] )

That will work everywhere except in homework problems where the teacher asked you to implement the non-elegant bubble sort algorithm. ;-)

Solution 3

Overall, there's nothing wrong with your bubble sort implementation. If I were doing a real code review, I'd make the following changes:

Choose more descriptive variable names

Why is your array just called c?

Minimize variable scope

All of your variables are declared at the top of the function. Unless this is a homework requirement or a coding standard, its more idiomatic to declare variables "close" to the location where they are used, preferably so they have the smallest amount of scope possible.

So, eliminate the first line which reads int i = 0,j = 0,t = 0;. Declare loop counters inline:

for(int i = 0; i < 20; i++)

And declare your temp variable in the place where its used:

                Console.WriteLine("c[{0}]={1}, c[{2}]={3}", i, c[i], j, c[j]);
                int t=c[i];
                c[i]=c[j];
                c[j]=t;

Eliminate hard-coded array bounds.

This:

for(i=0;i<20;i++)

Becomes this:

for(i = 0; i < c.Length; i++)

Solution 4

Most people would not bother making a bubble sort elegant. In general, though, I find that doing this:

for (int i = 0; i < items.Length; i++) {
    Item item = items[i];
    // do something with item
}

is both more elegant and more maintainable than doing this:

Item item;
int i;
for (i = 0; i < items.Length; i++) {
    item = items[i];
    // do something with item
}

In other words, declare your variables within the smallest applicable scope. Otherwise you might find yourself doing something with i or item at some other point in the code and then using them again where you shouldn't be.

Solution 5

• I would use a swap methed to swap the two array items. (details of how to write swap method left as homework!)

• You should think about the case when the items are already in order

• You should read up on Insertion sort for more marks :-)

• Rather then reading the test data from the keyboard, see if you can learn how to use nUnit

View more solutions

Comments

[Randolpho]

That wasn't there when I wrote this answer. But yeah, it's prolly homework.

[BFree]

And, this is actually wrong. If you look at the MS documentation, Array.Sort uses a QuickSort not a BubbleSort :)

[Sam Harwell]

@Ian: Not everyone who comes here is working on homework. With this answer, they'll find what they're looking for and can move on to the next problem. :)

[Henk Holterman]

I am (seriously) confused why you think this is a 'more real' bubble sort than the original. Both are bubbling, with different optimizations. Your version neglects to shrink the range.

[Jon Skeet]

@Henk: Take a look at the wikipedia article. Does the algorithm described there look anything like the original? In particular, the OP's code compares arbitrary pairs, immediately going against the "comparing each pair of adjacent items" part of the description of the algorithm. It's certainly a brute force swapping sort, but it's not a bubble sort.

[bcat]

It does matter when the question is specifically asking about bubble sort.

[gotgot1995]

Ian, I voted this up because your point about the swap method is valid. Just FYI though, someone added the homework tag, but I asked this to make a point at work.

[Henk Holterman]

Jon, you're right, i misread the if(c[i]>c[j]) part. I've seen similar loops doing if(c[j]>c[j+1]) and that's bubbling.