Practical 1. Write a program to implement Bubble sort.
Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent
elements if they are in the wrong order. This algorithm is not suitable for large data sets as its average
and worst-case time complexity are quite high.
Complexity Analysis of Bubble Sort:
Time Complexity: O(n2)
Auxiliary Space: O(1)
We assume list is an array of n elements. We further assume that swap function swaps the values of
the given array elements.
Step 1 − Check if the first element in the input array is greater than the next element in the array.
Step 2 − If it is greater, swap the two elements; otherwise move the pointer forward in the array.
Step 3 − Repeat Step 2 until we reach the end of the array.
Step 4 − Check if the elements are sorted; if not, repeat the same process (Step 1 to Step 3) from the
last element of the array to the first.
Step 5 − The final output achieved is the sorted array.
Algorithm: Sequential-Bubble-Sort (A)
fori ← 1 to length [A] do
for j ← length [A] down-to i +1 do
if A[A] < A[j-1] then
Exchange A[j] ⟷ A[j-1]
will come out of the loop.
Pseudocode of bubble sort algorithm can be written as follows −
voidbubbleSort(int numbers[], intarray_size){
inti, j, temp;
for (i = (array_size - 1); i>= 0; i--)
for (j = 1; j <= i; j++)
if (numbers[j-1] > numbers[j]){
temp = numbers[j-1];
numbers[j-1] = numbers[j];
numbers[j] = temp;
Analysis
Here, the number of comparisons are
1 + 2 + 3 + ... + (n - 1) = n(n - 1)/2 = O(n2)
Clearly, the graph shows the n2 nature of the bubble sort.
2. Write a program to implement Quick sort
QuickSort is one of the best sorting algorithms that follows the divide-and-conquer approach like
Merge Sort but unlike Merge Sort, this algorithm does in place sorting.
Quick sort
Quick Sort is a divide and conquer algorithm. This selects a pivot element and divides the array into
two subarrays.
• Step 1: Pick an element from an array, and call it a pivot element.
• Step 2: Divide an unsorted array element into two arrays.
• Step 3: If the value less than the pivot element comes under the first sub-array, the remaining
elements with a value greater than the pivot come in the second sub-array.
Consider an example given below, wherein
• P is the pivot element.
• L is the left pointer.
• R is the right pointer.
Quick Sort Algorithm
quickSort(array, leftmostIndex, rightmostIndex)
if (leftmostIndex < rightmostIndex)
pivotIndex <- partition(array,leftmostIndex, rightmostIndex)
quickSort(array, leftmostIndex, pivotIndex - 1)
quickSort(array, pivotIndex, rightmostIndex)
partition(array, leftmostIndex, rightmostIndex)
set rightmostIndex as pivotIndex
storeIndex <- leftmostIndex - 1
for i <- leftmostIndex + 1 to rightmostIndex
if element[i] < pivotElement
swap element[i] and element[storeIndex]
storeIndex++
swap pivotElement and element[storeIndex+1]
return storeIndex + 1
3. Write a program to implement Selection sort
The selection sort is a simple comparison-based sorting algorithm that sorts a collection by
repeatedly finding the minimum (or maximum) element and placing it in its correct position in the list.
It is very simple to implement and is preferred when you have to manually implement the sorting
algorithm for a small amount of dataset.
Selection Sort Algorithm
selectionSort(array, size)
for i from 0 to size - 1 do
set i as the index of the current minimum
for j from i + 1 to size - 1 do
if array[j] < array[current minimum]
set j as the new current minimum index
if current minimum is not i
swap array[i] with array[current minimum]
end selectionSort
4. Write a program to implement Insertion sort
Insertion sort is a simple sorting algorithm used to sort a collection of elements in a given order. It is
less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort
but it is simple to implement and is suitable to sort small data lists.
Complexity Analysis of Insertion Sort :
Time Complexity of Insertion Sort
• Best case: O(n), If the list is already sorted, where n is the number of elements in the list.
• Average case: O(n2), If the list is randomly ordered
• Worst case: O(n2), If the list is in reverse order
Insertion Sort Algorithm
Step to implement the insertion sort algorithm −
• If it is the first element, it is already sorted. return 1;
• Pick next element
• Compare with all elements in the sorted sub-list
• Shift all the elements in the sorted sub-list that is greater than the value to be sorted
• Insert for loop the value
• Repeat until the list is sorted
5 Write a program to implement Linear search
Linear search algorithm is the simplest searching algorithm that is used to find an element in the given
collection. It simply compares the element to find with each element in the collection one by one till the
matching element is found or there are no elements left to compare
Time Complexity: O(n), where n is the number of elements
Auxiliary Space: Implementation defined, discussed below
LinearSearch(array, key)
for each item in the array
if item == value
return its index
6. Write a program to implement Binary search.
Binary Search Algorithm
Binary Search Algorithm is a searching algorithm used in a sorted array by repeatedly dividing the search
interval in half. The idea of binary search is to use the information that the array is sorted and reduce
the time complexity to O(log N).
Iteration Method
do until the pointers low and high meet each other.
mid = (low + high)/2
if (x == arr[mid])
return mid
else if (x > arr[mid]) // x is on the right side
low = mid + 1
else // x is on the left side
high = mid - 1
Recursive Method
binarySearch(arr, x, low, high)
if low > high
return False
else
mid = (low + high) / 2
if x == arr[mid]
return mid
else if x > arr[mid] // x is on the right side
return binarySearch(arr, x, mid + 1, high)
else // x is on the left side
return binarySearch(arr, x, low, mid - 1)
7. Write a program to implement Stack operations: push, pop, display.
Stack is the linear data structure that follows the Last in, First Out(LIFO) principle of data insertion and
deletion. It means that the element that is inserted last will be the first one to be removed and the
element that is inserted first will be removed at last. Think of it as the stack of plates stacked on top of
one another where we can only add or remove the top plate.
Basic Stack Operations in C++
Following are some basic operations in the stack that make it easy to manipulate the stack data structure:
Operation Description Time Space
Complexity Complexity
Push Inserts an element at the top of the stack. O(1) O(1)
Pop Removes the top most element of the stack. O(1) O(1)
Peek Returns the topmost element of the stack. O(1) O(1)
IsFull Returns true is the stack is full otherwise returns O(1) O(1)
false.
IsEmpty Returns true is the stack is empty otherwise O(1) O(1)
returns false.
8. Write a program to implement Linear Queue operations: Insert, Delete, Display.
A queue is a linear data structure that follows the First-In-First-Out (FIFO) principle which means the
elements added first in a queue will be removed first from the queue
Basic Operations of Queue
Following are the basic operations of the Queue data structure which are required to manipulate the
elements present inside the Queue.
Operation Description Time Space
Complexity Complexity
Enqueue Inserts an element at the end of the queue using O(1) O(1)
the rear pointer.
Dequeue Deletes an element from the front of the queue O(1) O(1)
using the front pointer.
IsEmpty Checks if the queue is empty or not. If front ==-1 O(1) O(1)
returns true.
IsFull Checks if the queue is full or not . If O(1) O(1)
rear==MAX_SIZE-1 returns true.
