Sorting Algorithms

Sorting refers to rearrangement of a given array or list of elements according to a comparison

operator on the elements. The comparison operator is used to decide the new order of elements in
the respective data structure. Sorting means reordering of all the elements either in ascending or in
descending order.

Sorting Terminology:

 In-place Sorting: An in-place sorting algorithm uses constant space for producing the output
(modifies the given array only) or copying elements to a temporary storage. Examples:
Selection Sort, Bubble Sort Insertion Sort and Heap Sort.

 Internal Sorting: Internal Sorting is when all the data is placed in the main
memory or internal memory. In internal sorting, the problem cannot take input beyond its
size. Example: heap sort, bubble sort, selection sort, quick sort, shell sort, insertion sort.

 External Sorting : External Sorting is when all the data that needs to be sorted cannot be
placed in memory at a time, the sorting is called external sorting. External Sorting is used for
the massive amount of data. Examples: Merge sort, Tag sort, Polyphase sort, Four tape sort,
External radix sort, etc.

 Stable sorting: When two same items appear in the same order in sorted data as in the
original array called stable sort. Examples: Merge Sort, Insertion Sort, Bubble Sort.

 Unstable sorting: When two same data appear in the different order in sorted data it is
called unstable sort. Examples: Selection Sort, Quick Sort, Heap Sort, Shell Sort.

Characteristics of Sorting Algorithms:

 Time Complexity: Time complexity, a measure of how long it takes to run an algorithm, is
used to categorize sorting algorithms. The worst-case, average-case, and best-case
performance of a sorting algorithm can be used to quantify the time complexity of the
process.

 Auxiliary Space : This is the amount of extra space (apart from input array) needed to sort.
For example, Merge Sort requires O(n) and Insertion Sort O(1) auxiliary space

 Stability: A sorting algorithm is said to be stable if the relative order of equal elements is
preserved after sorting. This is important in certain applications where the original order of
equal elements must be maintained.

 In-Place Sorting: An in-place sorting algorithm is one that does not require additional
memory to sort the data. This is important when the available memory is limited or when
the data cannot be moved.

 Adaptivity: An adaptive sorting algorithm is one that takes advantage of pre-existing order in
the data to improve performance. For example insertion sort takes time proportional
to number of inversions in the input array.

Applications of Sorting Algorithms:

  Searching Algorithms: Sorting is often a crucial step in search algorithms like binary search
and Ternary Search. A lot of Greedy Algorithms use sorting as a first step to apply Greedy
Approach. For example Activity Selection, Fractional Knapsack, Weighted Job Scheduling, etc

 Data management: Sorting data makes it easier to search, retrieve, and analyze. For example
the order by operation in SQL queries requires sorting.

 Database optimization: Sorting data in databases improves query performance. We

preprocess the data by sorting so that efficient searching can be applied.

 Machine learning: Sorting is used to prepare data for training machine learning models.

 Data Analysis: Sorting helps in identifying patterns, trends, and outliers in datasets. It plays a
vital role in statistical analysis, financial modeling, and other data-driven fields.

 Operating Systems: Sorting algorithms are used in operating systems for tasks like task
scheduling, memory management, and file system organization

Merge Sort:
else
#include <iostream>
{
using namespace std;
arr[k]=b[j]
void mergeSort(int arr[],int l, int r)
k++;
{
j++;
if (l<r)
}
{
}
int mid=(l+r)/2;
while(i<n1)
mergeSort(arr,l,mid);
{
mergeSort(arr,mid+1,r);
arr[k]=a[i];
merge(arr, l,mid,r);
k++;
}
i++;
}
}
void merge(int arr[],int l,int mid,int r)
while(j<n2)
{
{
int n1=mid-l+1;
arr[k]=b[j];
int n2=r-mid;
k++;
int a[n1],b[n2];
j++;
for(int i=0;i< n1;i++)
}
{
}
a[i]=arr[l+i]; int main()
} {
for(int i=0;i< n2;i++) int arr[]={5,4,3,2,1};
{ // int length=sizeof(arr);
b[i]=arr[mid+1+i]; mergeSort(arr,0,4);
} for(int i=0;i<5;i++)
int i=0;j=0,k=l; {
while(i<n1 && j< n2) cout<< arr[i]<< " ";
{ }
if (a[i]< b[j]) cout<< endl;
{
return 0;
arr[k]=a[i];
}
k++;
i++;
}
 Quick Sort:

#include<bits/stdc++.h> swap(arr[l+1], arr[right]);

using namespace std; return l+1;
class QuickSort }
{ void swap(int& p, int& q)
public: {
void sort(int arr[], int size) int tmp = p;
{ p = q;
quickSort(arr, 0, size-1); q = tmp;
} }
private: };
void quickSort(int arr[], int left, int right)

{ int main()
if (left < right) {
{ int n;
int pivotIndex = partition(arr, left, right); cout<<"Enter the size of array n: \n";
quickSort(arr, left, pivotIndex-1); cin>>n;
quickSort(arr, pivotIndex+1, right); int arr[n];
} cout<<"Enter the elements of the array: \n";
} for(int i = 0;i < n;i++){
int partition(int arr[], int left, int right) cin>>arr[i];
{ }
int pivot = arr[right]; //object of the class//
int l = left - 1; QuickSort qSort;
for (int r = left; r < right; r++) qSort.sort(arr, n);
{ for(int i = 0;i < n;i++){
if (arr[r] < pivot) cout<<arr[i]<<" ";
{ } return 0;
l++; }
swap(arr[l], arr[r]);

}
Quicksort complexity

1. Time Complexity

Case Time Complexity

Best Case O(n*logn)
Average Case O(n*logn)
Worst Case O(n2)

o Best Case Complexity - In Quicksort, the best-case occurs when the pivot element is the
middle element or near to the middle element. The best-case time complexity of quicksort
is O(n*logn).

o Average Case Complexity - It occurs when the array elements are in jumbled order that is
not properly ascending and not properly descending. The average case time complexity of
quicksort is O(n*logn).

o Worst Case Complexity - In quick sort, worst case occurs when the pivot element is either
greatest or smallest element. Suppose, if the pivot element is always the last element of the
array, the worst case would occur when the given array is sorted already in ascending or
descending order. The worst-case time complexity of quicksort is O(n2).

Though the worst-case complexity of quicksort is more than other sorting algorithms such as Merge
sort and Heap sort,

2. Space Complexity

Space Complexity O(n*logn)

Stable NO

Radix Sort:

• Radix sort is the linear sorting algorithm that is used for integers.
• In Radix sort, there is digit by digit sorting is performed that is started from the least
significant digit to the most significant digit.

Complexity Analysis of Radix Sort

 Time Complexity of Radix Sort: O(d*(n + k)).

 Space Complexity of Radix Sort: O(n + k).

where d is the no. of digits, n is the total no. of elements and k is the base of the number system.

Benifits of Radix Sort

The radix sort has the following benefits:

 It is faster than other comparison-based sorting algorithms.

 It is a stable sort.

Limitations of Radix Sort:

The radix sort also has some limitations which are as follows:

 Radix sort is inefficient for sorting small data sets.

 Space Complexity is higher as compared to the other sorting algorithms.

 Processing negative numbers requires extra steps.

#include <iostream>

using namespace std;

// A utility function to get maximum

// value in arr[]

int getMax(int arr[], int n)

int mx = arr[0];

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

if (arr[i] > mx)

mx = arr[i];

return mx;

// A function to do counting sort of arr[]

// according to the digit

// represented by exp.

void countSort(int arr[], int n, int exp)

// Output array

int output[n];

int i, count[10] = { 0 };

// Store count of occurrences

// in count[]

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

count[(arr[i] / exp) % 10]++;

// Change count[i] so that count[i]

// now contains actual position

// of this digit in output[]

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

count[i] += count[i - 1];

// Build the output array

for (i = n - 1; i >= 0; i--) {

output[count[(arr[i] / exp) % 10] - 1] = arr[i];

count[(arr[i] / exp) % 10]--;

// Copy the output array to arr[],

// so that arr[] now contains sorted

// numbers according to current digit

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

arr[i] = output[i];

// The main function to that sorts arr[]

// of size n using Radix Sort

void radixsort(int arr[], int n)

// Find the maximum number to

// know number of digits

int m = getMax(arr, n);

// Do counting sort for every digit.

// Note that instead of passing digit

// number, exp is passed. exp is 10^i

// where i is current digit number

for (int exp = 1; m / exp > 0; exp *= 10)

countSort(arr, n, exp);

// A utility function to print an array

void print(int arr[], int n)

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

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

// Driver Code

int main()

int arr[] = { 170, 45, 75, 90, 802, 24, 2, 66 };

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

// Function Call

radixsort(arr, n);

print(arr, n);

return 0;

Bucket Sort:

Bucket sort is a sorting algorithm that separate the elements into multiple groups said to be buckets.
Elements in bucket sort are first uniformly divided into groups called buckets, and then they are
sorted by any other sorting algorithm. After that, elements are gathered in a sorted manner.

The basic procedure of performing the bucket sort is given as follows –

o First, partition the range into a fixed number of buckets.

o Then, toss every element into its appropriate bucket.

o After that, sort each bucket individually by applying a sorting algorithm.

o And at last, concatenate all the sorted buckets.

The advantages of bucket sort are –

o Bucket sort reduces the no. of comparisons.

o It is asymptotically fast because of the uniform distribution of elements.

The limitations of bucket sort are -

o It may or may not be a stable sorting algorithm.

o It is not useful if we have a large array because it increases the cost.

o It is not an in-place sorting algorithm, because some extra space is required to sort the
buckets.

The best and average-case complexity of bucket sort is O(n + k), and the worst-case complexity of
bucket sort is O(n2), where n is the number of items.

Bucket sort is commonly used -

 o With floating-point values.

o When input is distributed uniformly over a range.

The basic idea to perform the bucket sort is given as follows –

1. bucketSort(a[], n)

2. Create 'n' empty buckets

3. Do for each array element a[i]

4. Put array elements into buckets, i.e. insert a[i] into bucket[n*a[i]]

5. Sort the elements of individual buckets by using the insertion sort.

6. At last, gather or concatenate the sorted buckets.

7. End bucketSort

Algorithm

1. Bucket Sort(A[])

2. Let B[0....n-1] be a new array

3. n=length[A]

4. for i=0 to n-1

5. make B[i] an empty list

6. for i=1 to n

7. do insert A[i] into list B[n a[i]]

8. for i=0 to n-1

9. do sort list B[i] with insertion-sort

10. Concatenate lists B[0], B[1],........, B[n-1] together in order

11. End

Let's take an unsorted array to understand the process of bucket sort. It will be easier to understand
the bucket sort via an example.

Now, create buckets with a range from 0 to 25. The buckets range are 0-5, 5-10, 10-15, 15-20, 20-25.
Elements are inserted in the buckets according to the bucket range. Suppose the value of an item is
16, so it will be inserted in the bucket with the range 15-20. Similarly, every item of the array will
insert accordingly.

This phase is known to be the scattering of array elements.

Now, sort each bucket individually. The elements of each bucket can be sorted by using any of the
stable sorting algorithms.

At last, gather the sorted elements from each bucket in order

Now, the array is completely sorted.

Implementation of bucket sort

#include <iostream>

using namespace std;

int getMax(int a[], int n) // function to get maximum element from the given array

int max = a[0];

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

if (a[i] > max)

max = a[i];

return max;

void bucket(int a[], int n) // function to implement bucket sort

{
 int max = getMax(a, n); //max is the maximum element of array

int bucket[max], i;

for (int i = 0; i <= max; i++)

bucket[i] = 0;

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

bucket[a[i]]++;

for (int i = 0, j = 0; i <= max; i++)

while (bucket[i] > 0)

a[j++] = i;

bucket[i]--;

void printArr(int a[], int n) // function to print array elements

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

cout<<a[i]<<" ";

int main()

int a[] = {34, 42, 74, 57, 99, 84, 9, 5};

int n = sizeof(a) / sizeof(a[0]); // n is the size of array

cout<<"Before sorting array elements are - \n";

printArr(a, n);

bucket(a, n);
 cout<<"\nAfter sorting array elements are - \n";

printArr(a, n);

Output

After the execution of above code, the output will be -

bucket sort

Program: Write a program to implement bucket sort in C#.

using System;

class Bucket {

static int getMax(int[] a) // function to get maximum element from the given array

int n = a.Length;

int max = a[0];

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

if (a[i] > max)

max = a[i];

return max;

static void bucket(int[] a) // function to implement bucket sort

int n = a.Length;

int max = getMax(a); //max is the maximum element of array

int[] bucket = new int[max+1];

for (int i = 0; i <= max; i++)

bucket[i] = 0;

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

 {

bucket[a[i]]++;

for (int i = 0, j = 0; i <= max; i++)

while (bucket[i] > 0)

a[j++] = i;

bucket[i]--;

static void printArr(int[] a) /* function to print the array */

int i;

int n = a.Length;

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

Console.Write(a[i] + " ");

static void Main() {

int[] a = { 95, 50, 45, 15, 20, 10 };

Console.Write("Before sorting array elements are - \n");

printArr(a);

bucket(a);

Console.Write("\nAfter sorting array elements are - \n");

printArr(a);