| 2 | |
| 3 | |
| 4 | def cycleSort(array): |
| 5 | writes = 0 |
| 6 | |
| 7 | # Loop through the array to find cycles to rotate. |
| 8 | for cycleStart in range(0, len(array) - 1): |
| 9 | item = array[cycleStart] |
| 10 | |
| 11 | # Find where to put the item. |
| 12 | pos = cycleStart |
| 13 | for i in range(cycleStart + 1, len(array)): |
| 14 | if array[i] < item: |
| 15 | pos += 1 |
| 16 | |
| 17 | # If the item is already there, this is not a cycle. |
| 18 | if pos == cycleStart: |
| 19 | continue |
| 20 | |
| 21 | # Otherwise, put the item there or right after any duplicates. |
| 22 | while item == array[pos]: |
| 23 | pos += 1 |
| 24 | array[pos], item = item, array[pos] |
| 25 | writes += 1 |
| 26 | |
| 27 | # Rotate the rest of the cycle. |
| 28 | while pos != cycleStart: |
| 29 | # Find where to put the item. |
| 30 | pos = cycleStart |
| 31 | for i in range(cycleStart + 1, len(array)): |
| 32 | if array[i] < item: |
| 33 | pos += 1 |
| 34 | |
| 35 | # Put the item there or right after any duplicates. |
| 36 | while item == array[pos]: |
| 37 | pos += 1 |
| 38 | array[pos], item = item, array[pos] |
| 39 | writes += 1 |
| 40 | |
| 41 | return writes |
| 42 | |
| 43 | |
| 44 | # driver code |