Bubble sort using recursion in C#

Question

I've wrote this simple piece of code. And I have a slight problem with it.

int [] x = [50,70,10,12,129];
sort(x, 0,1);
sort(x, 1,2);
sort(x, 2,3);
sort(x, 3,4);

for(int i = 0; i < 5; i++) 
 Console.WriteLine(x[i]);

static int [] sort(int [] x, int i, int j)
{
   if(j ==x.length) 
      return x;
   else if(x[i]>x[j])
   {
      int temp = x[i];
      x[i] = x[j];
      x[j] = temp;
      return sort(x, i, j+1);
    }
    else 
       return sort(x, i, j+1);
}

I feel that calling sort 4 time isn't the best soultion. I need a way to handle this using sort() also. I also ask you for your advice, suggestion, or tip. Thanks

Is there a reason you are rolling your own sort() method rather than using Array.Sort() or List.Sort()? — LBushkin, Oct 29 '09 at 15:16

score 3 · Answer 1 · answered Oct 29 '09 at 15:27

3

A simple bubblesort shouldn't need recursion. You could do something like this, just passing in the array to sort:

public int[] Sort(int[] sortArray)
    {
        for (int i = 0; i < sortArray.Length - 1; i++)
        {
            for (int j = sortArray.Length - 1; j > i; j--)
            {
                if (sortArray[j] < sortArray[j - 1])
                {
                    int x = sortArray[j];
                    sortArray[j] = sortArray[j - 1];
                    sortArray[j - 1] = x;

                }
            }
        }
        return sortArray;
    }

answered Oct 29 '09 at 15:27

Robban

6,729
2
39
47

3

Hmm, "need" when applied to recursive algorithms is always an interesting one and if this is an exercise in self education then wanting to use recursion is not unreasonable. – Murph Oct 29 '09 at 15:37
1

Maybe Robban should have said that bubble sort doesn't *lend* itself to recursion. It might be more educational to code recursive sort with an algorithm that's designed for recursion. Of course that depends on what the OP is looking to learn. – Michael Burr Oct 29 '09 at 15:46
I can do it without recursion. But, I just wanted to see how things will go if I used recursion. It's just curiosity! – Loai Abdelhalim Oct 29 '09 at 17:48

score 3 · Accepted Answer · answered Oct 29 '09 at 15:36

Firstly, your sort is restricted to ints, however you can use the IComparable<T> interface to extend it to any comparable type. Alternatively you could have another parameter for a Comparer<T> to allow the user to define how to compare items in the input.

A recursive bubble sort would probably look something like this: (NOTE: not tested...)

public static T[] BubbleSort(T[] input) where T : IComparable<T>
{
    return BubbleSort(input, 0, 0);
}

public static T[] BubbleSort(T[] input, int passStartIndex, int currentIndex) where T : IComparable<T>
{
    if(passStartIndex == input.Length - 1) return input;
    if(currentIndex == input.Length - 1) return BubbleSort(input, passStartIndex+1, passStartIndex+1);

    //compare items at current index and current index + 1 and swap if required
    int nextIndex = currentIndex + 1;
    if(input[currentIndex].CompareTo(input[nextIndex]) > 0)
    {
        T temp = input[nextIndex];
        input[nextIndex] = input[currentIndex];
        input[currentIndex] = temp;
    }

    return BubbleSort(input, passStartIndex, currentIndex + 1);
}

However, an iterative solution would probably be more efficient and easier to understand...

score 2 · Answer 3 · answered Oct 29 '09 at 15:35

Nothing wrong with wanting to learn - couple of obvious things.

Firstly you're already aware that there's a length property for the array - so you could use that to create a loop that gets rid of the multiple calls to sort at the start and makes the length of the array a non problem.

Secondly you might want to think about the way the sort works - how about this: you're attempting to bubble a value up to its correct place in the list (or down if you prefer!) - so for a list of n items, remove the first, sort the remaining n - 1 items (that's the recursive bit) then bubble the first item into place.

Been decades since I thought about this, fun!

score 0 · Answer 4 · answered Oct 29 '09 at 15:44

another one with only 2 params :p yeah :

static void Sort(IList<int> data)
{
    Sort(data, 0);
}

static void Sort(IList<int> data, int startIndex)
{
    if (startIndex >= data.Count) return;

    //find the index of the min value
    int minIndex = startIndex;
    for (int i = startIndex; i < data.Count; i++)
        if (data[i] < data[minIndex])
            minIndex = i;

    //exchange the values
    if (minIndex != startIndex)
    {
        var temp = data[startIndex];
        data[startIndex] = data[minIndex];
        data[minIndex] = temp;
    }

    //recurring to the next
    Sort(data, startIndex + 1);
}

Note : This is completly useless in real life because - its extremely slow - its recursion iteration is linear meaning that when you have more than 1k items, it will stackoverflow

Bubble sort using recursion in C#

4 Answers4

Linked