Silly Sort

Silly Sort probleminin çözümünü ve programını paylaştım.
Soruya ulaşmak için tıklayınız. 2002 Problem H, Silly Sort

Algoritma Açıklaması:
Amaç sıralama yaparken minimum maliyet ile sıralamak.
Bu yüzden verilen sayılardan en küçük olanı ile yer değiştirme işlemini yapmak minimum olacaktır. Ayrıca verilen sayıların ilk adımda ve her adımda sıralı halde olacakları yerde olup olmadıkları önemlidir.

[8,1,2,4] -(9)- [1,8,2,4] -(10)- [1,2,8,4] -(12)- [1,2,4,8] (31)

[8,1,2,4] -(3)- [8,2,1,4] -(5)- [8,2,4,1] -(9)- [1,2,4,8] (17)

kaynak: 1

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;}