Daily Archives: February 26, 2015

The characteristic of circle sort is that it takes least swap operation than any other sorting algorithm.
Given an integer array a[], it loops the element start_pos from a[0] to a[length-2]. Each time, find the right position(next_pos) for a[start_pos]. And we should still find the position for a[next_pos], and update the next_pos on and on, until next_pos goes to start_pos. The above operation happens in certain elements, which one replace another one like a circle.

1. public static void circleSort(int[] a) {
2.         if (a == null || a.length == 1) {
3.             return;
4.         }
5.         for (int start_pos = 0; start_pos < a.length – 1; start_pos++) {
6.             int next_pos = start_pos;
7.             for (int i = start_pos + 1; i < a.length; i++) {
8.                 if (a[start_pos] > a[i]) {
9.                     next_pos++;
10.                 }
11.             }
12.             if (next_pos == start_pos) {
13.                 continue;
14.             }
15.             while (a[next_pos] == a[start_pos]) {
16.                 next_pos++;
17.             }
18.             while (true) {
19.                 int tmp_ele = a[next_pos];
20.                 a[next_pos] = a[start_pos];
21.                 next_pos = start_pos;
22.                 for (int i = start_pos + 1; i < a.length; i++) {
23.                     if (tmp_ele > a[i]) {
24.                         next_pos++;
25.                     }
26.                 }
27.                 if (next_pos == start_pos) {
28.                     a[start_pos] = tmp_ele;
29.                     break;
30.                 }
31.                 while (a[next_pos] == a[start_pos]) {
32.                     next_pos++;
33.                 }
34.             }
35.         }
36.     }