Bubble sort is a simple sorting algorithm that works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order.
1.
#include<stdio.h>
#include<conio.h>
#define MAXSIZE 10
void main()
{
int array[MAXSIZE];
int i, j, num, temp;
printf("Enter the value of num \n");
scanf("%d",&num);
printf("Enter the elements one by one \n");
for(i=0;i<num;i++)
{
scanf("%d",&array[i]);
}
/* Bubble sorting begins */
for(i=0;i<num;i++)
{
for(j=0;j<(num-i-1);j++)
{
if(array[j]>array[j+1]
{
temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
}
}
printf("Sorted array is...\n");
for (i=0;i<num;i++)
{
printf("%d\n", array[i]);
}
getch();
}
Output:
Enter the value of num
6
Enter the elements one by one
20
95
32
12
86
60
Sorted array is…
12
20
32
60
86
95
Insertion sort
Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list. Each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there. It repeats until no input elements remain.
2.
#include<stdio.h>
#include<conio.h>
#define MAX 10
void insertion_sort(int *);
void main()
{
int a[MAX], i;
printf("Enter 10 elements to be sorted:\n");
for (i = 0;i < MAX;i++)
{
scanf("%d", &a[i]);
}
insertion_sort(a);
printf("Sorted elements:\n");
for (i=0;i<MAX; i++)
{
printf("%d ", a[i]);
}
getch();
}
/* sorts the input */
void insertion_sort(int *x)
{
int temp, i, j;
for(i = 1;i < MAX;i++)
{
temp = x[i];
j = i - 1;
while(temp < x[j] && j >= 0)
{
x[j + 1] = x[j];
j = j - 1;
}
x[j + 1] = temp;
}
}
Output:
Enter 10 elements to be sorted:
2 4 7 8 3 6 12 24 13 1
Sorted elements:
1 2 3 4 6 7 8 12 13 24
Selection sort
Selection sort divides the input list into two parts: the sublist of items already sorted and the sublist of items remaining to be sorted. It proceeds by finding the smallest (or largest) element in the unsorted sublist, exchanging it with the leftmost unsorted element and moving the sublist boundaries one element to the right.
3.
#include<conio.h>
#include<stdio.h>
#define max 50
void selection_sort(int, int[]);
void main()
{
int i, size, data[max];
printf("\nEnter no of elements:");
scanf("%d",&size);
printf("\nEnter elements:\n");
for(i=1;i<=size;i++)
scanf("%d",&data[i]);
selection_sort(size, data);
getch();
}
void selection_sort(int n, int data[])
{
int i, j, min, temp;
printf("Sorted List is:\n");
for(i=1;i<=n-1;i++)
{
min = i;
for(j=i+1;j<=n;j++)
{
if(data[j]<data[min])
min = j;
}
temp=data[i];
data[i]=data[min];
data[min]=temp;
}
for(i=1;i<=n;i++)
printf("%d\n",data[i]);
}
Output:
Enter no of Elements:5
Enter Elements:
-5
-40
-12
24
10
Sorted list is:
-40
-12
-5
10
24
Alphabetical sort
Alphabetical sort is a program whereby strings of characters are placed in order based on the position of the characters in the conventional ordering of an alphabet.
4.
#include <stdio.h>
#include <string.h>
#include <conio.h>
void main()
{
char name[10][8], tname[10][8], temp[8];
int i, j, n;
printf("Enter the value of n:
\n");
scanf("%d", &n);
printf("Enter %d names:\n", n);
for(i = 0; i < n; i++)
{
scanf("%s", name[i]);
strcpy(tname[i], name[i]);
}
for(i = 0; i < n - 1 ; i++)
{
for(j = i + 1; j < n; j++)
{
if (strcmp(name[i],name[j]) > 0)
{
strcpy(temp, name[i]);
strcpy(name[i], name[j]);
strcpy(name[j], temp);
}
}
}
printf("Sorted names:\n");
for (i = 0; i < n; i++)
{
printf("%s\n",name[i]);
}
getch();
}
Output:
Enter the value of n:
5
Enter 5 names:
int
float
double
char
string
Sorted names:
char
double
float
int
string
Quicksort
Quicksort is a very efficient sorting algorithm.It has two phases:
-the partition phase and
-the sort phase.
Most of the work is done in the partition phase - it works out where to divide the work. The sort phase simply sorts the two smaller problems that are generated in the partition phase.
5.
#include<stdio.h>
#include<conio.h>
void quicksort(int[],int,int);
int main()
{
int list[50];
int size, i;
clrscr();
printf("Enter the number of elements: ");
scanf("%d",&size);
printf("Enter the elements to be sorted:\n");
for (i = 0; i < size; i++)
{
scanf("%d", &list[i]);
}
quicksort(list, 0, size - 1);
printf("Sorted elements:\n");
for (i = 0; i < size; i++)
{
printf("%d\n", list[i]);
}
printf("\n");
getch();
return 0;
}
void quicksort(int list[], int low, int high)
{
int pivot, i, j, temp;
if (low < high)
{
pivot = low;
i = low;
j = high;
while (i < j)
{
while (list[i] <= list[pivot] && i <= high)
{
i++;
}
while (list[j] > list[pivot] && j >= low)
{
j--;
}
if (i < j)
{
temp = list[i];
list[i] = list[j];
list[j] = temp;
}
}
temp = list[j];
list[j] = list[pivot];
list[pivot] = temp;
quicksort(list, low, j - 1);
quicksort(list, j + 1, high);
}
}
Output:
Enter the number of elements: 4
Enter the elements to be sorted:
12 24 36 -12
Sorted elements:
-12
12
24
36
Merge sort
Merge sort is a divide and conquer comparison-based sorting algorithm. It works as follows:-
1. Divide the unsorted list into n sublists, each containing 1 element (a list of 1 element is considered sorted).
2. Repeatedly merge sublists to produce new sublists until there is only 1 sublist remaining. This will be the sorted list.
6.
#include <stdio.h>
#include<conio.h>
void mergeSort(int [], int, int, int);
void partition(int [],int, int);
int main()
{
int list[50];
int i, size;
clrscr();
printf("Enter total number of elements:");
scanf("%d", &size);
printf("Enter the elements:\n");
for(i = 0; i < size; i++)
{
scanf("%d", &list[i]);
}
partition(list, 0, size - 1);
printf("Sorted elements:\n");
for(i = 0;i < size; i++)
{
printf("%d\n",list[i]);
}
return 0;
}
void partition(int list[],int low,int high)
{
int mid;
if(low < high)
{
mid = (low + high) / 2;
partition(list, low, mid);
partition(list, mid + 1, high);
mergeSort(list, low, mid, high);
}
}
void mergeSort(int list[],int low,int mid,int high)
{
int i, mi, k, lo, temp[50];
lo = low;
i = low;
mi = mid + 1;
while ((lo <= mid) && (mi <= high))
{
if (list[lo] <= list[mi])
{
temp[i] = list[lo];
lo++;
}
else
{
temp[i] = list[mi];
mi++;
}
i++;
}
if (lo > mid)
{
for(k = mi; k <= high; k++)
{
temp[i] = list[k];
i++;
}
}
else
{
for(k = lo; k <= mid; k++)
{
temp[i] = list[k];
i++;
}
}
for(k = low; k <= high; k++)
{
list[k] = temp[k];
}
}
Output:
Enter total number of elements:5
Enter the elements:
5
4
3
2
1
Sorted elements:
1
2
3
4
5
Heapsort
The heapsort algorithm can be divided into two parts.
-Step 1: a heap is built out of the data.
-Step 2: a sorted array is created by repeatedly removing the largest element from the heap, and inserting it into the array.
The heap is reconstructed after each removal. Once all objects have been removed from the heap, we have a sorted array. The direction of the sorted elements can be varied by choosing a min-heap or max-heap in step one.
Complexity:
Best case = Avg case = Worst case = 0(nlogn)
7.
#include<stdio.h>
#include<conio.h>
void main()
{
int heap[10], no, i, j, c, root, temp;
clrscr();
printf("\n Enter no of elements:");
scanf("%d", &no);
printf("\n Enter the elements:\n");
for(i = 0; i < no; i++)
scanf("%d", &heap[i]);
for(i = 1; i < no; i++)
{
c = i;
do
{
root = (c - 1) / 2;
if(heap[root] < heap[c]) /* to create MAX heap array */
{
temp = heap[root];
heap[root] = heap[c];
heap[c] = temp;
}
c = root;
} while(c != 0);
}
printf("Heap array:\n");
for(i = 0; i < no; i++)
printf("%d\t ", heap[i]);
for(j = no - 1; j >= 0; j--)
{
temp = heap[0];
heap[0] = heap[j];
/* swap max element with rightmost leaf element */
heap[j] = temp;
root = 0;
do
{
c = 2 * root + 1;
/* left node of root element */
if((heap[c] < heap[c + 1]) && c < j-1)
c++;
if(heap[root]<heap[c] && c<j)
/* again rearrange to max heap array */
{
temp = heap[root];
heap[root] = heap[c];
heap[c] = temp;
}
root = c;
} while(c < j);
}
printf("\nThe sorted elements:\n");
for(i = 0; i < no; i++)
printf("%d\n", heap[i]);
getch();
}
Output:
Enter no of elements :3
Enter the elements :
8
13
-7
Heap array:
13 8 -7
The sorted elements:
-7
8
13
Please post comment.Also you can post programming related problems.
Thank you for giving diffrrent sorting methods.
ReplyDelete