Design & Analysis Of
Algorithms
Presentation: 03
Sorting Techniques
Presented By: Pulkit Narwal
Sorting
• A Sorting Algorithm is used to rearrange a given array or list elements
according to a comparison operator on the elements. The comparison
operator is used to decide the new order of element in the respective
data structure
Merge Sort
• Merge sort is a sorting technique based on divide and conquer
technique.
• Here, a problem is divided into multiple sub-problems. Each sub-
problem is solved individually. Finally, sub-problems are combined to
form the final solution.
• Merge sort first divides the array into equal halves and then combines
them in a sorted manner.
• Best Case Complexity: O(n*log n)
• Worst Case Complexity: O(n*log n)
• Average Case Complexity: O(n*log n)
Merge Sort
Step 1 − if it is only one element in the list
it is already sorted, return.
Step 2 − divide the list recursively into
two halves until it can no more be
divided.
Step 3 − merge the smaller lists into new
list in sorted order.
Merge Sort
MergeSort(A, p, r):
if p > r
return
q = (p+r)/2
mergeSort(A, p, q)
mergeSort(A, q+1, r)
merge(A, p, q, r)
Bubble Sort
• The bubble sort algorithm compares two adjacent elements and
swaps them if they are not in the intended order. For example,
• Suppose we have an unsorted array with elements: 45, 1, 4.
• Here, the bubble sort algorithm compares the first element 45 and
second element 1. Since 45 is greater than 1, they are swapped (1, 45,
4).
• Similarly, the new second element is compared with the next
element. This process continues until all the elements are sorted.
Bubble Sort
Bubble Sort
•Worst Case Complexity: O(n2)
If we want to sort in ascending order and the array is in descending
order then, the worst case occurs.
•Best Case Complexity: O(n)
If the array is already sorted, then there is no need for sorting.
•Average Case Complexity: O(n2)
It occurs when the elements of the array are in jumbled order (neither
ascending nor descending).
Selection Sort
• Selection sort is an algorithm that selects the smallest element from
an unsorted list in each iteration and places that element at the
beginning of the unsorted list.
• Worst Case Complexity: O(n2)
If we want to sort in ascending order and the array is in descending
order then, the worst case occurs.
• Best Case Complexity: O(n2)
It occurs when the array is already sorted
• Average Case Complexity: O(n2)
It occurs when the elements of the array are in jumbled order (neither
ascending nor descending).
Selection Sort
Insertion Sort
• Insertion sort is a sorting algorithm that places an unsorted element
at its suitable place in each iteration.
• Worst Case Complexity: O(n2)
Suppose, an array is in ascending order, and you want to sort it in
descending order. In this case, worst case complexity occurs.
• Best Case Complexity: O(n)
When the array is already sorted, the outer loop runs for n number of
times whereas the inner loop does not run at all. So, there are
only n number of comparisons. Thus, complexity is linear.
• Average Case Complexity: O(n2)
It occurs when the elements of an array are in jumbled order (neither
ascending nor descending).
Insertion Sort
Similarly
Quicksort
• Quicksort algorithm is based on the divide and conquer
approach where
• An array is divided into subarrays by selecting a pivot
element (element selected from the array).
While dividing the array, the pivot element should be positioned in
such a way that elements less than pivot are kept on the left side and
elements greater than pivot are on the right side of the pivot.
• The left and right subarrays are also divided using the same approach.
This process continues until each subarray contains a single element.
• At this point, elements are already sorted. Finally, elements are
combined to form a sorted array.
Quicksort
•Worst Case Complexity [Big-O]: O(n2)
It occurs when the pivot element picked is either the greatest or the
smallest element.
However, the quicksort algorithm has better performance for scattered
pivots.
•Best Case Complexity [Big-omega]: O(n*log n)
It occurs when the pivot element is always the middle element or near
to the middle element.
•Average Case Complexity [Big-theta]: O(n*log n)
It occurs when the above conditions do not occur.
Quicksort
Step 1 − Choose the highest index value has pivot
Step 2 − Take two variables to point left and right of the list excluding
pivot
Step 3 − left points to the low index
Step 4 − right points to the high
Step 5 − while value at left is less than pivot move right
Step 6 − while value at right is greater than pivot move left
Step 7 − if both step 5 and step 6 does not match swap left and right
Step 8 − if left ≥ right, the point where they met is new pivot
Assignment: 01
• Write and algorithm to calculate factorial of a given number (A
factorial is a function that multiplies a number by every number
below it. For example 5!= 5*4*3*2*1=120).
• Write an algorithm to calculate Fibonacci series(The Fibonacci
numbers are the numbers in the following integer sequence.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ……..).