SORTING
ALGORITHMS
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.
WORKING OF BUBBLE SORT
1. First Iteration (Compare and Swap)
•Starting from the first index, compare the first and the second
elements.
•If the first element is greater than the second element, they are
swapped.
•Now, compare the second and the third elements. Swap them if
they are not in order.
•The above process goes on until the last element.
WORKING OF BUBBLE SORT
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.
INSERTION SORT
INSERTION SORT
Insertion sort is a sorting algorithm that places an unsorted element at its
suitable place in each iteration.
Insertion sort works similarly as we sort cards in our hand in a card game.
We assume that the first card is already sorted then, we select an unsorted
card. If the unsorted card is greater than the card in hand, it is placed on the
right otherwise, to the left. In the same way, other unsorted cards are taken
and put in their right place.
A similar approach is used by insertion sort.
WORKING OF INSERTION
SORT
The first element in the array is assumed to be sorted. Take the
second element and store it separately in key.
Compare key with the first element. If the first element is greater
than key, then key is placed in front of the first element.
WORKING OF INSERTION
SORT
Now, the first two elements are sorted.
Take the third element and compare it with the elements on the left
of it. Placed it just behind the element smaller than it. If there is no
element smaller than it, then place it at the beginning of the array.
Similarly, place every unsorted element at its correct position.
SELECTION SORT
SELECTION SORT
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.
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.
QUICK SORT
QUICKSORT
Quicksort is a sorting algorithm 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.
WORKING OF QUICKSORT
ALGORITHM
1. Select the Pivot Element
There are different variations of quicksort where the pivot element
is selected from different positions. Here, we will be selecting the
rightmost element of the array as the pivot element.
2. Rearrange the Array
Now the elements of the array are rearranged so that elements
that are smaller than the pivot are put on the left and the elements
greater than the pivot are put on the right.
MERGE SORT
MERGE SORT
Merge Sort is one of the most popular sorting algorithms that is
based on the principle of Divide and Conquer Algorithm.
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 ALGORITHM
- The MergeSort function repeatedly divides the array into two
halves until we reach a stage where we try to perform MergeSort
on a subarray of size 1.
- After that, the merge function comes into play and combines the
sorted arrays into larger arrays until the whole array is merged.
HEAP SORT
HEAP SORT
Heap Sort is a popular and efficient sorting algorithm in computer
programming. Learning how to write the heap sort algorithm
requires knowledge of two types of data structures - arrays and
trees.
Heap sort works by visualizing the elements of the array as a
special kind of complete binary tree called a heap.
HEAP DATA STRUCTURE
What is Heap Data Structure?
Heap is a special tree-based data structure. A binary tree is said to follow a heap data
structure if it is a complete binary tree
All nodes in the tree follow the property that they are greater than their children i.e. the
largest element is at the root and both its children and smaller than the root and so on.
Such a heap is called a max-heap. If instead, all nodes are smaller than their children,
it is called a min-heap
Note: A complete binary tree is a binary tree in which every level, except possibly
the last, is completely filled, and all nodes in the last level are as far left as possible.
OPERATIONS OF HEAP DATA
STRUCTURE
Heapify: a process of creating a heap from an array.
Insertion: process to insert an element in existing heap time
complexity O(log N).
Deletion: deleting the top element of the heap or the highest priority
element, and then organizing the heap and returning the element with
time complexity O(log N).
Peek: to check or find the first (or can say the top) element of the heap.
RELATIONSHIP BETWEEN ARRAY
INDEXES AND TREE ELEMENTS
A complete binary tree has an interesting property that we can use
to find the children and parents of any node.
If the index of any element in the array is i, the element in the
index 2i+1 will become the left child and element in 2i+2 index will
become the right child. Also, the parent of any element at index i is
given by the lower bound of (i-1)/2.
Position of left child of i=2*i +1
Position of right child of i=2*i+2
Position of parent of i = (i-1)/2
HOW TO "HEAPIFY" A TREE
Starting from a complete binary tree, we can modify it to become a
Max-Heap by running a function called heapify on all the non-leaf
elements of the heap.
WORKING OF HEAP SORT
First convert the array into heap data structure using heapify, then one by one delete the root node of the
Max-heap and replace it with the last node in the heap and then heapify the root of the heap. Repeat this
process until size of heap is greater than 1.
• Build a heap from the given input array.
• Repeat the following steps until the heap contains only one element:
• Swap the root element of the heap (which is the largest element) with the last element of the heap.
• Remove the last element of the heap (which is now in the correct position).
• Heapify the remaining elements of the heap.
• The sorted array is obtained by reversing the order of the elements in the input array.
COMPARE SORTING
ALGORITHM
