22 Şubat 2010 Pazartesi

Silly Sort C Program

//silly sort program
#include<stdio.h>

typedef struct{ //this struct is for values and places of numbers
int value;
int place;
}node;

#define min(X,Y) ((X) < (Y) ? (X) : (Y)) //finds minimum

int sillysort(int ,int []);
void sort_by_value(int,node []);//selection sort

int main(){

int n,i,sayac=1,cas_e;
int seq[1000];

while(sayac!=0){
printf("\nEnter the number of items to be sorted: (n)");
scanf("%d",&n);

printf("\nEnter different numbers:(positive and less than 1000)\n");

for(i=0;i<n;i++){
printf("\nEnter %d. number:",i+1);
scanf("%d",&seq[i]);
}

printf("\nCase %d: %d\n",sayac,sillysort(n,seq));
sayac++;

printf("\nEnter 0 to terminate the input or enter 1 to continue: ");
scanf("%d",&cas_e);

if(cas_e==0)//for another case or to close the program
sayac=0;
}
return 0;
}


void sort_by_value(int m,node temp[]){//this is a basic selection sort

int i, j, mini, tmp,tmp1;
for (i=0; i<m-1; i++)
{
mini = i;
for (j=i+1; j<m; j++)
{
if (temp[j].value < temp[mini].value)
mini = j;
}
tmp = temp[i].value;//swap part for value and place
tmp1=temp[i].place;
temp[i].value = temp[mini].value;
temp[i].place = temp[mini].place;
temp[mini].value = tmp;
temp[mini].place=tmp1;
}
}

//SILLY SORT FUNCTION
int sillysort(int m,int seq[]){
int cost=0,s,i;
node nodes[1000],temp[1000];

/*initialize*/
for(i=0;i<m;i++){
temp[i].value=seq[i];//temp[] is only for sorting by value and
temp[i].place=i; //assigning sorted places to nodes[]
}

sort_by_value(m,temp);

for(i=0;i<m;i++){
nodes[i].value=seq[i];
nodes[temp[i].place].place=i;//place of number is adjusted with respect to "temp" array
}//we know where the numbers have to place

s=temp[0].value;

/*compute*/
for(i=0;i<m;i++){
int j=nodes[i].place;//j holds place

if(j>=0 && j!=i){
int n=1,amin,sum;
amin=sum=nodes[i].value;//amin and sum hold value
while(j!=i){

int next=nodes[j].place;//next holds place,too

if(nodes[j].value < amin)
amin=nodes[j].value;

sum+=nodes[j].value;
n++;
nodes[j].place=-1;//we show that we controled it
j=next;
}//end while
cost+=min(sum + (n-2)*amin,sum + amin+(n+1)*s);//determine min cost
}//end if
}//end for
return cost;}

Hiç yorum yok:

Yorum Gönder