I want an efficient sorting algorithm to sort an a

Question

for (int i = 1; i < data.Count; i++) 
{
    int j = i;
    while (j > 0)
    {
        if (numarray[j - 1] > numarray[j])
        {   
            int temp = numarray[j - 1];
            numarray[j - 1] = numarray[j];
            numarray[j] = temp;
            j--;

        }

        else
            break;
    }
}

Can someone help me identify what is the sorting algorithm of the above code? I know that bubble sort is not very efficient. If I am to use insertion sort algorithm instead, how can I improve the above code. Thankyou!

Answer 1

Just do this:

 Array.Sort(data);

Answer 2

.NET has a default sort solution for arrays. Array.Sort. By default, .NET implements a Quicksort algorithm which sorts between O(n) and O(n log n). (this is much faster than a bubble sort).

You can use it by doing Array.Sort(your_array), or if you need something more complicated (like sorting objects, or sorting in reverse), there is an overload which takes in an IComparer object.

Answer 3

the most efficient way should be Array.Sort(data); which uses quicksort

some other sorting algorithms:

BubbleSort

public static void BubbleSort<T>(this List<T> source) where T : IComparable<T>
{
    IComparer<T> comparer = Comparer<T>.Default;
    for (int i = (source.Count - 1); i >= 0; i--)
    {
        for (int j = 1; j <= i; j++)
        {
            if (comparer.Compare(source[j - 1], source[j]) > 0)
            {
                var temp = source[j - 1];
                source[j - 1] = source[j];
                source[j] = temp;
            }
        }
    }
}

InsertionSort

public static void InsertionSort<T>(this List<T> source) where T : IComparable<T>
{
    IComparer<T> comparer = Comparer<T>.Default;
    int j;
    for (int i = 1; i < source.Count; i++)
    {
        var index = source[i];
        j = i;
        while ((j > 0) && comparer.Compare(source[j - 1], index) > 0)
        {
            source[j] = source[j - 1];
            j = j - 1;
        }
        source[j] = index;
    }
}

HeapSort

public static void HeapSort<T>(this List<T> source) where T : IComparable<T>
{
    int heapSize = source.Count;
    for (int p = (heapSize - 1) / 2; p >= 0; p--)
    {
        HeapSort_sub(source, heapSize, p);
    }
    for (int i = source.Count - 1; i > 0; i--)
    {
        var temp = source[i];
        source[i] = source[0];
        source[0] = temp;
        heapSize--;
        HeapSort_sub(source, heapSize, 0);
    }
}

private static void HeapSort_sub<T>(List<T> source, int heapSize, int index)
{
    IComparer<T> comparer = Comparer<T>.Default;
    int left = (index + 1) * 2 - 1;
    int right = (index + 1) * 2;
    int largest = 0;
    if (left < heapSize && comparer.Compare(source[left], source[index]) > 0)
    {
        largest = left;
    }
    else
    {
        largest = index;
    }
    if (right < heapSize && comparer.Compare(source[right], source[largest]) > 0)
    {
        largest = right;
    }
    if (largest != index)
    {
        var temp = source[index];
        source[index] = source[largest];
        source[largest] = temp;
        HeapSort_sub(source, heapSize, largest);
    }
}

QuickSort

public static void QuickSort<T>(this List<T> source) where T : IComparable<T>
{
    QuickSort_sub(source, 0, source.Count - 1);
}

private static void QuickSort_sub<T>(List<T> source, int left, int right)
{
    IComparer<T> comparer = Comparer<T>.Default;
    int i = left, j = right;
    var pivot = source[(left + right) / 2];
    while (i <= j)
    {
        while (comparer.Compare(source[i], pivot) < 0)
        {
            i++;
        }
        while (comparer.Compare(source[j], pivot) > 0)
        {
            j--;
        }
        if (i <= j)
        {
            var tmp = source[i];
            source[i] = source[j];
            source[j] = tmp;
            i++;
            j--;
        }
    }
    if (left < j)
    {
        QuickSort_sub(source, left, j);
    }
    if (i < right)
    {
        QuickSort_sub(source, i, right);
    }
}

StoogeSort

public static void StoogeSort<T>(this List<T> L) where T : IComparable
{
    StoogeSortSub(L, 0, L.Count - 1);
}

private static void StoogeSortSub<T>(List<T> L, int i, int j) where T : IComparable
{
    if (L[j].CompareTo(L[i]) < 0)
    {
        T tmp = L[i];
        L[i] = L[j];
        L[j] = tmp;
    }
    if (j - i > 1)
    {
        int t = (j - i + 1) / 3;
        StoogeSortSub(L, i, j - t);
        StoogeSortSub(L, i + t, j);
        StoogeSortSub(L, i, j - t);
    }
}

SelectionSort

public static void SelectionSort<T>(this List<T> source) where T : IComparable<T>
{
    IComparer<T> comparer = Comparer<T>.Default;
    int min;
    for (int i = 0; i < source.Count - 1; i++)
    {
        min = i;
        for (int j = i + 1; j < source.Count; j++)
        {
            if (comparer.Compare(source[j], source[min]) < 0)
            {
                min = j;
            }
        }
        var temp = source[i];
        source[i] = source[min];
        source[min] = temp;
    }
}

CocktailSort

public static void CocktailSort<T>(this List<T> A) where T : IComparable<T>
{
    IComparer<T> comparer = Comparer<T>.Default;
    bool swapped;
    do
    {
        swapped = false;
        for (int i = 0; i <= A.Count - 2; i++)
        {
            if (comparer.Compare(A[i] , A[i + 1])> -1)
            {
                T temp = A[i];
                A[i] = A[i + 1];
                A[i + 1] = temp;
                swapped = true;
            }
        }
        if (!swapped)
        {
            break;
        }
        swapped = false;
        for (int i = A.Count - 2; i >= 0; i--)
        {
            if (comparer.Compare(A[i], A[i + 1]) > -1)
            {
                T temp = A[i];
                A[i] = A[i + 1];
                A[i + 1] = temp;
                swapped = true;
            }
        }   
    } while (swapped);
}

GnomeSort

public static void GnomeSort<T>(this List<T> a) where T : IComparable<T>
{
    IComparer<T> comparer = Comparer<T>.Default;
    int i = 1, j = 2;

    while (i < a.Count)
    {
        if (comparer.Compare(a[i - 1] ,a[i])<1)
        {
            i = j;
            j++;
        }
        else
        {
            T tmp = a[i - 1];
            a[i - 1] = a[i];
            a[i] = tmp;
            i -= 1;
            if (i == 0)
            {
                i = 1;
                j = 2;
            }
        }
    }
}

ShellSort

public static void ShellSort<T>(this List<T> source) where T : IComparable<T>
{
    IComparer<T> comparer = Comparer<T>.Default;
    int j, increment;
    increment = 3;
    while (increment > 0)
    {
        for (int i = 0; i < source.Count; i++)
        {
            j = i;
            var temp = source[i];
            while ((j >= increment) && comparer.Compare(source[j - increment], temp) > 0)
            {
                source[j] = source[j - increment];
                j = j - increment;
            }
            source[j] = temp;
        }
        if (increment / 2 != 0)
        {
            increment = increment / 2;
        }
        else if (increment == 1)
        {
            increment = 0;
        }
        else
        {
            increment = 1;
        }
    }
}