These Algorithms include:
----------------------------------------------
1. Bubble Sort: It is the most simple sorting algorithm that repeatedly iterates through every element in the array and swapping the adjacent elements, by comparing them. And swaps the elements if they are not in proper arrangement/order. Thus giving us a sorted array of elements.
HOW IT WORKS: Firstly we compare the first two elements of the array
and if the element at the 1st index is greater than the element at the 2nd
index, then their positions are swapped. And then the so formed array in
2nd pass, that array's 2nd, and 3rd elements are compared and again swapped if the 2nd element is greater than the 3rd element. And so on.
#include<stdio.h>
int main()
{
int i,temp,p,c,n,count=-1,c1=-1,c2=-1;
int a[100];
printf("enter the size of array\n");
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
for(p=0;p<n-1;p++)
{ c2++;
for(c=0;c<n-1-p;c++)
{ c1++;
if(a[c]>a[c+1])
{ count++;
temp=a[c];
a[c]=a[c+1];
a[c+1]=temp;
}
}
}
printf("\n the sorted array is:");
for(i=0;i<n;i++)
printf("%d ",a[i]);
printf("\n the number of passes = %d",c2);
printf("\n the number of comparisons = %d",c1);
printf("\n the number of total swaps = %d",count);
return 0;
}
* Here we can also come to know about the total number of passes and comparisons.
Properties of Bubble sort are:
Worst and Average Case Time Complexity: O(n^2). The worst case occurs when the array is sorted in opposite
direction.
Best Case Time Complexity: O(n). The best-case occurs when the array is already sorted.
Auxiliary Space: O(1)
----------------------------------------------
2. Insertion Sort: In this sorting technique we have to consider the given array as 2
lists, 1 sorted on the right side of the array and other unsorted, here we
put 1 element on the right side, i.e sorted side, and then go on comparing
each element on the left side to the element placed on the right side
and then giving the element a position based on the comparison.
#include<stdio.h>
int main()
{ int i, j, size, temp, number[25];
printf("Enter size: ");
scanf("%d",&size);
printf("Enter Elements \n");
for(i=0;i<size;i++)
scanf("%d",&number[i]);
for(i=1;i<size;i++){
temp=number[i];
j=i-1;
while((temp<number[j])&&(j>=0)){
number[j+1]=number[j];
j=j-1;
}
number[j+1]=temp;
}
printf("Sorted Array: ");
for(i=0;i<size;i++)
printf(" %d",number[i]);
return 0;
}
Properties of Insertion sort are:
Worst and Average Case Time Complexity: O(n^2). The worst case occurs when the array is sorted in opposite
direction.
Best Case Time Complexity: O(n). The best-case occurs when the array is already sorted.
Auxiliary Space: O(1)
----------------------------------------------
3. Selection Sort: This sorting algorithm 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 inserted at the end of the sorted array. This process
continues moving unsorted array boundary by one element to the right
HOW IT WORKS :
loop for i=0 to i<size
select the smallest among A[i], . . . , A[n]
swap it with A[i];
end
#include <stdio.h>
int main()
{
int array[10], i,j,a,b,temp size;
printf("Enter Size");
scanf("%d", &size);
printf("Enter Elements");
for (i = 0; i < size; i++)
scanf("%d", &array[i]);
for (i = 0 ; i < size;i++)
{
for (j = i ; j < size; j++)
{
if (arr[i] > arr[j])
{
temp =
arr[i];
arr[i] =
arr[j];
arr[j] =
temp;
}
}
}
printf("\nSorted array is ");
for (i = 0; i < size;i++)
printf(" %d ", array[i]);
return 0;
}
Properties of Selection sort are:
Worst and Average Case Time Complexity: O(n^2). The worst case occurs when the array is sorted in opposite
direction.
Best Case Time Complexity: O(n^2). As in all cases, it will search minimum linearly for all n-1
iterations.
Auxiliary Space: O(1)
