2CSBS4102-Design And Analysis Of Algorithm
Practical – 5
Q . Write user defined functions for the following sorting methods and compare their
performance by time measurement with random data and Sorted data.
1. Selection Sort
code :-
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define ARRAY_SIZE 10000 // Define the size of the array
void selection_sort(int arr[], int size) {
int min_index, temp;
clock_t start, end;
double total_time;
start = clock();
for (int i = 0; i < size - 1; i++) {
min_index = i;
for (int j = i + 1; j < size; j++) {
if (arr[j] < arr[min_index]) {
min_index = j;
}
23012571013 U.V Patel College of Engineering Gayatri Solanki
2CSBS4102-Design And Analysis Of Algorithm
if (min_index != i) {
// Swap the elements
temp = arr[min_index];
arr[min_index] = arr[i];
arr[i] = temp;
end = clock();
total_time = ((double)(end - start)) / CLOCKS_PER_SEC;
printf("Time taken for sorting: %f seconds\n", total_time);
int main() {
int arr[ARRAY_SIZE];
int choice;
printf("1. Sorted Data\n2. Random Data\nEnter your choice: ");
scanf("%d", &choice);
switch (choice) {
case 1:
for (int i = 0; i < ARRAY_SIZE; i++) {
arr[i] = i + 1;
23012571013 U.V Patel College of Engineering Gayatri Solanki
2CSBS4102-Design And Analysis Of Algorithm
break;
case 2:
srand(time(NULL));
for (int i = 0; i < ARRAY_SIZE; i++) {
arr[i] = rand() % ARRAY_SIZE;
break;
default:
printf("Invalid choice!\n");
return 1;
selection_sort(arr, ARRAY_SIZE);
return 0;
Output :- 23012571013 U.V Patel
College of Engineering Gayatri Solanki
2CSBS4102-Design And Analysis Of Algorithm
2. Bubble Sort
code:-#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define SIZE 10000
void bubble_sort(int arr[], int size) {
int flag, temp;
clock_t start, end;
double total_time;
start = clock();
for (int i = 0; i < size - 1; i++) {
flag = 0;
for (int j = 0; j < size - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
flag = 1; }
if (flag == 0) {
break;
23012571013 U.V Patel College of Engineering Gayatri Solanki
2CSBS4102-Design And Analysis Of Algorithm
end = clock();
total_time = ((double)(end - start)) / CLOCKS_PER_SEC;
printf("Time taken for sorting: %f seconds\n", total_time);
int main() {
int arr[SIZE];
int choice;
printf("1. Sorted Data\n2. Random Data\nEnter your choice: ");
scanf("%d", &choice);
switch (choice) {
case 1:
for (int i = 0; i < SIZE; i++) {
arr[i] = i + 1;
break;
case 2:
srand(time(NULL));
for (int i = 0; i < SIZE; i++) {
23012571013 U.V Patel College of Engineering Gayatri Solanki
2CSBS4102-Design And Analysis Of Algorithm
arr[i] = rand() % SIZE;
break;
default:
printf("Invalid choice!\n");
return 1; }
bubble_sort(arr, SIZE);
return 0; }
output:-
3. Insertion Sort
code:-#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define SIZE 10000
23012571013 U.V Patel College of Engineering Gayatri Solanki
2CSBS4102-Design And Analysis Of Algorithm
void insertion_sort(int arr[], int size) {
int key, i, j;
clock_t start, end;
double total_time;
start = clock();
for (j = 1; j < size; j++) {
key = arr[j];
i = j - 1;
while (i >= 0 && arr[i] > key) {
arr[i + 1] = arr[i];
i = i - 1;
arr[i + 1] = key; }
end = clock();
total_time = ((double)(end - start)) / CLOCKS_PER_SEC;
printf("Time taken for sorting: %f seconds\n", total_time);
int main() {
int arr[SIZE];
int choice;
23012571013 U.V Patel College of Engineering Gayatri Solanki
2CSBS4102-Design And Analysis Of Algorithm
printf("1. Sorted Data\n2. Random Data\nEnter your choice: ");
scanf("%d", &choice);
switch (choice) {
case 1:
for (int i = 0; i < SIZE; i++) {
arr[i] = i + 1;
break;
case 2:
srand(time(NULL));
for (int i = 0; i < SIZE; i++) {
arr[i] = rand() % SIZE;
break;
default:
printf("Invalid choice!\n");
return 1;
insertion_sort(arr, SIZE);
return 0;
23012571013 U.V Patel College of Engineering Gayatri Solanki
2CSBS4102-Design And Analysis Of Algorithm
output:-
4. Merge Sort
code:-#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define SIZE 10000
// Function prototypes
void merge_sort(int arr[], int start, int finish, int temp[]);
void merge(int arr[], int start, int mid, int finish, int temp[]);
int main() {
int arr[SIZE];
int temp[SIZE];
int choice;
printf("1. Sorted Data\n2. Random Data\nEnter your choice: ");
scanf("%d", &choice);
switch (choice) {
23012571013 U.V Patel College of Engineering Gayatri Solanki
2CSBS4102-Design And Analysis Of Algorithm
case 1:
for (int i = 0; i < SIZE; i++) {
arr[i] = i + 1;
break;
case 2:
srand(time(NULL));
for (int i = 0; i < SIZE; i++) {
arr[i] = rand() % SIZE; }
break;
default:
printf("Invalid choice!\n");
return 1; }
clock_t start, end;
double total_time;
start = clock();
merge_sort(arr, 0, SIZE - 1, temp);
end = clock();
total_time = ((double)(end - start)) / CLOCKS_PER_SEC;
printf("Time taken for sorting: %f seconds\n", total_time);
return 0; }
23012571013 U.V Patel College of Engineering Gayatri Solanki
2CSBS4102-Design And Analysis Of Algorithm
void merge_sort(int arr[], int start, int finish, int temp[]) {
if (start < finish) {
int mid = start + (finish - start) / 2;
merge_sort(arr, start, mid, temp);
merge_sort(arr, mid + 1, finish, temp);
merge(arr, start, mid, finish, temp);
void merge(int arr[], int start, int mid, int finish, int temp[]) {
int i = start; // Starting index of the first subarray
int j = mid + 1; // Starting index of the second subarray
int k = start; // Starting index of the merged array
while (i <= mid && j <= finish) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
while (i <= mid) {
temp[k++] = arr[i++];
23012571013 U.V Patel College of Engineering Gayatri Solanki
2CSBS4102-Design And Analysis Of Algorithm
while (j <= finish) {
temp[k++] = arr[j++];
for (i = start; i <= finish; i++) {
arr[i] = temp[i];
output:-
6. Quick Sort
code:-#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define size 10000
23012571013 U.V Patel College of Engineering Gayatri Solanki
2CSBS4102-Design And Analysis Of Algorithm
void quick_sort(int[], int, int);
int partition(int[], int, int);
int main() {
int a[size];
int choice, i;
clock_t start, end;
double total_time;
printf("1. Sorted Data 2. Random Data \n");
scanf("%d", &choice);
switch (choice) {
case 1:
for (i = 0; i < size; i++) {
a[i] = i + 1;
break;
case 2:
srand(time(NULL));
for (i = 0; i < size; i++) {
a[i] = rand() % size;
break;
default:
23012571013 U.V Patel College of Engineering Gayatri Solanki
2CSBS4102-Design And Analysis Of Algorithm
printf("Invalid choice!\n");
return 0;
start = clock();
quick_sort(a, 0, size - 1);
end = clock();
total_time = (double)(end - start) / CLOCKS_PER_SEC;
printf("Time: %f seconds\n", total_time);
return 0;
void quick_sort(int a[], int lb, int ub) {
if (lb < ub) {
int pivot_index = partition(a, lb, ub);
quick_sort(a, lb, pivot_index - 1);
quick_sort(a, pivot_index + 1, ub);
int partition(int a[], int lb, int ub) {
int pivot = a[lb];
int start = lb;
23012571013 U.V Patel College of Engineering Gayatri Solanki
2CSBS4102-Design And Analysis Of Algorithm
int end = ub;
while (start < end) {
while (a[start] <= pivot && start < ub)
start++;
while (a[end] > pivot)
end--;
if (start < end) {
int temp = a[start];
a[start] = a[end];
a[end] = temp;
a[lb] = a[end];
a[end] = pivot;
return end;
23012571013 U.V Patel College of Engineering Gayatri Solanki
2CSBS4102-Design And Analysis Of Algorithm
output:-
23012571013 U.V Patel College of Engineering Gayatri Solanki
