GL BAJAJ Institute of Technology and Management
[Approved by AICTE, Govt. of India & Affiliated to Dr. APJ
Abdul Kalam Technical University, Lucknow, U.P. India]
Department of Computer Science and Engineering
Design and Analysis of Algorithm Lab (BCS-553)
Lab File
Session: 2024-25
Submitted To: Submitted By:
Ms. Paramjeet Kaur Name: Yash
Assistant Professor Roll No.: 2201920100335
CSE Department Branch: CSE Sec: F
Semester: V
INDEX
Date of
S. No. List of Programs Date Signature
Submission
Program No -1
Aim: - Write a program to implement the insertion sort using array.
Insertion Sort:-
Insertion sort is a simple sorting algorithm that works similar to the way you sort
playing cards in your hands. The array is virtually split into a sorted and an unsorted
part. Values from the unsorted part are picked and placed at the correct position in the
sorted part.
Insertion Sort is a simple sorting algorithm that builds the final sorted array one item
at a time. It works by considering one element at a time and comparing it with the
elements to its left, shifting elements to the right as necessary to make room for the
current element.
Complexity:-
Worst case complexity: O(n2)
Best-case complexity: O(n)
Average-case complexity: O(n2)
Algorithm:-
for j = 2 to [Link]
key = A[j]
// Insert A[j] into the sorted sequence A[1.. j - 1]
i=j-1
while i > 0 and A[i] > key
A[i + 1] = A[i]
i = i -1
A[i + 1] = key
Process:
We will store the random set of numbers in an array.
We will traverse this array and insert each element of this array, to its correct position
where it should actually be, by shifting the other elements on the left if required.
The first element in the array is considered as sorted, even if it is an unsorted array.
The array is sub-divided into two parts, the first part holds the first element of the
array which is considered to be sorted and second part contains all the remaining
elements of array.
With each iteration one element from the second part is picked and inserted into the
first part of array at its correct position by shifting the existing elements if required.
This goes until the last element in second part of array is placed in correct position in
the output array.
Now, we have the array in sorted order.
Source Code:-
#include<stdio.h>
int main()
{
int n, temp, a[25];
printf("Enter no. of elements of array\n");
scanf("%d",&n);
printf("Enter %d elements: \n",n);
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
}
for(int i = 1; i <= n - 1; i++)
{
for(int j = i; j > 0 && a[j - 1] > a[j]; j--)
{
int temp = a[j];
a[j] = a[j - 1];
a[j - 1] = temp;
}
}
printf("Sorted Elements: ");
for(int i=0;i<n;i++){
printf("%d ",a[i]);
}
return 0;
}
Output:-
Enter no. of elements of array
5
Enter 5 elements:
25 65 10 1 9
Sorted Elements: 1 9 10 25 65
Program No -2
Aim: - Write a program to implement the Selection sort using array.
Selection Sort: -
Selection sort is a simple sorting algorithm. This sorting algorithm, like insertion sort,
is an in-place comparison-based algorithm in which the list is divided into two parts,
the sorted part at the left end and the unsorted part at the right end. Initially, the sorted
part is empty and the unsorted part is the entire list.
The smallest element is selected from the unsorted array and swapped with the
leftmost element, and that element becomes a part of the sorted array. This process
continues moving unsorted array boundaries by one element to the right.
Complexity:-
Worst case complexity: O(n2)
Best-case complexity: O(n2)
Average-case complexity: O(n2)
Algorithm:-
For i← 1 to n-1 do
min j ←i;
min x ← A[i]
for j ←i + 1 to n do
if A[j] < min x then
min j ← j
min x ← A[j]
A[min j] ← A [i]
A[i] ← min x
Process:
Set the first element as minimum.
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...
After each iteration, minimum is placed in the front of the unsorted list.
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.
Source Code:-
#include<stdio.h>
int main()
{
int n,i,j, temp, a[25],min_idx;
printf("Enter no. of elements of array\n");
scanf("%d",&n);
printf("Enter %d elements: \n",n);
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
}
for (i = 0; i < n-1; i++) {
min_idx = i;
for (j = i+1; j < n; j++) {
if (a[j] < a[min_idx]) {
min_idx = j;
}
}
temp = a[min_idx];
a[min_idx] = a[i];
a[i] = temp;
}
printf("Sorted Elements: ");
for(int i=0;i<n;i++){
printf("%d ",a[i]);
}
return 0;
}
Output:-
Enter no. of elements of array
5
Enter 5 elements:
35 15 10 8 45
Sorted Elements: 8 10 15 35 45
Program No -3
Aim: - Write a program to implement the Linear Search.
Linear Search: -
The linear search algorithm is defined as a sequential search algorithm that starts at
one end and goes through each element of a list until the desired element is found;
otherwise, the search continues till the end of the dataset.
It is a method for searching for an element in a collection of elements. In linear
search, each element of the collection is visited one by one in a sequential fashion to
find the desired element. Linear search is also known as sequential search.
Complexity:-
Worst case complexity: O(n)
Best-case complexity: O(1)
Average-case complexity: O(n)
Algorithm:-
Start: Begin at the first element of the collection of elements.
Compare: Compare the current element with the desired element.
Found: If the current element is equal to the desired element, return true or index to
the current element.
Move: Otherwise, move to the next element in the collection.
Repeat: Repeat steps 2-4 until we have reached the end of collection.
Not found: If the end of the collection is reached without finding the desired element,
return that the desired element is not in the array.
Process:
First, we have to traverse the array elements using a for loop.
In each iteration of for loop, compare the search element with the current array
element.
If the element matches, then return the index of the corresponding array element.
If the element does not match, then move to the next element.
If there is no match or the search element is not present in the given array, return -1.
Source Code:-
#include <stdio.h>
int main() {
int array[100], search, c, n;
printf("Enter number of elements in array\n");
scanf("%d", &n);
printf("Enter %d integers\n", n);
for (c = 0; c < n; c++)
scanf("%d", &array[c]);
printf("Enter a number to search\n");
scanf("%d", &search);
for (c = 0; c < n; c++) {
if (array[c] == search) {
printf("%d is present at location %d.\n", search, c + 1);
break;
}
}
if (c == n)
printf("%d isn't present in the array.\n", search);
return 0;
}
Output:-
Enter number of elements in array
5
Enter 5 integers
10 20 30 40 50
Enter a number to search
30
30 is present at location 3
Program No -4
Aim: - Write a program to implement the Binary Search.
Binary Search: -
Binary Search Algorithm is a searching algorithm used in a sorted array by repeatedly
dividing the search interval in half.
It is a search algorithm used to find the position of a target value within a sorted array.
It works by repeatedly dividing the search interval in half until the target value is
found or the interval is empty. The search interval is halved by comparing the target
element with the middle value of the search space.
Complexity:-
Worst case complexity: O(logn)
Best-case complexity: O(1)
Average-case complexity: O(logn)
Algorithm:-
Divide the search space into two halves by finding the middle index mid.
Compare the middle element of the search space with the key.
If the key is found at middle element, the process is terminated.
If the key is not found at middle element, choose which half will be used as the next
search space.
If the key is smaller than the middle element, then the left side is used for next search.
If the key is larger than the middle element, then the right side is used for next search.
This process is continued until the key is found or the total search space is exhausted.
Process:
Start with two pointers, low at the beginning and high at the end of the array.
Calculate the middle index: mid = (low + high) / 2.
Compare the target value with the middle element of the array.
If the target value equals the middle element, the search is successful, and the index is
returned.
If the target value is less than the middle element, adjust the high pointer to mid - 1 to
search the left half.
If the target value is greater than the middle element, adjust the low pointer to mid +
1 to search the right half.
Continue the process until the low pointer exceeds the high pointer or the target value
is found.
Source Code:-
#include <stdio.h>
int main() {
int n, i, x, beg, end, mid, flag = 0;
int a[100];
printf("Enter size of array: ");
scanf("%d", &n);
printf("Please enter array elements in ascending order:\n");
for (i = 0; i < n; i++) {
printf("Enter element: ");
scanf("%d", &a[i]);
}
printf("Enter element to be searched: ");
scanf("%d", &x);
beg = 0;
end = n - 1;
while (beg <= end) {
mid = (beg + end) / 2;
if (a[mid] == x) {
printf("Element found at position %d\n", mid + 1);
flag = 1;
break;
}
if (a[mid] > x) {
end = mid - 1;
} else {
beg = mid + 1;
}
}
if (!flag) {
printf("No such element found\n");
}
return 0;
}
Output:-
Enter number of elements in array
5
Enter 5 integers
10 20 30 40 50
Enter a number to search
30
30 is present at location 3