Sorting Algorithms
in C
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Agenda
● Bubble Sort
● Selection Sort
● Insertion Sort
● Quick Sort
● Merge Sort
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Sorting Algorithms
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Bubble Sort Algorithm
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
What is Bubble Sort?
● Bubble sort is one of the easiest and brute force sorting algorithm.
● It is used to sort elements in either ascending or descending order.
● Every element is compared with every other element in bubble sort.
● It basically does swapping of elements if they are not in the right order
depending on their value and the intended order.
● Nested loop will be used to implement this algorithm.
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Bubble Sort - Algorithm
bubbleSort(arr, size)
for i=0 to n
for j=0 to n-i-1
if arr[j]>arr[j+1]
Swap arr[j] and arr[j+1]
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Bubble Sort - Demonstration
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Bubble Sort - Demonstration Cont.
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Bubble Sort – Implementation
void bubbleSort(int arr[]) {
int size = arr.length;
for (int i = 0; i < size; i++)
for (int j = 0; j < size - i - 1; j++)
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Bubble Sort - Time Complexity
● Best Time Complexity: O(n)
● Average Time Complexity: O(n^2)
● Worst Time Complexity: O(n^2)
● Each and every element is compared with the other elements for array
which takes n time and the above steps continues for n iterations.
● In the best case that is sorted array, we can do some modification
by using flag to check whether the lament is already sorted or
not.
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Bubble Sort - Space Complexity
• No auxiliary space is required in bubble sort implementation.
• Hence space complexity is: O(1)
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Bubble Sort - Analysis
• Number of Comparisons
• Number of Swaps
• Stable or Unstable
• Inplace or Outplace
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Selection Sort Algorithm
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
What is Selection Sort?
● It is a simple sort algorithm that revolves around the ‘comparison’.
● In each iteration, one element gets placed.
● We choose the minimum element in the array and place is at the
beginning of the array by swapping with the front element.
● We can also do this by choosing maximum element
and placing it at the rear end.
● Selection sort basically selects an element in every iteration
and place it at the appropriate position.
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Selection Sort - Algorithm
selectionSort(arr, n)
iterate (n - 1) times
set the first unsorted element index as the min
for each of the unsorted elements
if element < currentMin
set element's index as new min
swap element at min with first unsorted position
end selectionSort
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Selection Sort - Demonstration
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Selection Sort - Demonstration Cont.
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Selection Sort - Implementation
void selectionSort(int arr[]) {
int size = arr.length;
for (int j = 0; j < size - 1; j++) {
int min = j;
for (int i = j + 1; i < size; i++) {
if(arr[i]<arr[min])
min = i;
}
int tmp = arr[j];
arr[j] = arr[min];
arr[min] = tmp;
}
} Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Selection Sort - Time Complexity
● Best Time Complexity: O(n^2)
● Average Time Complexity: O(n^2)
● Worst Time Complexity: O(n^2)
● In the worst case, in every iteration, we have to traverse the entire array
for finding min elements and this will continue for all n elements. Hence
this will perform n^2 operations in total.
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Selection Sort - Space Complexity
• No auxiliary space is required in Selection Sort implementation that is
we are not using any arrays, linked list, stack, queue, etc to store our
elements.
• Hence space complexity is: O(1)
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Selection Sort - Analysis
• Number of Comparisons
• Number of Swaps
• Stable or unstable
• Inplace or outplace
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Insertion Sort Algorithm
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
What is Insertion Sort?
● It is one of the easiest and brute force sorting algorithms
● Insertion sort is used to sort elements in either ascending or descending order
● In insertion sort, we maintain a sorted part and unsorted part
● It works just like playing cards i.e picking one card and sorting it with the cards that we
have in our hand already which in turn are sorted
● With every iteration, one item from unsorted is moved to the sorted part
● First element is picked and considered as sorted
● Then we start picking from 2nd elements onwards and start comparison
with elements in sorted part.
● We shift the elements from sorted by one element until an appropriate
location is not found for the picked element
● This continues till all the elements get exhausted
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Insertion Sort - Algorithm
insertionSort(arr, size)
consider 1st element as sorted part
for each element from i=2 to n-1
tmp = arr[i]
for j=i-1 to 0
If a[j]>tmp
Then right shift it by one position
put tmp at current j
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Insertion Sort - Demonstration
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Insertion Sort - Demonstration Cont.
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Insertion Sort - Implementation
void insertionSort(int arr[]) {
int size = arr.length;
for (int i = 1; i < size; i++) {
int tmp = arr[i];
int j = i - 1;
while (j >= 0 && tmp < arr[j]) {
arr[j + 1] = arr[j];
--j;
}
arr[j + 1] = tmp;
}
} Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Insertion Sort - Time Complexity
● In the worst case, it will take n to pick all elements and then at max n
shifts to set it to the right position
● In best case that is sorted array we will just pick the elements but no
shifting will take place leading it to n time complexity that is every
element is traversed at least once
● Best Time Complexity: O(n)
● Average Time Complexity: O(n^2)
● Worst Time Complexity: O(n^2)
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Insertion Sort - Space Complexity
• No auxiliary space is required in Insertion sort implementation that is
we are not using any arrays, linked list, stack, queue, etc to store our
elements
• Hence space complexity is: O(1)
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Insertion Sort - Analysis
• Number of Comparisons
• Number of Swaps
• Stable or Unstable
• Inplace or Outplace
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Quick Sort Algorithm
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
What is Quick Sort?
● It is one of the most widely used sorting algorithm
● It follows divide and conquer paradigm
● Recursion is used in quicksort implementation
● In each recursive call, a pivot is chosen then the array is partitioned in such a way
that all the elements less than pivot lie to the left and all the elements greater
than pivot lie to the right
● After every call, the chosen pivot occupies its correct position in
the array which it is supposed to as in sorted array
● So with each step, our problem gets reduced by 2 which leads to
quick sorting
● Pivot can be an element. Example: last element of current array,
first element of current array, random pivot, etc.
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Quick Sort - Algorithm
quickSort(arr, beg, end)
if (beg < end)
pivotIndex = partition(arr,beg, end)
quickSort(arr, beg, pivotIndex -1)
quickSort(arr, pivotIndex + 1, end)
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Partition - Algorithm
partition(arr, beg, end)
set end as pivotIndex
pIndex = beg - 1
for i = beg to end-1
if arr[i] < pivot
swap arr[i] and arr[pIndex]
pIndex++
swap pivot and arr[pIndex+1]
return pIndex + 1
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Quick Sort - Demonstration
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Quick Sort - Implementation
void quickSort(int[] a,int p,int r)
{
if(p<r)
{
int q=partition(a,p,r);
quickSort(a,p,q-1);
quickSort(a,q+1,r);
}
}
Quick Sort – Implementation Cont.
int partition_function(int arr[], int l, int h){
int pivot = arr[h]; // pivot is the last element
int pIndex = (l - 1); // Index of smaller element
for (int j = l; j <= h- 1; j++){
if (arr[j] < p){
i++;
swap_elements(&arr[i], &arr[j]);
}
}
swap_elements(&arr[i + 1], &arr[h]);
return (i + 1);
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
}
Quick Sort - Time Complexity
● Partition of elements take n time and in quicksort problem is divide by
the factor 2
● Best Time Complexity: O(nlogn)
● Average Time Complexity: O(nlogn)
● Worst Time Complexity: O(n^2)
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Quick Sort - Space Complexity
• O(n): basic approach
• O(logn): modified approach
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Quick Sort - Analysis
• Number of Comparisons
• Number of Swaps
• Stable or unstable
• Inplace or outplace
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Merge Sort Algorithm
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
What is Merge Sort?
• In merge sort, the problem is divided into two sub problems in every
iteration
• Hence efficiency is increased drastically
• It follows divide and conquer approach
• Divide break the problem into 2 sub problem which continues until
problem set is left with one element only
• Conquer basically merges the 2 sorted array into the
original array
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Merge Sort - Algorithm
mergeSort(arr, left, right)
if left > right
return
mid = (left+right)/2
mergeSort(arr, left, mid)
mergeSort(arr, mid+1, right)
merge(arr, left, mid, right)
end
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Merge Sort - Demonstration
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Merge - Algorithm
• Create 2 subarrays Left and Right
• Create 3 iterators i, j and k
• Insert elements in Left and Right ( i & j)
• k - Replace the values in the original array
• Pick the larger elements from Left and Right & place them in the correct
position
• If there are no elements in either Left or Right, pick up
the remaining elements either from Left or Right and
insert in original array
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Merge - Demonstration
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Merge Sort - Implementation
void mergeSort(int arr[], int start, int right) {
if (start < right) {
int mid = (start + right) / 2;
mergeSort(arr, start, mid);
mergeSort(arr, mid + 1, right);
merge(arr, start, mid, right);
}
}
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Merge Sort – Implementation Cont.
void merge(int arr[], int start, int mid, int end) {
int len1 = mid - start + 1;
int len2 = end - mid;
int leftArr[len1], rightArr[len2];
for (int i = 0; i < len1; i++)
leftArr[i] = arr[start + i];
for (int j = 0; j < len2; j++)
rightArr[j] = arr[mid + 1 + j];
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Merge Sort – Implementation Cont.
int i, j, k;
i = 0;
j = 0;
k = start;
while (i < len1 && j < len2) {
if (leftArr[i] <= rightArr[j]) {
arr[k] = leftArr[i];
i++;
} else {
arr[k] = rightArr[j];
j++;
}
k++;
}
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Merge Sort – Implementation Cont.
while (i < len1) {
arr[k] = leftArr[i];
i++;
k++;
}
while (j < len2) {
arr[k] = rightArr[j];
j++;
k++;
}
} Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Merge Sort - Time Complexity
• In the worst case, in every iteration, we are dividing the problem into
further 2 subproblems. Hence this will perform logn operations and this
has to be done for n iteration resulting in nlogn operations total.
• In the best case that is sorted array, we can do some modification by using
flag to check whether the lament is already sorted or not
• Best Time Complexity: O(nlogn)
• Average Time Complexity: O(nlogn)
• Worst Time Complexity: O(nlogn)
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Merge Sort - Space Complexity
• n auxiliary space is required in Merge Sort implementation as all the
elements are copied into auxiliary array
• Hence space complexity is: O(n)
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Merge Sort - Analysis
• Number of Comparisons
• Stable or unstable
• Inplace or outplace
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Summary
● Sorting Algorithms
○ Bubble Sort, Selection Sort, etc.
○ Implementation
○ Analysis
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Thank You!
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited