Wednesday, July 16, 2008

Sorting Algorithms in C

Here we will give you the implementation of different sorting algorithms in C language. All the implementations have been tested using "gcc" compiler in cygwin. We have used file input and output.

Input specification: Input file contains 15,000 integers for each case. The numbers are generated in the input file randomly.
Output specification: Output file contains the numbers in ascending order.

1. Bubble Sort:

#include<stdio.h>
#include<stdlib.h>
#define SIZE 15000

void bubbleSort(unsigned int[]);

int main(void)
{
unsigned int A[SIZE];
int i,j;
if(freopen("bubble.in","r",stdin)==NULL)
{
printf("Error Reading File");
exit(1);
}
freopen("bubble.out","w",stdout);
for(i=0;i<SIZE;i++)
scanf("%d",&A[i]);
bubbleSort(A);
for(i=0;i<SIZE;i++)
printf("%d ",A[i]);
fclose(stdin);
fclose(stdout);
return 0;
}

void bubbleSort(unsigned int A[])
{
unsigned int temp;
int i,j;
for(i=0;i<SIZE;i++)
{
for(j=SIZE-1;j>i;j--)
if(A[j]<A[j-1])
{
temp=A[j];
A[j]=A[j-1];
A[j-1]=temp;
}
}
}

Input file: bubble.in
Output file: bubble.out
Complexity: O(n^2)

2. Insertion Sort

#include<stdio.h>
#include<stdlib.h>
#define SIZE 15000

void insertionSort(unsigned int[]);

int main(void)
{
unsigned int A[SIZE];
int i,j;
if(freopen("insertion.in","r",stdin)==NULL)
{
printf("Error Reading File");
exit(1);
}
freopen("insertion.out","w",stdout);
for(i=0;i< SIZE;i++)
scanf("%d",&A[i]);
insertionSort(A);
for(i=0;i< SIZE;i++)
printf("%d ",A[i]);
fclose(stdin);
fclose(stdout);
return 0;
}

void insertionSort(unsigned int a[])
{
int i,j;
unsigned int key;
for(j=1;j< SIZE;j++)
{
key = a[j];
i = j-1;
while(i>=0 && a[i]>key)
{
a[i+1]=a[i];
i=i-1;
}
a[i+1]=key;
}
}

Input file: insertion.in
Output file: insertion.out
Complexity: O(n^2)

More sorting algorithms to follow..


No comments: