Sorting Algorithms

-
Sorting Algorithm

• A sorting algorithm is used to arrange

elements of an array/list in a specific
order. For example,
• There are various sorting algorithms
that can be used to complete this
operation. And, we can use any
algorithm based on the requirement.

2
Sorting Algorithm
• Different Sorting Algorithms.
▪ Bubble Sort
▪ Selection Sort
▪ Insertion Sort
▪ Merge Sort
▪ Quicksort
▪ Counting Sort
▪ Radix Sort
▪ Bucket Sort
▪ Heap Sort
▪ Shell Sort
3
Bubble Sort

• Bubble sort is a sorting algorithm that

compares two adjacent elements and swaps
them until they are in the intended order.
• Just like the movement of air bubbles in the
water that rise up to the surface, each element
of the array move to the end in each iteration.
Therefore, it is called a bubble sort.

4
Working of Bubble Sort
• Suppose we are trying to sort the elements
in ascending order.
• 1. First Iteration (Compare and Swap)
1. Starting from the first index, compare
the first and the second elements.
2. If the first element is greater than the
second element, they are swapped.
3. Now, compare the second and the
third elements. Swap them if they are
not in order.
4. The above process goes on until the
last element.
5
Working of Bubble Sort

• Suppose we are trying to sort the

elements in ascending order.
• 2. Remaining Iteration
• The same process goes on for the
remaining iterations.
• After each iteration, the largest
element among the unsorted elements
is placed at the end.

6
Working of Bubble Sort

• In each iteration, the comparison takes

place up to the last unsorted element.

7
Working of Bubble Sort

• The array is sorted when all the

unsorted elements are placed at their
correct positions.

8
Working of Bubble Sort

9
Optimized Bubble Sort

10
Bubble Sort Complexity

• nearly equals to 𝑛2
• Hence, Complexity: O(𝑛2 )

11
Selection Sort Algorithm
• Selection sort is a sorting algorithm that selects the smallest element
from an unsorted list in each iteration and places that element at the
beginning of the unsorted list.
• Working of Selection Sort
1. Set the first element as minimum.
2. Compare minimum with the second
element. If the second element is smaller
than minimum, assign the second
element as minimum.

12
Selection Sort Algorithm
• Selection sort is a sorting algorithm that selects the smallest element
from an unsorted list in each iteration and places that element at the
beginning of the unsorted list.
• Working of Selection Sort
1. Set the first element as minimum.
2. Compare minimum with the second
element. If the second element is smaller
than minimum, assign the second
element as minimum.
Compare minimum with the third element.
Again, if the third element is smaller, then
assign minimum to the third element
otherwise do nothing. The process goes on
until the last element. 13
Selection Sort Algorithm
• Selection sort is a sorting algorithm that selects the smallest element
from an unsorted list in each iteration and places that element at the
beginning of the unsorted list.
• Working of Selection Sort
3. After each iteration, minimum is placed
in the front of the unsorted list.
4. For each iteration, indexing starts from
the first unsorted element. Step 1 to 3
are repeated until all the elements are
placed at their correct positions.
14
Selection Sort Algorithm

• Working of Selection Sort

4. For each iteration, indexing starts from
the first unsorted element. Step 1 to 3
are repeated until all the elements are
placed at their correct positions.

15
Selection Sort Algorithm

• Working of Selection Sort

4. For each iteration, indexing starts from
the first unsorted element. Step 1 to 3
are repeated until all the elements are
placed at their correct positions.

16
Selection Sort Algorithm

• Working of Selection Sort

4. For each iteration, indexing starts from
the first unsorted element. Step 1 to 3
are repeated until all the elements are
placed at their correct positions.

17
Selection Sort Algorithm
• Working of Selection Sort
4. For each iteration, indexing starts from
the first unsorted element. Step 1 to 3
are repeated until all the elements are
placed at their correct positions.

18
Insertion Sort Algorithm
• Insertion sort is a sorting algorithm that places an unsorted element at
its suitable place in each iteration.
• Working of Insertion Sort
• Suppose we need to sort the following array.

1. The first element in the array is assumed

to be sorted. Take the second element and
store it separately in key.
2. Compare key with the first element. If the
first element is greater than key, then key
is placed in front of the first element.
19
Insertion Sort Algorithm

• Working of Insertion Sort

2. Now, the first two elements are sorted.

20
Insertion Sort Algorithm

• Working of Insertion Sort

2. Similarly, place every unsorted element at
its correct position.

21
References:
• https://www.programiz.com/dsa/bubble-sort
• https://www.programiz.com/dsa/selection-sort
• https://www.programiz.com/dsa/insertion-sort

23