The Ultimate Guide To Best Sorting Algorithms With Programs

The Ultimate Guide To Best Sorting Algorithms With Programs: Now and then we have to sort our information. Possibly we have a rundown of names or a rundown of numbers, and we need them to be all together. There is a wide range of sorting techniques, yet some are superior to other people.
(Furthermore, in a meeting, you might be asked which is ideal.) There are no best sorting techniques, it relies upon the information/circumstance. In any case, we should see when to utilize each sorting technique.


Factors In Deciding A Good Sorting Algorithm 

1 Running Time - How quick is an algorithm? We care about the average and worst-case scenarios. O(N) is godly, O(NlogN) is the standard, O(N^2) is bad, usually.

2 Space - How much extra space does a sorting algorithm need? (Set up implies no additional room is required, which is great.)

3 Stable - Will the order of equivalent information/data be preserved? For example, in [2, 4(a), 1, 5, 4(b), 3] if the first 4 (labeled as 4(a)) ends up before the second 4 (labeled as (4b)) in the sorted array, like [1, 2, 3, 4(a), 4(b), 5], then the sorting algorithm is stable.

4 Swaps - There's a cost related to swapping two components in a cluster/list. In the case of swapping is costly, at that point we might need to pick a calculation that does as not many swaps as would be prudent.

5 Is the information previously arranged? - Sometimes, the information isn't arbitrarily sorted out, which influences how a calculation performs. For instance, possibly we have sorted list and include a couple of numbers toward its finish. A few calculations improve on, for the most part, arranged information than others.

6 Will the data fit in RAM - Sometimes we have to sort data that are so huge that it won't fit into RAM, meaning we need to use a special algorithm that will work on data stored on a hard drive (The Ultimate Guide To Best Sorting Algorithms With Programs).


Top-Tier Sorting Algorithms

There are a ton of sorting methods, however since we're just taking a gander at this for an inquiry question, we'll look at the four best ones.

Selection Sort - The least difficult arranging calculation: Start at the primary component of an exhibit. Search through every one of the components left in the exhibit, and monitor which one is the smallest. If the current number is greater than the present minimum value then swap them.
Time: O(N^2).
Space: O(1).
 Stable: No.
 Swaps: O(N). In the event that information is now arranged:
O(N^2).selection sort is straightforward, yet just helpful if swaps are costly.

// C++ program for implementation of selection sort 

#include <bits/stdc++.h>

using namespace std;

  

void swap(int *xp, int *yp) 

{ 

    int temp = *xp; 

    *xp = *yp; 

    *yp = temp; 

} 

  

void selectionSort(int arr[], int n) 

{ 

    int i, j, min_idx; 

  

    // One by one move boundary of unsorted subarray 

    for (i = 0; i < n-1; i++) 

    { 

        // Find the minimum element in unsorted array 

        min_idx = i; 

        for (j = i+1; j < n; j++) 

        if (arr[j] < arr[min_idx]) 

            min_idx = j; 

  

        // Swap the found minimum element with the first element 

        swap(&arr[min_idx], &arr[i]); 

    } 

} 

  

/* Function to print an array */

void printArray(int arr[], int size) 

{ 

    int i; 

    for (i=0; i < size; i++) 

        cout << arr[i] << " "; 

    cout << endl; 

} 

  

// Driver program to test above functions 

int main() 

{ 

    int arr[] = {64, 25, 12, 22, 11}; 

    int n = sizeof(arr)/sizeof(arr[0]); 

    selectionSort(arr, n); 

    cout << "Sorted array: \n"; 

    printArray(arr, n); 

    return 0; 

} 

  

filter_none

edit
close

play_arrow

link
brightness_4
code

<?php // PHP program for implementation  // of selection sort  function selection_sort(&$arr, $n)  {     for($i = 0; $i < $n ; $i++)     {         $low = $i;         for($j = $i + 1; $j < $n ; $j++)         {             if ($arr[$j] < $arr[$low])             {                 $low = $j;             }         }                    // swap the minimum value to $ith node         if ($arr[$i] > $arr[$low])         {             $tmp = $arr[$i];             $arr[$i] = $arr[$low];             $arr[$low] = $tmp;         }     } }    // Driver Code $arr = array(64, 25, 12, 22, 11); $len = count($arr); selection_sort($arr, $len); echo "Sorted array : \n";     for ($i = 0; $i < $len; $i++)      echo $arr[$i] . " ";     // This code is contributed  // by Deepika Gupta.  ?>

chevron_right

filter_none

Output:

Sorted array: 
11 12 22 25 64

Insertion Sort - Go through every component in the exhibit. If the current element is smaller than the element to it's left, swap it left (until it's bigger than the element to it's left).
Time: O(N^2).
 Space: O(1).
Stable: Yes.
Swaps: O(N^2). If the data is already sorted:
O(N). Insertion sort is excellent if there's an already sorted list, and a bit of data is added to the end of it (and then you need to resort the whole list).

// C++ program for insertion sort 

#include <bits/stdc++.h>

using namespace std;

  

/* Function to sort an array using insertion sort*/

void insertionSort(int arr[], int n) 

{ 

    int i, key, j; 

    for (i = 1; i < n; i++)

    { 

        key = arr[i]; 

        j = i - 1; 

  

        /* Move elements of arr[0..i-1], that are 

        greater than key, to one position ahead 

        of their current position */

        while (j >= 0 && arr[j] > key)

        { 

            arr[j + 1] = arr[j]; 

            j = j - 1; 

        } 

        arr[j + 1] = key; 

    } 

} 

  

// A utility function to print an array of size n 

void printArray(int arr[], int n) 

{ 

    int i; 

    for (i = 0; i < n; i++) 

        cout << arr[i] << " "; 

    cout << endl;

} 

  

/* Driver code */

int main() 

{ 

    int arr[] = { 12, 11, 13, 5, 6 }; 

    int n = sizeof(arr) / sizeof(arr[0]); 

  

    insertionSort(arr, n); 

    printArray(arr, n); 

  

    return 0; 

} 

  

filter_none

edit
close

play_arrow

link
brightness_4
code

<?php  // PHP program for insertion sort    // Function to sort an array // using insertion sort function insertionSort(&$arr, $n) {     for ($i = 1; $i < $n; $i++)     {         $key = $arr[$i];         $j = $i-1;                // Move elements of arr[0..i-1],         // that are    greater than key, to          // one position ahead of their          // current position         while ($j >= 0 && $arr[$j] > $key)         {             $arr[$j + 1] = $arr[$j];             $j = $j - 1;         }                    $arr[$j + 1] = $key;     } }    // A utility function to // print an array of size n function printArray(&$arr, $n) {     for ($i = 0; $i < $n; $i++)         echo $arr[$i]." ";     echo "\n"; }    // Driver Code $arr = array(12, 11, 13, 5, 6); $n = sizeof($arr); insertionSort($arr, $n); printArray($arr, $n);    // This code is contributed by ChitraNayal. ?>

chevron_right

filter_none

Output:

5 6 11 12 13

Merge Sort - Merge sort divides an array into 2 parts, forming two subarrays. It cuts those subarrays in half and repeats the process until the subarrays are one element in size. Merge sort then merges the subarrays by selectively choosing the smallest elements to put in first, and builds the subarrays back up in size until the full array is recreated, in sorted form.
Time: O(NlogN).
Space: O(N).
Stable: Yes.
 If the data is already sorted: O(NlogN).
Merge sort is great, and the technique is good for sorting data that can't fit in RAM(The Ultimate Guide To Best Sorting Algorithms With Programs).

/* C program for Merge Sort */

#include<stdlib.h>

#include<stdio.h>

  

// Merges two subarrays of arr[].

// First subarray is arr[l..m]

// Second subarray is arr[m+1..r]

void merge(int arr[], int l, int m, int r)

{

    int i, j, k;

    int n1 = m - l + 1;

    int n2 =  r - m;

  

    /* create temp arrays */

    int L[n1], R[n2];

  

    /* Copy data to temp arrays L[] and R[] */

    for (i = 0; i < n1; i++)

        L[i] = arr[l + i];

    for (j = 0; j < n2; j++)

        R[j] = arr[m + 1+ j];

  

    /* Merge the temp arrays back into arr[l..r]*/

    i = 0; // Initial index of first subarray

    j = 0; // Initial index of second subarray

    k = l; // Initial index of merged subarray

    while (i < n1 && j < n2)

    {

        if (L[i] <= R[j])

        {

            arr[k] = L[i];

            i++;

        }

        else

        {

            arr[k] = R[j];

            j++;

        }

        k++;

    }

  

    /* Copy the remaining elements of L[], if there

       are any */

    while (i < n1)

    {

        arr[k] = L[i];

        i++;

        k++;

    }

  

    /* Copy the remaining elements of R[], if there

       are any */

    while (j < n2)

    {

        arr[k] = R[j];

        j++;

        k++;

    }

}

  

/* l is for left index and r is right index of the

   sub-array of arr to be sorted */

void mergeSort(int arr[], int l, int r)

{

    if (l < r)

    {

        // Same as (l+r)/2, but avoids overflow for

        // large l and h

        int m = l+(r-l)/2;

  

        // Sort first and second halves

        mergeSort(arr, l, m);

        mergeSort(arr, m+1, r);

  

        merge(arr, l, m, r);

    }

}

  

/* UTILITY FUNCTIONS */

/* Function to print an array */

void printArray(int A[], int size)

{

    int i;

    for (i=0; i < size; i++)

        printf("%d ", A[i]);

    printf("\n");

}

  

/* Driver program to test above functions */

int main()

{

    int arr[] = {12, 11, 13, 5, 6, 7};

    int arr_size = sizeof(arr)/sizeof(arr[0]);

  

    printf("Given array is \n");

    printArray(arr, arr_size);

  

    mergeSort(arr, 0, arr_size - 1);

  

    printf("\nSorted array is \n");

    printArray(arr, arr_size);

    return 0;

}

filter_none

edit
close

play_arrow

link
brightness_4
code

# Python program for implementation of MergeSort def mergeSort(arr):     if len(arr) >1:         mid = len(arr)//2 #Finding the mid of the array         L = arr[:mid] # Dividing the array elements          R = arr[mid:] # into 2 halves            mergeSort(L) # Sorting the first half         mergeSort(R) # Sorting the second half            i = j = k = 0                    # Copy data to temp arrays L[] and R[]         while i < len(L) and j < len(R):             if L[i] < R[j]:                 arr[k] = L[i]                 i+=1             else:                 arr[k] = R[j]                 j+=1             k+=1                    # Checking if any element was left         while i < len(L):             arr[k] = L[i]             i+=1             k+=1                    while j < len(R):             arr[k] = R[j]             j+=1             k+=1    # Code to print the list def printList(arr):     for i in range(len(arr)):                 print(arr[i],end=" ")     print()    # driver code to test the above code if __name__ == '__main__':     arr = [12, 11, 13, 5, 6, 7]      print ("Given array is", end="\n")      printList(arr)     mergeSort(arr)     print("Sorted array is: ", end="\n")     printList(arr)    # This code is contributed by Mayank Khanna

chevron_right

filter_none

Output:

Given array is
12 11 13 5 6 7

Sorted array is
5 6 7 11 12 13

Quick Sort - Choose an element as the "pivot" element, and go through the array, moving all elements smaller than the pivot to the left, and all the larger elements to the right.  Then, for each "left" and "right" subarray, do the same process of picking a pivot and moving elements around(The Ultimate Guide To Best Sorting Algorithms With Programs).
Time: O(N^2) in the worst case, but usually acts like O(NlogN).
Space: O(1).
Stable: If the given data is already sorted: O(N^2) depending on the pivot's position.
Quicksort is generally quicker than merge sort, so ordinarily, it's utilized. But it does have a worst case of O(N^2) so don't choose it if we absolutely need O(NlogN) to be guaranteed.

/* C++ implementation of QuickSort */

#include <bits/stdc++.h>

using namespace std; 

  

// A utility function to swap two elements 

void swap(int* a, int* b) 

{ 

    int t = *a; 

    *a = *b; 

    *b = t; 

} 

  

/* This function takes last element as pivot, places 

the pivot element at its correct position in sorted 

array, and places all smaller (smaller than pivot) 

to left of pivot and all greater elements to right 

of pivot */

int partition (int arr[], int low, int high) 

{ 

    int pivot = arr[high]; // pivot 

    int i = (low - 1); // Index of smaller element 

  

    for (int j = low; j <= high - 1; j++) 

    { 

        // If current element is smaller than the pivot 

        if (arr[j] < pivot) 

        { 

            i++; // increment index of smaller element 

            swap(&arr[i], &arr[j]); 

        } 

    } 

    swap(&arr[i + 1], &arr[high]); 

    return (i + 1); 

} 

  

/* The main function that implements QuickSort 

arr[] --> Array to be sorted, 

low --> Starting index, 

high --> Ending index */

void quickSort(int arr[], int low, int high) 

{ 

    if (low < high) 

    { 

        /* pi is partitioning index, arr[p] is now 

        at right place */

        int pi = partition(arr, low, high); 

  

        // Separately sort elements before 

        // partition and after partition 

        quickSort(arr, low, pi - 1); 

        quickSort(arr, pi + 1, high); 

    } 

} 

  

/* Function to print an array */

void printArray(int arr[], int size) 

{ 

    int i; 

    for (i = 0; i < size; i++) 

        cout << arr[i] << " "; 

    cout << endl; 

} 

  

// Driver Code

int main() 

{ 

    int arr[] = {10, 7, 8, 9, 1, 5}; 

    int n = sizeof(arr) / sizeof(arr[0]); 

    quickSort(arr, 0, n - 1); 

    cout << "Sorted array: \n"; 

    printArray(arr, n); 

    return 0; 

} 

  

filter_none

edit
close

play_arrow

link
brightness_4
code

// C# program for implementation of QuickSort using System;    class GFG {            /* This function takes last element as pivot,     places the pivot element at its correct     position in sorted array, and places all     smaller (smaller than pivot) to left of     pivot and all greater elements to right     of pivot */     static int partition(int []arr, int low,                                    int high)     {         int pivot = arr[high];                     // index of smaller element         int i = (low - 1);          for (int j = low; j < high; j++)         {             // If current element is smaller              // than the pivot             if (arr[j] < pivot)             {                 i++;                    // swap arr[i] and arr[j]                 int temp = arr[i];                 arr[i] = arr[j];                 arr[j] = temp;             }         }            // swap arr[i+1] and arr[high] (or pivot)         int temp1 = arr[i+1];         arr[i+1] = arr[high];         arr[high] = temp1;            return i+1;     }           /* The main function that implements QuickSort()     arr[] --> Array to be sorted,     low --> Starting index,     high --> Ending index */     static void quickSort(int []arr, int low, int high)     {         if (low < high)         {                            /* pi is partitioning index, arr[pi] is              now at right place */             int pi = partition(arr, low, high);                // Recursively sort elements before             // partition and after partition             quickSort(arr, low, pi-1);             quickSort(arr, pi+1, high);         }     }        // A utility function to print array of size n     static void printArray(int []arr, int n)     {         for (int i = 0; i < n; ++i)             Console.Write(arr[i] + " ");                        Console.WriteLine();     }        // Driver program     public static void Main()     {         int []arr = {10, 7, 8, 9, 1, 5};         int n = arr.Length;         quickSort(arr, 0, n-1);         Console.WriteLine("sorted array ");         printArray(arr, n);     } }    // This code is contributed by Sam007.

chevron_right

filter_none

Output:

Sorted array:
1 5 7 8 9 10

(P.S. In reality, most quick sort calculations randomize the dataset before arranging it, to help maintain a strategic distance from the worst-case scenarios.)

(The Ultimate Guide To Best Sorting Algorithms With Programs)

A trick to choose the best algorithm:

You can follow me on Quora and ask any doubt related to sorting or any programming topic. Here's the link:  https://www.quora.com/profile/Mayank-Mewar-3