-1

I have a method which sorts items in an array which is handed to it.

Currently the method accepts an int[] as an argument. The Swap() method being called here just swaps the two indexes in the array handed as arguments.

I'm not interested in how to make a better sorting method here, just how to let it accept any array where that array contains comparable types.

Swap will also have to be updated to swap items in any type of array.

Here is what I currently have:

        static void Swap(int firstIndex, int secondIndex, int[] array)
        {
            int firstValue = array[firstIndex];
            int secondValue = array[secondIndex];
            array[firstIndex] = secondValue;
            array[secondIndex] = firstValue;
        }
        
        static void DoubleBubbleSort(int[] array)
        {
            for (int i = 0; i < array.Length -1; i++)
            {
                // if next index is smaller swap values
                if (array[i + 1] < array[i])
                {
                    Swap(i, i+1, array);
                    for (int j = i; j > 0; j--)
                    {
                        if (array[j] < array[j - 1])
                        {
                            Swap(j,j-1,array);
                        }
                        else
                        {
                            break;
                        }
                    }
                }
            }
        }

I guess I need something a bit like this for the signature of the method

DoubleBubbleSort(Array<T>) where T : Icomparable<T>

However I can't get anything like that to work. Is what I'm asking for possible? If the sort method could sort an array of anything that's sortable it would have much more utility.

For swap I guess it could be:

static void Swap(int firstIndex, int secondIndex, object[] array)
        {
            var firstValue = array[firstIndex];
            var secondValue = array[secondIndex];
            array[firstIndex] = secondValue;
            array[secondIndex] = firstValue;
        }

But I'm not sure if this could work either.

Toby Armond
  • 3
  • 5
  • Side note: I completely agree with @Servy duplicate, but that chain of duplicates currently points to older variant of comparison for generics - check out https://learn.microsoft.com/en-us/dotnet/standard/generics/math – Alexei Levenkov Mar 10 '23 at 18:15

1 Answers1

0

Make your two methods generic, and call IComparable.CompareTo()

static void Swap<T>(int firstIndex, int secondIndex, T[] array)
{
    T firstValue = array[firstIndex];
    T secondValue = array[secondIndex];
    array[firstIndex] = secondValue;
    array[secondIndex] = firstValue;
}

static void DoubleBubbleSort<T>(T[] array) where T : IComparable<T>
{
    for (int i = 0; i < array.Length - 1; i++)
    {
        // if next index is smaller swap values
        if (array[i + 1].CompareTo(array[i]) < 0)
        {
            Swap(i, i + 1, array);
            for (int j = i; j > 0; j--)
            {
                if (array[j].CompareTo(array[j - 1]) < 0)
                {
                    Swap(j, j - 1, array);
                }
                else
                {
                    break;
                }
            }
        }
    }
}

If CompareTo returns a value less than zero, this is equivalent to < for an int. If CompareTo returns 0 this is equivalent to ==, and if CompareTo returns a value greater than zero, this is equivalent to >.

Kit
  • 20,354
  • 4
  • 60
  • 103
  • Good solution. With tuples we can simplify swapping: `(a[j], a[i]) = (a[i], a[j]);` – Olivier Jacot-Descombes Mar 10 '23 at 18:05
  • While 2009 solution is ok we are now in 2023 - C#/.Net natively supports comparison operators with https://learn.microsoft.com/en-us/dotnet/standard/generics/math – Alexei Levenkov Mar 10 '23 at 18:13
  • @Kit Thanks, I knew that this must be possible. Even though this question has been flagged as a duplicate I couldn't find that anywhere. Maybe the terms I was using for the search weren't correct. – Toby Armond Mar 10 '23 at 18:51
  • @OlivierJacot-Descombes Thanks I've changed the swap method to something similar. I'm keeping the method as my class Sort will be using this a lot. – Toby Armond Mar 10 '23 at 18:52
  • @AlexeiLevenkov for sure. I didn't know what version OP was using and just along with their attempt to use `IComparable`. – Kit Mar 10 '23 at 20:30
  • 2
    @AlexeiLevenkov keep in mind some types that implement `IComparable` are not necessarily going to implement the mathematical operators. There's probably a ton of code out there like this. A full solution might be to have overloads of this method. – Kit Mar 10 '23 at 20:34
  • @Kit for real code sure, but this is clearly question of purely educational value. And for that I think ability to write bubble sort with `<` for multiple types is useful. Indeed for real library code one would give all 4 variants - `IComparable` as a constraint, `IComparisonOperators` as a constraint, IComparer as a parameter, and comparing lambda as a parameter. – Alexei Levenkov Mar 10 '23 at 21:07
  • Agree. That’s the strongest form, and what I’d do from now on. – Kit Mar 11 '23 at 18:13
  • Using .CompareTo() has actually proven to be useful. As I need to sort in either direction the fact that this yields either -1,0 or 1 rather than true or false has allowed me to multiply this by either 1 or -1 to flip the direction. – Toby Armond Mar 13 '23 at 12:23
  • @TobyArmond just be careful. `CompareTo` doesn't necessarily always return 1, 0, -1. The contract states positive, zero, negative. It's a weak contract, unfortunately, but it's rooted in a historical and conventional sense all the way back to C. – Kit Mar 13 '23 at 16:12
  • @Kit Thanks for the information, it should still work for my purposes though. I have a search method also that I would also like to make generic but if it cannot find the search term it needs to find the closest. Is there an interface that only applies to number types? Currently I find the term by computing the difference between one index up and one index down of the middle index in my binary search. Obviously strings wouldn't work in this case. – Toby Armond Mar 14 '23 at 20:47
  • I'm not sure I understand your comment fully... you may want to ask a separate question. – Kit Mar 15 '23 at 14:31