Practical-1

GUJARAT TECHNOLOGICAL UNIVERSITY

SCHOOL OF ENGINEERING AND TECHNOLOGY

Course Code & Name 3150703-Analysis And Design of Algorithms

Academic Term: AY-2025-26-Odd Term Semester 5

Student Enrollment No: 231370107041 Batch: B2

Student Name: Parth Devangbhai Oza

AIM/Objective:
Implementation and Time analysis of sorting algorithms.
1
Bubble sort, Selection sort, Insertion sort, Merge sort and Quicksort
Expected Outcome: CO/PO/PSO

Student Report with Experiment Results and Analysis

❖ Implementation and Time analysis of sorting

algorithms.
Sorting algorithms are used to rearrange elements of a list in a particular order (like
ascending or descending). Efficient sorting is important for improving the
performance of other algorithms that require sorted data (like search and merge
algorithms).

• Types of shorting algorithms:

(1) Bubble Sort
(2) Selection Sort
(3) Insertion Sort
(4) Merge Sort (Divide & Conquer)
(5) Quick Sort (Divide & Conquer)

• Here brief notes for this all shorting algorithms:

1. Bubble Sort:
 Practical-1
• Bubble Sort is a simple comparison-based sorting algorithm. It repeatedly steps
through the list, compares adjacent elements, and swaps them if they are in the
wrong order.
• We sort the array using multiple passes. After the first pass, the maximum element
goes to end (its correct position). Same way, after second pass, the second largest
element goes to second last position and so on.

➢ Bubble Sort Algorithm

1. Start by repeating the process for (n - 1) passes, where n is the total number of
elements in the array.
2. In each pass, compare each pair of adjacent elements in the array.
3. For every pair of adjacent elements:
o If the left element is greater than the right element, swap them.
4. After each complete pass, the largest unsorted element "bubbles up" to its
correct position at the end of the array.
5. Continue this process for all passes until the array is completely sorted.

Algorithm:
1. Start

2. Repeat from i = 0 to n-1 (outer loop):

a. Set a flag "swapped" = false

b. Repeat from j = 0 to n-i-2 (inner loop):

i. If arr[j] > arr[j+1], then
- Swap arr[j] and arr[j+1]
- Set swapped = true

c. If swapped == false
- Break (array is already sorted)

3. End

Code
#include <stdio.h>
void bubbleSort(int arr[], int n) {
int i, j, temp;
for (i = 0; i < n - 1; i++) {
for (j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
 Practical-1
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}

void printArray(int arr[], int size) {

int i;
for (i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}

int main() {
int n, i;
printf("Enter the number of elements: ");
scanf("%d", &n);
int arr[n]; // Declare array of size n
printf("Enter %d integers:\n", n);
for (i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
printf("Original array: ");
printArray(arr, n);
bubbleSort(arr, n);
printf("Sorted array (Bubble Sort): ");
printArray(arr, n);
return 0;
}
 Practical-1
2. Selection sort

• Selection Sort is a simple comparison-based sorting algorithm. It

divides the array into two parts: sorted and unsorted. It
repeatedly selects the smallest (or largest) element from the
unsorted portion and swaps it with the first element of the
unsorted part, moving the boundary of the sorted section one
step forward.
Algorithm:
1. Start
2. Repeat from i = 0 to n-1 (outer loop):
a. Assume the minimum element index is i
b. Repeat from j = i+1 to n-1 (inner loop):
• If arr[j] < arr[min_idx], set min_idx = j
c. Swap arr[i] and arr[min_idx]
3. End

Code
#include <stdio.h>
void selectionSort(int arr[], int n) {
int i, j, min_idx, temp;
for (i = 0; i < n - 1; i++) {
min_idx = i;
for (j = i + 1; j < n; j++)
if (arr[j] < arr[min_idx])
min_idx = j;
temp = arr[min_idx];
arr[min_idx] = arr[i];
arr[i] = temp;
}
}
 Practical-1
void printArray(int arr[], int size) {
int i;
for (i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
int main() {
int n, i;
printf("Enter the number of elements: ");
scanf("%d", &n);
int arr[n]; // Declare array of size n
printf("Enter %d integers:\n", n);
for (i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
printf("Original array: ");
printArray(arr, n);
selectionSort(arr, n);
printf("Sorted array (Selection Sort): ");
printArray(arr, n);
return 0;
}
 Practical-1
3. Insertion Sort
Insertion Sort builds the final sorted array one item at a time. It works
similarly to the way we sort playing cards in our hands. It picks each
element from the unsorted part and places it at the correct position in
the sorted part.
Algorithm:
1. Start
2. Repeat from i = 1 to n-1:
a. Set key = arr[i]
b. Set j = i - 1
c. While j ≥ 0 and arr[j] > key:
• arr[j+1] = arr[j]
• j=j-1
d. arr[j+1] = key
3. End

Code
#include <stdio.h>
void insertionSort(int arr[], int n) {
int i, key, j;
for (i = 1; i < n; i++) {
key = arr[i];
j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
void printArray(int arr[], int size) {
 Practical-1
int i;
for (i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
int main() {
int n, i;
printf("Enter the number of elements: ");
scanf("%d", &n);
int arr[n]; // Declare array of size n
printf("Enter %d integers:\n", n);
for (i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
printf("Original array: ");
printArray(arr, n);
insertionSort(arr, n);
printf("Sorted array (Insertion Sort): ");
printArray(arr, n);
return 0;
}
 Practical-1
4. Merge Sort
Merge Sort is an efficient, general-purpose, comparison-based Divide
and Conquer algorithm. It divides the input array into two halves,
recursively sorts them, and then merges the sorted halves.
Algorithm:
1. Start
2. If left index < right index:
a. Find middle point: mid = (left + right) / 2
b. Recursively sort first half
c. Recursively sort second half
d. Merge both sorted halves
3. End

Code
#include <stdio.h>
#include <stdlib.h> // For malloc and free
void merge(int arr[], int l, int m, int r) {
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
int *L = (int *)malloc(n1 * sizeof(int));
int *R = (int *)malloc(n2 * sizeof(int));
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];
i = 0;
j = 0;
k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
 Practical-1
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
free(L);
free(R);
}
void mergeSort(int arr[], int l, int r) {
if (l < r) {
int m = l + (r - l) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
 Practical-1
void printArray(int arr[], int size) {
int i;
for (i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n"); }
int main() {
int n, i;
printf("Enter the number of elements: ");
scanf("%d", &n);
int *arr = (int *)malloc(n * sizeof(int)); // Dynamically allocate array
if (arr == NULL) {
printf("Memory allocation failed!\n");
return 1;
}
printf("Enter %d integers:\n", n);
for (i = 0; i < n; i++) {
scanf("%d", &arr[i]); }
printf("Original array: ");
printArray(arr, n);
mergeSort(arr, 0, n - 1);
printf("Sorted array (Merge Sort): ");
printArray(arr, n);
free(arr); // Free dynamically allocated memory
return 0; }
 Practical-1
5. Quick Sort
Quick Sort is an efficient Divide and Conquer algorithm. It selects a
"pivot" element and partitions the array such that elements smaller than
the pivot come before it, and larger elements come after. It then
recursively sorts the partitions.
Algorithm:
1. Start
2. Choose a pivot element
3. Partition the array around the pivot
• Elements < pivot → left side
• Elements > pivot → right side
4. Recursively apply the same logic to sub-arrays
5. End

Code
#include <stdio.h>
void swap(int* a, int* b) {
int t = *a;
*a = *b;
*b = t;
}
int partition(int arr[], int low, int high) {
int pivot = arr[high];
int i = (low - 1);
for (int j = low; j <= high - 1; j++) {
if (arr[j] <= pivot) {
i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
 Practical-1
return (i + 1);
}
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
void printArray(int arr[], int size) {
int i;
for (i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
int main() {
int n, i;
printf("Enter the number of elements: ");
scanf("%d", &n);
int arr[n]; // Declare array of size n
printf("Enter %d integers:\n", n);
for (i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
printf("Original array: ");
printArray(arr, n);
quickSort(arr, 0, n - 1);
printf("Sorted array (Quick Sort): ");
printArray(arr, n);
 Practical-1
return 0;
}

Evaluation Rubrics Marks Inadequate Good Excellent

0% 50% 100%
1 The understanding of the Student regarding 2
the objective of the given practical
2 Installation of Software or Hardware Setup 2
level
3 Quality of the Analysis done 2
4 Quality of the report including concluding 2
reamrks and Findings
5 Question & Answer related to given practical 2
& timely submission
10
Total Marks Obtained Out of 10

Date of Completion: _________________ Course Co-ordinator:_________________________