| 2 | using namespace std; |
| 3 | |
| 4 | void cycleSort(int arr[], int n) |
| 5 | { |
| 6 | //All required variables initilized |
| 7 | int counter = 0,start,elem,pos,temp,i; |
| 8 | |
| 9 | //Array elems are traversed to ensure that they are in correct positions |
| 10 | //elem represents the initial point |
| 11 | for (start = 0; start <= n - 2; start++) { |
| 12 | elem = arr[start]; |
| 13 | |
| 14 | //Smaller array elements to be shifted to the elem varaible's right |
| 15 | //to maintain the sorted order of the final array |
| 16 | pos = start; |
| 17 | for (i = start + 1; i < n; i++) |
| 18 | if (arr[i] < elem) |
| 19 | pos++; |
| 20 | if (pos == start) |
| 21 | continue; |
| 22 | |
| 23 | //Ignore duplicate elements |
| 24 | while (elem == arr[pos]) |
| 25 | pos += 1; |
| 26 | //Element swapped to keep it at right position |
| 27 | if (pos != start) { |
| 28 | temp = elem; |
| 29 | elem = arr[pos]; |
| 30 | arr[pos] = temp; |
| 31 | counter++; |
| 32 | } |
| 33 | while (pos != start) { |
| 34 | pos = start; |
| 35 | for (i = start + 1; i < n; i++) |
| 36 | if (arr[i] < elem) |
| 37 | pos += 1; |
| 38 | while (elem == arr[pos]) |
| 39 | pos += 1; |
| 40 | if (elem != arr[pos]) { |
| 41 | temp = elem; |
| 42 | elem = arr[pos]; |
| 43 | arr[pos] = temp; |
| 44 | counter++; |
| 45 | } |
| 46 | } |
| 47 | } |
| 48 | } |
| 49 | |
| 50 | //Driver method |
| 51 | int main() |