3/6/08

C Selection Sort

Selection sort is a simple sorting algorithm. Selection sort replaces the next element with the least of the rest elements in a table starting from the first one.
e.g. table[i] is replaced by the min(table[i] - table[N-1]) where N is the table size. To read more about selection sort visit Wikipedia or click here.
Here is an implementation in C programming language. Implemented with and without recursion.

#include <stdio.h>
#include <stdlib.h>
#define N 50

int b[N];

/*a[]-table & n end of table
return position of minimum*/
int min(int a[],int n) {
int i,y,mi;
mi = a[0];
y=0;
for (i=1; i<n ; i++) {
if ( a[i] < mi ) {
mi = a[i];
y = i;
}
}
return (y);
}

void selection_sort(int p[],int n) {
int k,y,i,x,*d=p;

for (i=0,k=n;i<=n;i++,d++,k=k-1) {
y=min(d,k);
x=*d; *d=d[y]; d[y]=x;
}
}

void selection_sort2(int p[],int n) {
/*recursive using min() */
int x,y,*d=p;

y=min(d,n);
x=*d; *d=d[y]; d[y]=x;
d++;n=n-1;
if (n>=0) {
selection_sort2(d,n);
}
}
int main(int argc, char *argv[]) {
int len,i,l,k;

printf("Give table numbers, 999999 to stop: ");
for(i=0;i<N;i++) {
scanf("%d",&k);
if (k!= 999999 ) { b[i]=k;}
else {len=i; break;} /*len=end oftable*/
}

printf("\nThe least number is at index : %d",min(b,len));
printf("\n\n------------------------\n\n");

selection_sort2(b,len);
printf("Sorted table with recursion : \n");
for (i=0;i<len;i++) {
printf("%d\n",b[i]);
}
printf("\n\n-----------------------\n\n");

selection_sort(b,len);
printf("Sorted table without recursion : \n");
for (i=0;i<len;i++) {
printf("%d\n",b[i]);
}
system("pause");//only for windows
exit(0);
}

No comments: