There are various sorting algorithms viz. Selection, Insertion, Bubble, Merge, Quick, Heap, Radix, Bucket Sort.
The following algorithms take polynomial time complexity of O(n^2).
>> BUBBLE SORT
>> INSERTION SORT
>> SELECTION SORT
>> QUICK SORT
>> BUCKET SORT.
Here the worst-case time complexity is considered.
BUBBLE SORT:
Bubble sort has best-case time complexity n and a worst and average case of n^2. So why do we need Bubble sort?
>> In a special case, where from a list of elements only two elements can be manipulated (read/write) at a time. Two elements are accessed and passed forward until the end of the list is reached. And again another iteration can be started only from the beginning, not in between. There Bubble sort is the best sorting algorithm.
Although compared to other sorting algorithms, bubble sort is the worst possible sorting algorithm.
Source Code:
#include<stdio.h>
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
int bubble(int a[], int n) {
int i, j;
for (i=0; i<n-1; i++) {
for (j=0; j<n-i-1; j++) {
if (a[j] > a[j+1])
swap(&a[j], &a[j+1]);
}
}
}
int main() {
int arr[100], n;
printf("Enter the size of array: \n");
scanf("%d", &n);
printf("Enter the array: \n");
for (int i=0; i<n; i++)
scanf("%d", &arr[i]);
bubble(arr, n);
printf("After sorting: \n");
for (int i=0; i<n; i++)
printf("%d ", arr[i]);
}
INSERTION SORT :
Insertion Sort has the best case of linear time complexity and n^2 for both average and worst-case.
>> Insertion Sort is useful when the array is already sorted and contains a few numbers of elements. It requires less memory.
Source Code:
#include<stdio.h>
int insertion(int arr[], int n) {
int i, j, k;
for (i=0; i<n; i++) {
k = arr[i];
j=i-1;
while (j >= 0 && arr[j] > k) {
arr[j+1] = arr[j];
j--;
}
arr[j+1] = k;
}
}
int main() {
int arr[100], n;
printf("Enter the size of array: \n");
scanf("%d", &n);
printf("Enter the array: \n");
for (int i=0; i<n; i++)
scanf("%d", &arr[i]);
insertion(arr, n);
printf("After sorting: \n");
for (int i=0; i<n; i++)
printf("%d ", arr[i]);
}
SELECTION SORT :
Selection Sort has n^2 time complexity for the worst best and average-case scenario. It is noted for its simplicity.
>> Generally used for sorting files with very large objects and small keys.
>> Generally used for sorting files with very large objects and small keys.
Source Code:
#include<stdio.h>
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
int selection(int a[], int n) {
int i, j, min;
for (i=0; i<n-1; i++) {
min = i;
for (j=i+1; j<n; j++)
if (a[j] < a[min])
min = j;
swap(&a[i], &a[min]);
}
}
int main() {
int arr[100], n;
printf("Enter the size of array: \n");
scanf("%d", &n);
printf("Enter the array: \n");
for (int i=0; i<n; i++)
scanf("%d", &arr[i]);
selection(arr, n);
printf("After sorting: \n");
for (int i=0; i<n; i++)
printf("%d ", arr[i]);
}
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
int selection(int a[], int n) {
int i, j, min;
for (i=0; i<n-1; i++) {
min = i;
for (j=i+1; j<n; j++)
if (a[j] < a[min])
min = j;
swap(&a[i], &a[min]);
}
}
int main() {
int arr[100], n;
printf("Enter the size of array: \n");
scanf("%d", &n);
printf("Enter the array: \n");
for (int i=0; i<n; i++)
scanf("%d", &arr[i]);
selection(arr, n);
printf("After sorting: \n");
for (int i=0; i<n; i++)
printf("%d ", arr[i]);
}
Theoretically, It can be proved that the Insertion sort is faster than (40%) Selection Sort. And selection sort is faster than (60%) Bubble Sort.
>> Apart from other sorting algorithms of O(n*log(n)) time, quick sort doesn't need an auxiliary array. Although Quicksort is not a stable sorting algorithm.
>> Merge Sort follows the divide and conquers paradigm so it is easy to implement. Also, It is a stable sorting algorithm (order of equal elements is the same in input and output).
QUICK SORT :
Quick Sort is the best sorting algorithm for the average case scenario. It has O(n*log(n)) time complexity. Although for worst-case it reaches O(n^2) time complexity.
>> Apart from other sorting algorithms of O(n*log(n)) time, quick sort doesn't need an auxiliary array. Although Quicksort is not a stable sorting algorithm.
Source Code:
#include<stdio.h>
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
int temp = *a;
*a = *b;
*b = temp;
}
int partition(int arr[], int lb, int ub) {
int pivot, start=lb, end=ub;
pivot = arr[lb];
while (start < end) {
while (arr[start] <= pivot) start++;
while (arr[end] > pivot) end--;
if (start<end){swap(arr[start], arr[end]);}
}
swap(arr[lb], arr[end]);
return end;
}
int quick(int arr[], int lb, int ub) {
int loc;
if (lb < ub) {
loc = partition(arr, lb, ub);
quick(arr, lb, loc-1);
quick(arr, loc+1, ub);
}
}
int main() {
int n, a[500];
printf("Enter the size of array: \n");
scanf("%d", &n);
printf("Enter the array: \n");
for (int i=0; i<n; i++)
scanf("%d", &a[i]);
quick(a, 0, n-1);
for (int i=0; i<n; i++)
printf("%d ", a[i]);
}
MERGE SORT :
Merge Sort is a stable sorting algorithm having O(n*log(n)) time complexity for best, worst, average time complexity. This sorting algorithm was invented by well-known Mathematician, computer scientist Jon Von Neumann.
>> Merge Sort follows the divide and conquers paradigm so it is easy to implement. Also, It is a stable sorting algorithm (order of equal elements is the same in input and output).
Source Code:
#include<stdio.h>
int arr[20];
int merge(int arr[],int l,int m,int h)
{
int arr1[10],arr2[10];
int n1,n2,i,j,k;
n1=m-l+1;
n2=h-m;
for(i=0;i<n1;i++)
arr1[i]=arr[l+i];
for(j=0;j<n2;j++)
arr2[j]=arr[m+j+1];
arr1[i]=9999;
arr2[j]=9999;
i=0;j=0;
for(k=l;k<=h;k++)
{
if(arr1[i]<=arr2[j])
arr[k]=arr1[i++];
else
arr[k]=arr2[j++];
}
return 0;
}
int merge_sort(int arr[],int low,int high)
{
int mid;
if(low<high)
{
mid=(low+high)/2;
merge_sort(arr,low,mid);
merge_sort(arr,mid+1,high);
merge(arr,low,mid,high);
}
return 0;
}
int main()
{
int n,i;
printf("Enter the size of array\n");
scanf("%d",&n);
printf("Enter the elements:");
for(i=0;i<n;i++)
scanf("%d",&arr[i]);
merge_sort(arr,0,n-1);
printf("Sorted array:");
for(i=0;i<n;i++)
printf("%d ",arr[i]);
return 0;
}
No comments:
Post a Comment