C# Sorting algorithms implementation

Question

C# Sorting algorithms implementation

Jack Herer 140

Hey guys... this post will contain several sorting algorthm implementations in C#.

Follow for more content like this :)

Jack Herer 140

Bubble sort implementation:

int[] array = { 108, 23, 69, 420, 9 };
int temporary;

for (int j = 0; j <= array.Length - 2; j++)
{
    for (int i = 0; i <= array.Length - 2; i++)
    {
        if (array[i] > array[i + 1])
        {
            temporary= array[i + 1];
            array[i + 1] = array[i];
            array[i] = temporary;
        }
    }
}

Console.WriteLine("Sorted:");
foreach (int p in array)
{
    Console.Write($"{p} ");
}
Console.ReadLine();

Jack Herer 140 Reputation points

2023-04-26T17:52:59.39+00:00
This sort splits array to half, in the first half are sorted elements and in the other are unsorted It takes firstly values that are smallest or largest, after getting them (lets say the smallest) it moves them to she start of array and after that, the array gets smaller

Select sort implementation:

int[] array = { 108, 23, 69, 420, 9 }; for (int i = 0; i < array.Length - 1; i++) { int smallestVal = i; for (int j = i + 1; j < array.Length; j++) { if (array[j] < array[smallestVal]) { smallestVal = j; } } int temporary = array[smallestVal]; array[smallestVal] = array[i]; array[i] = temporary; }

Jack Herer 140

Insertion Sort is a simple sorting algorithm that builds the resulting sorted array on an item-by-item basis using matching. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort or merge sort

Insertion sort implementation:

int[] array = new int[10] { 23, 9, 85, 12, 99, 34, 60, 15, 100, 1 };
int n = 10;
int value;
int flag;

for (int i = 1; i < n; i++)
{
    value = array[i];
    flag = 0;
    for (int j = i - 1; j >= 0 && flag != 1;)
    {
        if (value < array[j])
        {
            array[j + 1] = array[j];
            j--;
            array[j + 1] = value;
        }
        else flag = 1;
    }
}
Console.Write("Seřazeno: ");
for (int i = 0; i < n; i++)
{
    Console.Write(array[i] + " ");
}

Jack Herer 140

Quick Sort is done by splitting the list into two parts Initially, a pivot element is selected using the splitting algorithm The left part of the pivot stores smaller values than the pivot and the right part stores larger values After splitting, each separate list is split using the same procedure

Quick sort implementation:

class QuickSort
    {
        public static void Sort(int[] arr, int left, int right)
        {
            if (left < right)
            {
                int pivot = Partition(arr, left, right);
 
                Sort(arr, left, pivot - 1);
                Sort(arr, pivot + 1, right);
            }
        }
 
        private static int Partition(int[] arr, int left, int right)
        {
            int pivot = arr[right];
            int i = left - 1;
 
            for (int j = left; j < right; j++)
            {
                if (arr[j] <= pivot)
                {
                    i++;
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
 
            int temp1 = arr[i + 1];
            arr[i + 1] = arr[right];
            arr[right] = temp1;
 
            return i + 1;
        }
 
        static void Main()
        {
            int[] ints = { 8, 875, 7, 9, 764, 55 };
 
            Console.WriteLine("Original array:");
            foreach (int i in ints)
            {
                Console.WriteLine(i);
            }
 
 
            Sort(ints, 0, 5);
            
            Console.WriteLine("Sorted array:");
 
            foreach (int i in ints)
            {
                Console.WriteLine(i);
            }
        }
    }

Jack Herer 140

Merge Sort is a recursive sorting algorithm that uses the Divide() and Conquer() methods It divides the array into two parts and then calls itself for each of the two parts This process continues until the array is sorted It is good for sorting Linked Lists Is stable, meaning that the same elements in the array retain their original relative positions

Merge sort implementation:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Merge_sort
{    
    class Program
    {
        static void Main(string[] args)
        {
            List<int> unsorted = new List<int>();
            List<int> sorted;

            Random random = new Random();

            Console.WriteLine("Original array elements:" );
            for(int i = 0; i< 10;i++)
            {
                unsorted.Add(random.Next(0,100));
                Console.Write(unsorted[i]+" ");
            }
            Console.WriteLine();

            sorted = MergeSort(unsorted);

            Console.WriteLine("Sorted array elements: ");
            foreach (int x in sorted)
            {
                Console.Write($"{x} ");
            }
        }
		

        private static List<int> MergeSort(List<int> unsorted)
        {
            if (unsorted.Count <= 1)
                return unsorted;

            List<int> left = new List<int>();
            List<int> right = new List<int>();

            int middle = unsorted.Count / 2;
            for (int i = 0; i < middle;i++)  //Dividing the unsorted list
            {
                left.Add(unsorted[i]);
            }

            for (int i = middle; i < unsorted.Count; i++)
            {
                right.Add(unsorted[i]);
            }

            left = MergeSort(left);
            right = MergeSort(right);
            return Merge(left, right);
        }

        private static List<int> Merge(List<int> left, List<int> right)
        {
            List<int> result = new List<int>();

            while(left.Count > 0 || right.Count>0)
            {
                if (left.Count > 0 && right.Count > 0)
                {
                    if (left.First() <= right.First())
                    {
                        result.Add(left.First());
                        left.Remove(left.First());
                    }
                    else
                    {
                        result.Add(right.First());
                        right.Remove(right.First());
                    }
                }
                else if(left.Count>0)
                {
                    result.Add(left.First());
                    left.Remove(left.First());
                }
                else if (right.Count > 0)
                {
                    result.Add(right.First());

                    right.Remove(right.First());    
                }    
            }
            return result;
        }
    }
}

Jack Herer 140

Heap Sort is a sorting algorithm that uses the heap data structure Each time the root element of the heap, i.e. the largest element, is removed and stored in an array It is replaced by the leaf element furthest to the right, and then the heap is recreated This is done until no more elements remain in the heap and the array is sorted

Heap sort implementation:

public static void Main()
{
    int[] array = {55, 25, 89, 34, 12, 19, 78, 95, 1, 100};
    int n = 10, i;
    HeapSort(array, 10);
    Console.Write("Sorted: ");
    for (i = 0; i < n; i++)
    {
        Console.Write(array[i] + " ");
    }
    Console.ReadKey();
}
    static void HeapSort(int[] array, int n)
    {
        for (int i = n / 2 - 1; i >= 0; i--)
        {
            Heapify(array, n, i);
        }

        for (int i = n-1; i>=0; i--)
        {
            int temporary = array[0];
            array[0] = array[i];
            array[i] = temporary;

            Heapify(array, i, 0);
        }
    }

    static void Heapify(int[] array, int n, int i)
    {
        int largest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;

        if (left < n && array[left] > array[largest])
        {
            largest = left;
        }
        
        if (right < n && array[right] > array[largest])
        {
            largest = right;
        }

        if (largest != i) 
        {
            int swap = array[i];
            array[i] = array[largest];
            array[largest] = swap;
            Heapify(array, n, largest);
        }
    }

David McCarter 1 Reputation point MVP

2023-05-03T16:49:27.03+00:00

Are you asking a question?
roy 0 Reputation points

2024-12-19T14:49:01.21+00:00

Excellent content for learning sorting algorithms. Followed you. Thank you!
Karen Payne MVP 35,591 Reputation points Volunteer Moderator

2024-12-21T11:40:09.3833333+00:00

Rather than sharing information here which is for asking questions, best to write an article on a site such as https://dev.to/ that is backed up with a GitHub repository.

1 answer

Your answer

Jack Herer 140 Reputation points

2023-04-26T17:52:37.19+00:00

Bubble sort implementation:

int[] array = { 108, 23, 69, 420, 9 }; int temporary; for (int j = 0; j <= array.Length - 2; j++) { for (int i = 0; i <= array.Length - 2; i++) { if (array[i] > array[i + 1]) { temporary= array[i + 1]; array[i + 1] = array[i]; array[i] = temporary; } } } Console.WriteLine("Sorted:"); foreach (int p in array) { Console.Write($"{p} "); } Console.ReadLine();
Jack Herer 140 Reputation points

2023-04-26T17:52:59.39+00:00

This sort splits array to half, in the first half are sorted elements and in the other are unsorted It takes firstly values that are smallest or largest, after getting them (lets say the smallest) it moves them to she start of array and after that, the array gets smaller

Select sort implementation:

int[] array = { 108, 23, 69, 420, 9 }; for (int i = 0; i < array.Length - 1; i++) { int smallestVal = i; for (int j = i + 1; j < array.Length; j++) { if (array[j] < array[smallestVal]) { smallestVal = j; } } int temporary = array[smallestVal]; array[smallestVal] = array[i]; array[i] = temporary; }
Jack Herer 140 Reputation points

2023-04-26T17:53:17.2033333+00:00

Insertion Sort is a simple sorting algorithm that builds the resulting sorted array on an item-by-item basis using matching. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort or merge sort

Insertion sort implementation:

int[] array = new int[10] { 23, 9, 85, 12, 99, 34, 60, 15, 100, 1 }; int n = 10; int value; int flag; for (int i = 1; i < n; i++) { value = array[i]; flag = 0; for (int j = i - 1; j >= 0 && flag != 1;) { if (value < array[j]) { array[j + 1] = array[j]; j--; array[j + 1] = value; } else flag = 1; } } Console.Write("Seřazeno: "); for (int i = 0; i < n; i++) { Console.Write(array[i] + " "); }
Jack Herer 140 Reputation points

2023-04-26T17:55:11.12+00:00

Quick Sort is done by splitting the list into two parts Initially, a pivot element is selected using the splitting algorithm The left part of the pivot stores smaller values than the pivot and the right part stores larger values After splitting, each separate list is split using the same procedure

Quick sort implementation:

class QuickSort { public static void Sort(int[] arr, int left, int right) { if (left < right) { int pivot = Partition(arr, left, right); Sort(arr, left, pivot - 1); Sort(arr, pivot + 1, right); } } private static int Partition(int[] arr, int left, int right) { int pivot = arr[right]; int i = left - 1; for (int j = left; j < right; j++) { if (arr[j] <= pivot) { i++; int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } int temp1 = arr[i + 1]; arr[i + 1] = arr[right]; arr[right] = temp1; return i + 1; } static void Main() { int[] ints = { 8, 875, 7, 9, 764, 55 }; Console.WriteLine("Original array:"); foreach (int i in ints) { Console.WriteLine(i); } Sort(ints, 0, 5); Console.WriteLine("Sorted array:"); foreach (int i in ints) { Console.WriteLine(i); } } }
Jack Herer 140 Reputation points

2023-04-26T17:58:05.85+00:00

Merge Sort is a recursive sorting algorithm that uses the Divide() and Conquer() methods It divides the array into two parts and then calls itself for each of the two parts This process continues until the array is sorted It is good for sorting Linked Lists Is stable, meaning that the same elements in the array retain their original relative positions

Merge sort implementation:

using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace Merge_sort { class Program { static void Main(string[] args) { List<int> unsorted = new List<int>(); List<int> sorted; Random random = new Random(); Console.WriteLine("Original array elements:" ); for(int i = 0; i< 10;i++) { unsorted.Add(random.Next(0,100)); Console.Write(unsorted[i]+" "); } Console.WriteLine(); sorted = MergeSort(unsorted); Console.WriteLine("Sorted array elements: "); foreach (int x in sorted) { Console.Write($"{x} "); } } private static List<int> MergeSort(List<int> unsorted) { if (unsorted.Count <= 1) return unsorted; List<int> left = new List<int>(); List<int> right = new List<int>(); int middle = unsorted.Count / 2; for (int i = 0; i < middle;i++) //Dividing the unsorted list { left.Add(unsorted[i]); } for (int i = middle; i < unsorted.Count; i++) { right.Add(unsorted[i]); } left = MergeSort(left); right = MergeSort(right); return Merge(left, right); } private static List<int> Merge(List<int> left, List<int> right) { List<int> result = new List<int>(); while(left.Count > 0 || right.Count>0) { if (left.Count > 0 && right.Count > 0) { if (left.First() <= right.First()) { result.Add(left.First()); left.Remove(left.First()); } else { result.Add(right.First()); right.Remove(right.First()); } } else if(left.Count>0) { result.Add(left.First()); left.Remove(left.First()); } else if (right.Count > 0) { result.Add(right.First()); right.Remove(right.First()); } } return result; } } }
Jack Herer 140 Reputation points

2023-04-26T17:58:51.7666667+00:00

Heap Sort is a sorting algorithm that uses the heap data structure Each time the root element of the heap, i.e. the largest element, is removed and stored in an array It is replaced by the leaf element furthest to the right, and then the heap is recreated This is done until no more elements remain in the heap and the array is sorted

Heap sort implementation:

public static void Main() { int[] array = {55, 25, 89, 34, 12, 19, 78, 95, 1, 100}; int n = 10, i; HeapSort(array, 10); Console.Write("Sorted: "); for (i = 0; i < n; i++) { Console.Write(array[i] + " "); } Console.ReadKey(); } static void HeapSort(int[] array, int n) { for (int i = n / 2 - 1; i >= 0; i--) { Heapify(array, n, i); } for (int i = n-1; i>=0; i--) { int temporary = array[0]; array[0] = array[i]; array[i] = temporary; Heapify(array, i, 0); } } static void Heapify(int[] array, int n, int i) { int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left < n && array[left] > array[largest]) { largest = left; } if (right < n && array[right] > array[largest]) { largest = right; } if (largest != i) { int swap = array[i]; array[i] = array[largest]; array[largest] = swap; Heapify(array, n, largest); } }
David McCarter 1 Reputation point MVP

2023-05-03T16:49:27.03+00:00

Are you asking a question?
roy 0 Reputation points

2024-12-19T14:49:01.21+00:00

Excellent content for learning sorting algorithms. Followed you. Thank you!
Karen Payne MVP 35,591 Reputation points Volunteer Moderator

2024-12-21T11:40:09.3833333+00:00

Rather than sharing information here which is for asking questions, best to write an article on a site such as https://dev.to/ that is backed up with a GitHub repository.

Answer 1

I just created couple algorithms for sorting with and w/out creating new array.

    public static T[] SortT<T>(T[] a) where T:IComparable<T>

    {

        T[] result = new T[a.Length];

        int current = 0;

        for (int i = 0; i < a.Length; i++)

        {

            current = 0;

            for (int j = 0; j < a.Length; j++)

            {

                if (a[i].CompareTo(a[j])>0)

                    current++;

            }

            result[current] = a[i];

        }

        for (int i = 1; i < result.Length; i++)

            if (result[i].CompareTo(default(T))==0)

                result[i] = result[i - 1];

        return result;

    }

    // for sorting big data class w/out creating new Tarray.

    public static void SortSwapT<T>(ref T[] a) where T:IComparable<T>

    {

        int[] indCurrent = new int[a.Length];

        Dictionary<int, int> currentInd = new Dictionary<int, int>();

        int current;

        for (int i = 0; i < a.Length; i++)

        {

            current = 0;

            for (int j = 0; j < a.Length; j++)

            {

                if (a[i].CompareTo(a[j])>0)

                    current++;

            }

            indCurrent[i] = current;

        }

        for (int i = 0; i < indCurrent.Length; i++)

        {

            while (currentInd.ContainsKey(indCurrent[i]))

                indCurrent[i] += 1;

            currentInd.Add(indCurrent[i], i);

        }

        T temp;

        for (int i = 0; i < a.Length - 1; i++)

        {

            temp = a[i];

            a[i] = a[currentInd[i]];

            a[currentInd[i]] = temp;

            currentInd[indCurrent[i]] = currentInd[i];

            indCurrent[currentInd[i]] = indCurrent[i];

        }

    }

Share via

C# Sorting algorithms implementation

1 answer

Your answer