I want an efficient sorting algorithm to sort an array

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!

it is bubble sort, because the maximum number goes up like a bubble. — Valentin
– Valentin, Commented Feb 26, 2016 at 14:15
Your goal is not quite clear. If you need just to sort an array - then Array.Sort method is pretty sufficient. If you need to implement insertion sort for some educational reasons - well, try implement it and come back when you're stuck somewhere with concrete question. — Andrey Korneyev
– Andrey Korneyev, Commented Feb 26, 2016 at 14:18
Do you want to know which kind of algorithm this ocde is or do you need a more efficient (whatever this means) one? — MakePeaceGreatAgain
– MakePeaceGreatAgain, Commented Feb 26, 2016 at 14:19
in this example what is data... as i was expecting to see array.length — Seabizkit
– Seabizkit, Commented Feb 26, 2016 at 14:22
If you want an efficient sort, use the sorting provided by the .Net framework. If your goal is to implement insertion sort (which is not at the top of the efficient sort list), then learn the algorithm and implement it. — crashmstr
– crashmstr, Commented Feb 26, 2016 at 14:24

fubo · Accepted Answer · 2016-02-26 14:30:40Z

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

Ashkan Mobayen Khiabani · Accepted Answer · 2016-02-26 14:24:03Z

4

Just do this:

 Array.Sort(data);

edited Feb 26, 2016 at 14:24

answered Feb 26, 2016 at 14:17

Ashkan Mobayen Khiabani

34.3k35 gold badges111 silver badges187 bronze badges

7 Comments

xanatos Over a year ago

Why are you using the .ToList()? List<T> implements the .Sort()

Ashkan Mobayen Khiabani Over a year ago

well Eshqna mentioned its an Array and no a list

Andrey Korneyev Over a year ago

Why bother with List at all? Why don't just Array.Sort?

Ashkan Mobayen Khiabani Over a year ago

Arrays does not have a sort method, Lists have

Andrey Korneyev Over a year ago

@AshkanMobayenKhiabani Sort is static method of Array class.

|

kemiller2002 · Accepted Answer · 2016-02-26 14:29:14Z

1

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

answered Feb 26, 2016 at 14:29

kemiller2002

116k28 gold badges201 silver badges255 bronze badges

Collectives™ on Stack Overflow

I want an efficient sorting algorithm to sort an array

3 Answers 3

Comments

7 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

7 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related