Sorting algorithms/Cycle sort: Difference between revisions
Content deleted Content added
No edit summary |
Add C |
||
Line 6:
* [http://www.youtube.com/watch?v=ZSJGf5Ngw18 Youtube] Visualization and audibilization of Cycle Sort algorithm.
=={{header|C}}==
{{trans|NetRexx}}
<lang C>
#include <stdio.h>
#include <stdlib.h>
int cycleSort(int * list, size_t l_len);
void show_array(int * array, size_t a_len);
/*
* Sort an array in place and return the number of writes.
*/
int cycleSort(int * list, size_t l_len)
{
int writes = 0;
/* Loop through the array to find cycles to rotate. */
for (int cycleStart = 0; cycleStart < l_len - 1; ++cycleStart)
{
int item = list[cycleStart];
int swap_tmp;
/* Find where to put the item. */
int pos = cycleStart;
for (int i = cycleStart + 1; i < l_len; ++i)
{
if (list[i] < item)
{
++pos;
}
}
/* If the item is already there, this is not a cycle. */
if (pos == cycleStart)
{
continue;
}
/* Otherwise, put the item there or right after any duplicates. */
while (item == list[pos])
{
++pos;
}
swap_tmp = list[pos];
list[pos] = item;
item = swap_tmp;
++writes;
/* Rotate the rest of the cycle. */
while (pos != cycleStart)
{
/* Find where to put the item. */
pos = cycleStart;
for (int i = cycleStart + 1; i < l_len; ++i)
{
if (list[i] < item)
{
++pos;
}
}
/* Put the item there or right after any duplicates. */
while (item == list[pos])
{
++pos;
}
swap_tmp = list[pos];
list[pos] = item;
item = swap_tmp;
++writes;
}
}
return writes;
}
int main(int argc, char ** argv)
{
int arr[] = { 0, 1, 2, 2, 2, 2, 1, 9, 3, 5, 5, 8, 4, 7, 0, 6, };
int arr_k = sizeof(arr) / sizeof(arr[0]);
int writes;
show_array(arr, arr_k);
writes = cycleSort(arr, arr_k);
show_array(arr, arr_k);
printf("writes: %d\n", writes);
return 0;
}
void show_array(int * array, size_t a_len)
{
for (int ix = 0; ix < a_len; ++ix)
{
printf("%d ", array[ix]);
}
putchar('\n');
return;
}
</lang>
{{out}}
<pre>
0 1 2 2 2 2 1 9 3 5 5 8 4 7 0 6
0 0 1 1 2 2 2 2 3 4 5 5 6 7 8 9
writes: 10
</pre>
=={{header|D}}==
|