Cycle Sort Algorithm | Baeldung中文网

1. Introduction

Cycle Sort is an in-place, comparison-based sorting algorithm known for its efficiency in minimizing the number of writes. Unlike traditional sorting algorithms such as Quick Sort and Merge Sort, Cycle Sort rearranges elements with the fewest swaps possible. As a result, it’s especially efficient when write operations are expensive, e.g., in Electrically Erasable Programmable Read-Only Memory (EEPROM) or flash memory.

In this tutorial, we’ll explain how Cycle Sort works and provide a step-by-step pseudocode implementation of the algorithm. Then, we’ll explore its time and space complexities and discuss a use case where Cycle Sort is particularly useful. We’ll compare Cycle Sort to other sorting algorithms to put everything in context.

2. How Cycle Sort Works

Cycle Sort places each element in its correct position by counting the elements smaller than it. If an element is not in its correct position, we move it to the appropriate index, and this process continues until the entire array is sorted:

algorithm CycleSort(array, n):
    // INPUT    //    array = unsorted array (0-indexed)    //    n = array size
    // OUTPUT    //    Sorted array (in-place)

    for cycle_start from 0 to n - 2:
        item <- array[cycle_start]
        position <- cycle_start

        // Step 1: Find the correct position
        for i from cycle_start + 1 to n - 1:
            if array[i] < item:
                position <- position + 1

        // Skip if the item is already in the correct place
        if position = cycle_start:
            continue

        // Handle possible duplicates
        while item = array[position]:
            position <- position + 1        
        // Step 2: Place the item in the correct position
        // (swap means exchanging 'item' with array[position], not array[cycle_start])
        swap(array[position], item)

        // Step 3: Rotate the rest of the cycle
        while position != cycle_start do:
            position <- cycle_start
            for i from cycle_start + 1 to n - 1 do:
                if array[i] < item:
                    position <- position + 1
            while item = array[position]:
                position <- position + 1
            swap(array[position], item)

In Cycle Sort, a cycle refers to a sequence of swaps triggered when an element is incorrectly positioned. Each cycle forms a closed loop, moving displaced elements into their correct positions until the original starting element returns to its initial index.

2.1. Iteration of Cycle Sort

As we see, an iteration of Cycle Sort has three steps:

In step 1, we find the correct position of the current element by counting the elements smaller than the current item to determine exactly where it belongs in the final sorted array. If the position is already occupied by a duplicate, we move right until we hit a different element.

*In step 2, we place the item (which is held in a temporary variable) at the position we found in step 1 by exchanging it with the value at array[position].* The displaced value becomes the new item, continuing the cycle. This doesn’t involve directly swapping array[cycle_start] with array[position] unless the item has returned to that original position.

In step 3, we rotate through the rest of the cycle. Placing the item into its correct position might displace another value from the array. We resolve this by repeating the same procedure (finding correct positions, handling duplicates, and swapping) for each displaced item until the original item is returned to its starting position. This rotation ensures all elements in the cycle are properly placed with minimal data movements.

3. Example

Let’s walk through how Cycle Sort operates on the unsorted array [30, 10, 20, 50, 40]. For clarity, we show each iteration of the outer loop horizontally. We visually highlight, in blue, the elements of the array that require swaps and are moved during one cycle:

Cycle Sort Iterations and Cycles while sorting an array

Let’s now examine each iteration of Cycle Sort step-by-step for the unsorted array [30, 10, 20, 50, 40].

We begin with cycle_start = 0, where the current element is 30, held in the temporary variable item. In step 1, we find the correct position for this element. By counting how many elements are smaller than 30, we find two such elements, which tells us that 30 should be placed at index 2. Since there are no duplicates of 30 ahead in the array, we don’t need to adjust the target position further. In step 2, we place item 30 at index 2, displacing 20, which becomes the new item. In step 3, we continue the cycle. We place item 20 at index 1, displacing 10, which becomes the next item. Finally, we place item 10 at index 0, bringing the original value 30 back to its starting position and completing the cycle.

Next, cycle_start = 1, and the current element is 20. It is in its correct position, which also is the case with cycle_start = 2 and 30.

Proceeding to cycle_start = 3, we focus on the element 50. In step 1, we count the number of elements smaller than 50, which includes 10, 20, 30, and 40 — a total of four. This means 50 belongs at index 4. Again, there are no duplicates so, in step 2, we place item 50 at index 4, displacing 40, which becomes the new item. In step 3, we continue the cycle by placing item 40 at index 3, thus bringing 40 at the starting index and completing the cycle.

*With no more elements left to process, the cycle sorting is complete. The final sorted array is [10, 20, 30, 40, 50].*

4. Time and Space Complexity Analysis

From the time complexity standpoint, Cycle Sort is in the best, average, and worst cases. This is because the algorithm may compare every element with others to determine its correct position in the array.

Despite this quadratic runtime, Cycle Sort distinguishes itself by how few writes it performs. The algorithm is designed to perform a minimal number of write operations, specifically $\O(n)$ writes for elements. Here’s why:

Each element is moved at most once to its final sorted position.
For a cycle of length k (a sequence of elements that need to be rotated into place), the algorithm performs exactly k-1 writes to resolve the cycle.
Summing across all cycles in the array, the total number of swaps equals the number of elements minus the number of cycles. Since the total length of all cycles combined cannot exceed n, the total number of swaps is $\leq n$ . Therefore, the number of writes is .

In terms of space, Cycle Sort is highly efficient. It operates in place and doesn’t require any additional memory, resulting in an auxiliary space complexity of . This is particularly valuable in systems where memory overhead must be kept minimal.

5. When to Use Cycle Sort

Due to its quadratic time complexity, Cycle Sort isn’t meant to be a general-purpose sorting algorithm. However, it’s useful when write operations are expensive or limited. This makes it highly effective in embedded systems, firmware applications, and memory-constrained environments.

The algorithm performs best when sorting arrays containing distinct elements. In these cases, the cycle structure is simpler and more efficient to traverse. Conversely, Cycle Sort is less suitable for datasets with many duplicate values, as managing duplicates requires additional checks to avoid redundant cycles, potentially complicating the implementation and reducing its effectiveness.

Similarly, Cycle Sort becomes impractical when dealing with large datasets. The O(n^2) time complexity makes sorting hundreds of thousands or millions of elements inefficient. Faster algorithms like Merge Sort or Quick Sort are more appropriate in these cases.

6. Comparing Cycle Sort with Other Sorting Algorithms

Unlike Merge Sort, which guarantees a worst-case complexity of $O(n \log n)$ , or Quick Sort, which boasts a fast average time complexity of $O(n \log n)$ , Cycle Sort is O(n^2) in the worst and best cases. However, Cycle Sort significantly reduces the number of write operations (swaps):

Algorithm

Comparisons (Worst Case)

Swaps / Writes (Worst Case)

Total
(Comparisons + Swaps)

Cycle Sort

O(n^2)

O(n)

O(n^2)

Quick Sort

O(n^2)

Merge Sort

$O(n\log(n))$

Heap Sort

$O(n\log(n))$

Insertion Sort

O(n^2)

Most sorting algorithms, such as Insertion Sort, Heap Sort, or even Quick Sort, involve a significant number of write operations due to repeated swaps or recursive calls. In contrast, Cycle Sort writes each element directly into its final position with minimal redundancy.

However, Cycle Sort isn’t a stable sorting algorithm, which means that the relative order of equal elements may not be preserved. Stability is often desirable in sorting algorithms when handling structured data with multiple fields, so this limitation must also be considered.

7. Conclusion

In this article, we discussed Cycle Sort.

Cycle Sort is a memory-efficient sorting algorithm that shines in environments where minimizing write operations is crucial. Although its time complexity is quadratic, its write efficiency is optimal. It’s not suited for general-purpose usage but finds value in specialized hardware and constrained systems where we want the number of write operations (swaps) to be as low as possible.

Persistence

REST

Security

1. Introduction

2. How Cycle Sort Works

2.1. Iteration of Cycle Sort

3. Example

4. Time and Space Complexity Analysis

5. When to Use Cycle Sort

6. Comparing Cycle Sort with Other Sorting Algorithms

7. Conclusion