Get this book -> Problems on Array: For Interviews and Competitive Programming

Reading time: 20 minutes | Coding time: 10 minutes

**Cycle sort** is a comparison based sorting algorithm which forces array to be factored into the number of cycles where each of them can be rotated to produce a sorted array.

It is an **in-place** and **unstable** sorting algorithm.

It is optimal in terms of number of memory writes. It minimizes the number of memory writes to sort. Each value is either written zero times, if itβs already in its correct position, or written one time to its correct position.

It is based on the idea that array to be sorted can be divided into **cycles**. Cycles can be visualized as a **graph**. We have **n** nodes and an **edge** directed from node i to node j if the element at *i-th index* must be present at **j-th index** in the sorted array.

### Algorithm

Consider an array of n distinct elements.

An element a is given, index of a can be calculated by counting the number of elements that are smaller than a.

- If the element is found to be at its correct position, simply leave it as it is.
- Otherwise, find the correct position of a by counting the total number of elements that are less than a. where it must be present in the sorted array. The other element b which is replaced is to be moved to its correct position. This process continues until we got an element at the original position of a.

### Example

Example 1: Assume the Unsorted input array is: **[3, 2, 1, 4, 6, 5]**.

Based on above algorithm we will illustrate the process which constitutes a cycle. We one by one consider all cycles. We first consider the cycle that includes first element. We find correct position of first element, place it at its correct position, say j. We consider old value of arr[j] and find its correct position, we keep doing this till all elements of current cycle are placed at correct position, i.e., we do not come back to cycle starting point.

## Pseudocode

```
Begin
for start := 0 to n β 2 do
key := array[start]
location := start
for i := start + 1 to n-1 do
if array[i] < key then
location:=location +1
done
if location = start then
ignore lower part, go for next iteration
while key = array[location] do
location := location +1
done
if location β start then
swap array[location] with key
while location β start do
location := start
for i := start + 1 to n-1 do
if array[i] < key then
location:=location +1
done
while key = array[location]
location := location +1
if key β array[location]
swap array[location] and key
done
done
End
```

### Complexity Analysis

Best case time complexity:**O(n^2)**

Average case time complexity:**O(n^2)**

Worst case time complexity:**O(n^2)**

Space complexity:**O(1)**

This sorting algorithm is best suited for situations where memory write or swap operations are costly.

Here, in this comparison based sorting algorithm the time complexity will remain same for all case (i.e. Best, Average & worst cases) that is **O(n^2)** as in each iteration, we have to traverse the entire subarray, starting from current position, to count the no. of all the elements that are less than the current element. So, whether or not the array is already sorted or not has no consequence on the running time, nor does it provide an opportunity for optimization and the algorithm must run in quadratic time.

Also, This sorting algorithm is inplace so it does not use any extra memory to sort the array and so that's why it's Space Complexity is constant

### Implementation

- C
- Java

## C

```
#include<stdio.h>
void sort(int a[], int n)
{
int writes = 0,start,element,pos,temp,i;
for (start = 0; start <= n - 2; start++) {
element = a[start];
pos = start;
for (i = start + 1; i < n; i++)
if (a[i] < element)
pos++;
if (pos == start)
continue;
while (element == a[pos])
pos += 1;
if (pos != start) {
temp = element;
element = a[pos];
a[pos] = temp;
writes++;
}
while (pos != start) {
pos = start;
for (i = start + 1; i < n; i++)
if (a[i] < element)
pos += 1;
while (element == a[pos])
pos += 1;
if (element != a[pos]) {
temp = element;
element = a[pos];
a[pos] = temp;
writes++;
}
}
}
}
int main()
{
int a[] = {1, 9, 2, 4, 2, 10, 45, 3, 2};
int n = sizeof(a) / sizeof(a[0]),i;
sort(a, n);
printf("After sort, array : ");
for (i = 0; i < n; i++)
printf("%d ",a[i]);
return 0;
}
```

## Java

`import java.io.*; import java.util.*; public class CycleSort { static void sort(int a[], int n) { int writes = 0,start,element,pos,temp,i;`

`for (start = 0; start <= n - 2; start++) { element = a[start]; pos = start; for (i = start + 1; i < n; i++) if (a[i] < element) pos++; if (pos == start) continue; while (element == a[pos]) pos += 1; if (pos != start) { temp = element; element = a[pos]; a[pos] = temp; writes++; } while (pos != start) { pos = start; for (i = start + 1; i < n; i++) if (a[i] < element) pos += 1; while (element == a[pos]) pos += 1; if (element != a[pos]) { temp = element; element = a[pos]; a[pos] = temp; writes++; } } }`

`}`

public static void main(String[] args)

{

int a[] = { 1, 9, 2, 4, 2, 10, 45, 3, 2 };

int n = a.length,i;

sort(a, n);

System.out.println("After sort, array : ");

for (i = 0; i < n; i++)

System.out.println(a[i]);

}

}

### Advantages

- Cycle Sort offers the advantage of little or no additional storage.
- It is an in-place sorting Algorithm .
- It is optimal in terms of number of memory writes. It makes minimum number of writes to the memory and hence efficient when array is stored in EEPROM or Flash. Unlike nearly every other sort (Quick , insertion , merge sort), items are never written elsewhere in the array simply to push them out of the way of the action. Each value is either written
**zero**times, if it's already in its correct position, or written**one**time to its correct position.This matches the minimal number of overwrites required for a completed in-place sort.

### Disadvantages

- It is not mostly used because it has more time complexity (i.e O(n^2)) than any other comparison sorting algorithm.

### Application

- This sorting algorithm is best suited for situations where memory write or swap operations are costly.