#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