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

Answer 1

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!

Answer 2

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...

Answer 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;
    } 

Answer 4

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