Sorting
Algorithms
What issorting?
An operation that puts
(organizes) elements of alist
(a collection of data) into
certain order (ascending or
descending order).
Sorting = ordering.
Sorted = ordered based on a particular 3 1 621 3 45 90
way.
01 1 2 3 3 4 5 6 9
965 43 3 2 1 1 0
Sorting
Input:
A sequence of n numbers:
a1, a2, ..., an
Output:
A permutation (reordering):
ak1, ak2, ..., akn
of the input sequence such that
f(ak1) < f(ak2 ) < ... < f(akn )
where f is an ordering function
Examples of Sorting
– Words in a dictionary are sorted.
– Files in a directory are often listed in sortedorder.
– In a newspaper, the calendar of events in a schedule is generally
sorted by date.
– In a record store musical compact disks are generally sorted by
recording artist.
What is a Sorting Algorithm?
An algorithm for sorting a set ofelements.
3 1 62 1 3 45 90
01 1 2 3 3 4 5 6 9
965 43 3 2 1 1 0
Types of Sorting Algorithms
There are many, many different types of sortingalgorithms,
but the primary onesare:
❖ Selection Sort
❖ Insertion Sort
❖ Bubble Sort
❖ Quick Sort
❖ Heap Sort
❖ Merge Sort
Selection Sort
One of the simplest sorting
algorithms works asfollows:
– Selection: 1. Select the
lowest element in the
remaining array.
– Swapping: 2. Bring it to the
Name “selection sort” because it
starting position.
works by r position repeatedly
“selecting“ the smallest remaining – Counter Shift: 3. Change
element and swapping it with the i- the counter for unsorted
th element in i-th iteration.
array by one.
Selection Sort
Selection Sort
Selection Sort
Selection Sort
Selection Sort
Selection Sort
Selection Sort
Selection Sort
Selection Sort
Passes = No. of Elements - 1
=6–1
=5
Example
//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
Example
//Cont.
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]);
}
}
Example
//Cont.
/* 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;
}
Output
Sorted array:
11 12 22 25 64
Insertion sort
1. We have two group of items:
–sorted group, and
–unsorted group
2. Initially, all items in the
unsorted group and the sorted
group is empty.
–We assume that items in the
This method is often unsorted group unsorted.
used for playing cards (usedby –We have to keep items in the
people to sort bridgehands).
sorted group sorted.
3. Pick any item from, then insert
the item at the right position in
the sorted group to maintain
sorted property.
4. Repeat the process until the
unsorted group becomes empty.
Insertion sort
Like sorting a hand of playing cards:
– Start with an empty left hand andthe cards facing down on the table.
– Remove one card at a time from the table, and insert it into the
correct position in the left hand
Compare it with each of the cards already in the hand, from right
to left.
– The cards held in the left handare sorted
These cards were originally the top cards of the pile on thetable.
Insertion sort
1. To insert 12, we need to
make room for it.
24
Insertion sort
2. Moving 36.
25
Insertion sort
3. Moving 24.
26
Insertion sort
12 4. Place 12 into right position.
27
Example
//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 */
Example
//Cont.
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)
{
Example
//Cont.
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;
}
Output
5 6 11 12 13
Bubble Sort
Bubble Sort is the simplest sorting algorithm that works by repeatedly
swapping the adjacent elements if they are in wrong order.
Compare each element (except the last one) with its neighbor to the right.
– If they are out oforder, swap them.
– This puts the largest element at thevery end.
– The last element is now in the correct and finalplace.
Compare each element (except the last two) with its neighbor to the right.
– If they are out oforder, swap them.
– This puts the largest element at thevery end.
– The last two elements is now in the correct and final place.
Compare each element (except the last three) with its neighbor to the right.
– Continue as above until you have no unsorted elements on the left.
50 30 10 20 40
Pass 1: Number Of Passes = Max – 1 = 5 – 1 = 4
50 30 10 20 40 0,1
30 50 10 20 40 1,2
30 10 50 20 40 2,3
30 10 20 50 40
3,4
30 10 20 40 50
Pass 2:
30 10 20 40 50 0,1
10 30 20 40 50 1,2
10 20 30 40 50
2,3
10 20 30 40 50
Pass 3:
10 20 30 40 50 0,1
10 20 30 40 50 1,2
10 20 30 40 50
Pass 4:
10 20 30 40 50 0,1
10 20 30 40 50
10 20 30 40 50 Sorted list
Example
// Bubble sort
#include <bits/stdc++.h>
using namespace std;
void swap(int *xp, int *yp)
{
int temp = *xp;
*xp = *yp;
*yp = temp;
}
// A function to implement bubble sort
void bubbleSort(int arr[], int n)
{
int i, j;
for (i = 0; i < n-1; i++)
Example
// Cont
// Last i elements are already in place
for (j = 0; j < n-i-1; j++)
if (arr[j] > arr[j+1])
swap(&arr[j], &arr[j+1]);
}
/* Function to print an array */
void printArray(int arr[], int size)
{
int i;
for (i = 0; i < size; i++)
cout << arr[i] << " ";
cout << endl;
}
Example
// Cont
// Driver code
int main()
{
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr)/sizeof(arr[0]);
bubbleSort(arr, n);
cout<<"Sorted array: \n";
printArray(arr, n);
return 0;
}
Output
Sorted array:
11 12 22 25 34 64 90
Quick Sort
• Quick sort is one of the most popular sortingtechniques.
• Asthe name suggests the quick sort is the fastest known sorting
algorithm in practice.
• It has the best average time performance.
• It works by partitioning the array tobe sorted and each partition in
turn sorted recursively. Hence also called partition exchangesort.
Quick Sort
• In partition one of the array elements is choses asapivot element
• Choosean element pivot=a[n-1]. Supposethat elements of an array
a are partitioned so that pivot is placed into position I and the
following condition hold:
• Each elements in position 0 through i-1 is less than or equal to
pivot
• Each of the elements in position i+1 through n-1 is greater than
or equal to key
• The pivot remains at the ith position when the array is
completely sorted. Continuously repeating this process will
eventually sortan array.
Quick Sort
Quick Sort
Quick Sort
Quick Sort
Quick Sort
Quick Sort
Quick Sort
Quick Sort
Quick Sort
Quick Sort
Quick Sort
Quick Sort
Quick Sort
Example
//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 */
Example
//Cont.
int partition (int arr[], int low, int high)
{
int pivot = arr[high]; // pivot
int i = (low - 1); // Index of smaller element and indicates the right
position of pivot found so far
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);
}
Example
//Cont.
/* 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);
}
}
Example
//Cont.
/* 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;
}
Output
Sorted array:
1 5 7 8 9 10
Heap Sort
Heap Sort is one of the best sorting methods being in-
place and with no quadratic worst-case scenarios. Heap
sort algorithm is divided into two basic parts
Creating a Heap of the unsorted list
Then a sorted array is created by repeatedly removing
the largest/smallest element from the heap, and
inserting it into the array
The heap is reconstructed after each removal
Heap Sort
MaxHeapConstructionAlgorithm
Step 1 Create a new node at the end of heap.
Step 2 Assign new value to the node.
Step 3 Compare the value of this child node with its
parent.
Step 4 If value of parent is less than child,then
swap them.
Step 5 Repeat step 3 & 4 until Heap property
holds.
MaxHeapDeletionAlgorithm
Step 1 − Remove root node.
Step 2 − Move the last element of last level to root
Step 3 − Compare the value of this child node with
its parent.
Step 4 − If value of parent is less than child, then
swap them.
Step 5 − Repeat step 3 & 4 until Heap property
holds.
Heap Sort
Heap Sort
Heap Sort
Heap Sort
Heap Sort
Heap Sort
Heap Sort
Heap Sort
Heap Sort
Heap Sort
Heap Sort
Heap Sort
Heap Sort
Heap Sort
Heap Sort
Heap Sort
Heap Sort
Heap Sort
Heap Sort
Heap Sort
Heap Sort
Heap Sort
Heap Sort
Heap Sort
Heap Sort
Heap Sort
Heap Sort
Example
// Heap Sort
#include <iostream>
using namespace std;
// To heapify a subtree rooted with node i which is
// an index in arr[]. n is size of heap
void heapify(int arr[], int n, int i)
{
int largest = i; // Initialize largest as root
int l = 2 * i + 1; // left = 2*i + 1
int r = 2 * i + 2; // right = 2*i + 2
// If left child is larger than root
if (l < n && arr[l] > arr[largest])
largest = l;
Example
// Cont.
// If right child is larger than largest so far
if (r < n && arr[r] > arr[largest])
largest = r;
// If largest is not root
if (largest != i) {
swap(arr[i], arr[largest]);
// Recursively heapify the affected sub-tree
heapify(arr, n, largest);
}
}
Example
// Cont.
// main function to do heap sort
void heapSort(int arr[], int n)
{
// Build heap (rearrange array)
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
// One by one extract an element from heap
for (int i = n - 1; i >= 0; i--) {
// Move current root to end
swap(arr[0], arr[i]);
// call max heapify on the reduced heap
heapify(arr, i, 0);
}
Example
// Cont.
}
/* A utility function to print array of size n */
void printArray(int arr[], int n)
{
for (int i = 0; i < n; ++i)
cout << arr[i] << " ";
cout << "\n";
}
Example
// Cont.
// Driver program
int main()
{
int arr[] = { 12, 11, 13, 5, 6, 7 };
int n = sizeof(arr) / sizeof(arr[0]);
heapSort(arr, n);
cout << "Sorted array is \n";
printArray(arr, n);
}
Output:
Sorted array is
5 6 7 11 12 13
Output
Sorted array is
5 6 7 11 12 13
Merge sort
• Divide array into two halves.
• Use divide and conquer
• Recursively sort each half.
• Merge two halves to make sorted whole.
Merge sort
Divide array into two halves.
Merge sort
Divide array into two halves.
Merge sort
Merge sort
Merge sort
Example
// Merge Sort
#include <iostream>
using namespace std;
// 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 n1 = m - l + 1;
int n2 = r - m;
// Create temp arrays
int L[n1], R[n2];
Example
// Cont.
// Copy data to temp arrays L[] and R[]
for (int i = 0; i < n1; i++)
L[i] = arr[l + i];
for (int j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];
// Merge the temp arrays back into arr[l..r]
// Initial index of first subarray
int i = 0;
// Initial index of second subarray
int j = 0;
// Initial index of merged subarray
int k = l;
Example
// Cont.
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
}
else {
arr[k] = R[j];
j++;
}
k++;
}
Example
// Cont.
// 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++;
}
}
Example
// Cont.
// 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){
return;//returns recursively
}
int m =l+ (r-l)/2;
mergeSort(arr,l,m);
mergeSort(arr,m+1,r);
merge(arr,l,m,r);
}
// UTILITY FUNCTIONS
// Function to print an array
Example
// Cont.
void printArray(int A[], int size)
{
for (int i = 0; i < size; i++)
cout << A[i] << " ";
}
// Driver code
int main()
{
int arr[] = { 12, 11, 13, 5, 6, 7 };
int arr_size = sizeof(arr) / sizeof(arr[0]);
cout << "Given array is \n";
printArray(arr, arr_size);
mergeSort(arr, 0, arr_size - 1);
Example
// Cont.
cout << "\nSorted array is \n";
printArray(arr, arr_size);
return 0;
}
// This code is contributed by Mayank Tyagi
Output
Given array is
12 11 13 5 6 7
Sorted array is
5 6 7 11 12 13
Thank you!!!
