Skip to content

Instantly share code, notes, and snippets.

@aatishnn
Last active January 3, 2016 00:19
Show Gist options
  • Save aatishnn/8381940 to your computer and use it in GitHub Desktop.
Save aatishnn/8381940 to your computer and use it in GitHub Desktop.
Different sorting algorithms implementation
#include <stdio.h>
#include <stdlib.h>
void isort(int a[], int len) {
int key, i,j;
for(i=1; i < len; ++i) {
key = a[i];
for(j=i-1; j>=0 && key < a[j]; --j) {
a[j+1] = a[j];
}
a[j+1] = key;
}
}
void ssort(int a[], int len) {
int min, min_id, temp, i, j;
for(i=0; i<len-1;++i) {
min_id = i;
for(j=i+1;j<len;++j) {
if(a[j] < a[min_id]) {
min_id = j;
}
}
temp = a[i];
a[i] = a[min_id];
a[min_id] = temp;
}
}
void msort(int a[], int p, int q, int r) {
int t[10];
int i,j,k,m;
j=p;
m=q+1;
for(i=p; j<=q && m<=r ; i++)
{
if(a[j]<=a[m])
{
t[i]=a[j];
j++;
}
else
{
t[i]=a[m];
m++;
}
}
if(j>q)
{
for(k=m; k<=r; k++)
{
t[i]=a[k];
i++;
}
}
else
{
for(k=j; k<=q; k++)
{
t[i]=a[k];
i++;
}
}
for(k=p; k<=r; k++) {
a[k]=t[k];
}
}
void qusort(int a[], int too_big_index, int too_small_index) {
int pivot,j,temp,i;
if(too_big_index<too_small_index){
pivot=too_big_index;
i=too_big_index;
j=too_small_index;
while(i<j){
while(a[i]<=a[pivot]&&i<too_small_index)
i++;
while(a[j]>a[pivot])
j--;
if(i<j){
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
temp=a[pivot];
a[pivot]=a[j];
a[j]=temp;
qusort(a,too_big_index,j-1);
qusort(a,j+1,too_small_index);
}
}
void merge(int a[], int l, int r) {
int centre;
if(l<r) {
centre = (l + r)/2;
merge(a, l, centre);
merge(a, centre+1, r);
msort(a, l, centre, r);
}
}
int main() {
int a[10], i;
int choice;
printf("Enter 10 values: ");
for(i=0; i<10;++i) {
scanf("%d", &a[i]);
}
while(1) {
printf("1. Insertion sort\n"
"2. Selection sort\n"
"3. Merge sort\n"
"4. Quick sort\n"
"5. Print array\n");
printf("Enter an option:");
scanf("%d", &choice);
switch(choice) {
case 1:
isort(a, 10);
break;
case 2:
ssort(a, 10);
break;
case 3:
merge(a, 0, 9);
break;
case 4:
qusort(a, 0, 9);
break;
case 5:
for(i=0; i<10;++i) {
printf("%d ", a[i]);
}
printf("\n");
break;
default:
exit(0);
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment