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

Popular Posts