Cycle Sort (requires minimum number of swaps)
#include<stdio.h>
int cycleSort(int *array,int size){
int writes = 0;
int cycleStart;
for (cycleStart=0; cycleStart<size - 1;cycleStart++)
{
int item = array[cycleStart];
int pos = cycleStart,i;
for (i=cycleStart + 1;i< size;i++)
if (array[i] < item)
pos += 1;
if (pos == cycleStart)
continue;
while (item == array[pos])
pos += 1;
array[pos] ^= item;
item ^= array[pos];
array[pos] ^= item;
writes += 1;
while (pos != cycleStart)
{
pos = cycleStart;
for (i=cycleStart + 1;i< size;i++)
if (array[i] < item)
pos += 1;
while (item == array[pos])
pos += 1;
array[pos]^= item;
item^=array[pos];
array[pos]^= item;
writes += 1;
}
}
return writes;
}
int main()
{
int a[]={4,3,7,1,9};
printf("%d\n",cycleSort(a,5));
int i=0;
for(i=0;i<5;i++)
printf("%d ",a[i]);
reutrn 0;
}
Comments
Post a Comment