DATE: 09/12/2025

ANALYSIS OF SORTING ALGORITHM

AIM:

To write a C program to perform soting algorithm and analyze its

ALGORITHM:

1. Start with the given array.

2. Selection Sort:

* Find the smallest element from the unsorted part of the array.

* Swap it with the first element of the unsorted part.

* Move the boundary of the sorted portion one step forward.

3. Bubble Sort:

* Compare each pair of adjacent elements in the unsorted part.

* Swap them if they are in the wrong order.

* Repeat this process until the largest element “bubbles” to the correct
position at the end.

4. Insertion Sort:

* Pick the next element from the unsorted part.

* Compare it with the elements in the sorted portion.

* Shift all larger elements one position to the right.

5. Merge Sort:

* Divide the array into two halves.

* Recursively divide each half until single-element arrays remain.

* Merge two sorted halves by comparing elements one by one.

* Continue merging until the whole array is sorted.

6. Quick Sort:

* Choose a pivot element.

* Partition the array so all smaller elements go left of pivot and larger
elements go right.

* Place the pivot in its correct position.

* Recursively apply the same process to left and right partitions.

7. Repeat steps 2–6 as needed according to the method used until the
array is fully sorted.

SOURCE CODE:

#include <stdio.h>

#include <stdlib.h>

void bubble_sort(int arr[],int n)

for(int i=0;i<n;i++)

{
 for(int j=0;j<n-i-1;j++)

if(arr[j]>arr[j+1])

int temp=arr[j];

arr[j]=arr[j+1];

arr[j+1]=temp;

void selection_sort(int arr[],int n)

int min_index,i;

for(i=0;i<n-1;i++)

min_index=i;

for(int j=i;j<n;j++)

if(arr[j]<arr[min_index])
 {

min_index=j;

int temp=arr[i];

arr[i]=arr[min_index];

arr[min_index]=temp;

void insertion_sort(int arr[],int n)

for(int i=1;i<n;i++)

int key=arr[i];

int j=i-1;

while(j>=0&&arr[j]>key) {

arr[j+1]=arr[j];

j=j-1;

arr[j+1]=key;
 }

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[n1];

int R[n2];

for(int i=0;i<n1;i++)

L[i]=arr[l+i];

for(int i=0;i<n2;i++)

R[i]=arr[m+1+i];

i=0,j=0,k=l;

while(i<n1 && j<n2)

{
 if(L[i]<R[j])

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++;

void merge_sort(int arr,int l,int r)

if(l<r)

int m=l+(r-l)/2;

merge_sort(arr,l,m);

merge_sort(arr,m+1,r);

merge(arr,l,m,r);

int partition(int arr[], int low, int high) {

//last element is the pivot

int pivot = arr[high];

//here i is the first index before sorting.

int i = low - 1;

for (int j = low; j <= high - 1; j++) {

//here i++ acts as the index for placing the small element.

i++;

swap(&arr[i], &arr[j]);

//swapping pivot element

swap(&arr[i + 1], &arr[high]);

return i + 1;

void quick_sort(int arr[], int low, int high) {

if (low < high) {

int pi = partition(arr, low, high);

//pi-1 indicates elements before pivot element

quick_sort(arr, low, pi - 1);

//pi+1 indicates elements after pivot element.

quick_sort(arr, pi + 1, high);

}
void swap(int* a, int* b) {

int t = *a;

*a = *b;

*b = t;

int main()

int n;

printf("Enter the number of elements in the array:");

scanf("%d",&n);

printf("Enter the %d elements of the array:",n);

int arr[n];

for(int i=0;i<n;i++)

scanf("%d",&arr[i]);

quick_sort(arr,0,n);

printf("\nSorted array using quick sort:");

for(int i=0;i<n;i++)

{
 printf("%d ",arr[i]);

merge_sort(arr,0,n);

printf("\nSorted array using merge sort:");

for(int i=0;i<n;i++)

printf("%d ",arr[i]);

insertion_sort(arr,n);

printf("\nSorted array using insertion sort:");

for(int i=0;i<n;i++)

printf("%d ",arr[i]);

selection_sort(arr,n);

printf("\nSorted array using selection sort:");

for(int i=0;i<n;i++)

printf("%d ",arr[i]);

}
 bubble_sort(arr,n);

printf("\nSorted array using bubble sort:");

for(int i=0;i<n;i++)

printf("%d ",arr[i]);

return 0;

COMPLEXITY:
Sort Best Case Average Case Worst Case Space Complexity
Bubble Sort O(n) O(n²) O(n²) O(1)
Selection Sort O(n²) O(n²) O(n²) O(1)
Insertion Sort O(n) O(n²) O(n²) O(1)
Merge Sort O(n log n) O(n log n) O(n log n) O(n)
Quick Sort O(n log n) O(n log n) O(n²) O(log n)
OUTPUT:

Enter the number of elements in the array:5

Enter the 5 elements of the array:1

13

45

-5

Sorted array using quick sort:-5 1 2 13 45

Sorted array using merge sort:-5 1 2 13 45

Sorted array using insertion sort:-5 1 2 13 45

Sorted array using selection sort:-5 1 2 13 45

Sorted array using bubble sort:-5 1 2 13 45