Sorting algorithms/Cycle sort: Difference between revisions

Content added Content deleted

Inline

@@ Line 6: / 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>
+1 2 2 2 2 1 9 3 5 5 8 4 7 0 6
+0 1 1 2 2 2 2 3 4 5 5 6 7 8 9
+writes: 10
+</pre>
 =={{header|D}}==