Cycle Sort Algorithm

Cycle Sort is an in-place, comparison-based sorting algorithm that is optimal in terms of the number of writes to the original array. It is particularly useful when memory write operations are expensive because it minimizes the number of writes. Cycle Sort achieves this by determining the correct position of each element in the sorted array and only writing it once to its correct position.

How Cycle Sort Works:

1. Cycle Detection:
   • The algorithm traverses the array and determines cycles. A cycle is a sequence of elements that can be cyclically permuted to sort the array. Each cycle involves moving an element to its correct position, then moving the displaced element to its correct position, and so on until the cycle is complete.
2. Finding the Correct Position:
   • For each element in the array, Cycle Sort finds the correct position of the element by counting the number of elements smaller than it. This count gives the position where the element should be placed in the sorted array.
3. Placing Elements:
   • Once the correct position of an element is found, it is placed there. If the position already contains the correct element, no swap is needed. Otherwise, the displaced element is moved to its correct position, continuing this process until all elements in the cycle are correctly placed.
4. Repeat for All Cycles:
   • The process is repeated for all cycles in the array. The algorithm ensures that each element is written exactly once to its correct position, minimizing the number of writes.

Characteristics of Cycle Sort:

• Time Complexity:
  • Best Case: O(n²) – Cycle Sort performs a series of passes over the array, each of which involves counting the number of elements and performing swaps.
  • Average Case: O(n²)
  • Worst Case: O(n²)
  • Although the time complexity is O(n²) in all cases, Cycle Sort can be more efficient in terms of the number of writes.
• Space Complexity:
  • Cycle Sort is an in-place algorithm, requiring only a constant amount of additional memory space, O(1).
• Stability:
  • Cycle Sort is not a stable sorting algorithm. Stability refers to preserving the relative order of records with equal keys.
• Usage:
  • Cycle Sort is particularly useful when minimizing the number of write operations is important. This could be relevant in systems where write operations are expensive, such as certain types of memory devices or when dealing with large datasets where write operations are costly.

Code Example

def cycle_sort(arr):
    writes = 0  # To count the number of writes

    # Loop through the array to find cycles to rotate
    for cycle_start in range(0, len(arr) - 1):
        item = arr[cycle_start]

        # Find where to put the item
        pos = cycle_start
        for i in range(cycle_start + 1, len(arr)):
            if arr[i] < item:
                pos += 1

        # If the item is already in the correct position
        if pos == cycle_start:
            continue

        # Ignore all duplicate elements
        while item == arr[pos]:
            pos += 1

        # Put the item to its right position
        if pos != cycle_start:
            arr[pos], item = item, arr[pos]
            writes += 1

        # Rotate the rest of the cycle
        while pos != cycle_start:
            pos = cycle_start
            for i in range(cycle_start + 1, len(arr)):
                if arr[i] < item:
                    pos += 1

            while item == arr[pos]:
                pos += 1

            if item != arr[pos]:
                arr[pos], item = item, arr[pos]
                writes += 1

    return arr, writes

# Example usage
arr = [4, 3, 2, 1]
sorted_arr, num_writes = cycle_sort(arr)
print("Sorted array is:", sorted_arr)
print("

Code Explanation

Function Definition

def cycle_sort(arr):

• The function cycle_sort is defined to take a single list arr as its parameter.

Initialize Write Counter

    writes = 0  # To count the number of writes

• The variable writes is initialized to count the number of write operations performed.

Loop to Find Cycles

    for cycle_start in range(0, len(arr) - 1):
        item = arr[cycle_start]

• The outer loop iterates over the array to find cycles, starting from the first element and ending at the second-to-last element.
• The variable item holds the value of the current element at cycle_start.

Find the Correct Position

        pos = cycle_start
        for i in range(cycle_start + 1, len(arr)):
            if arr[i] < item:
                pos += 1

• The inner loop finds the correct position (pos) for item by counting the number of elements that are less than item.

Ignore Already Positioned Elements

        if pos == cycle_start:
            continue

• If pos is equal to cycle_start, it means item is already in the correct position, so we continue to the next cycle.

Ignore Duplicates

        while item == arr[pos]:
            pos += 1

• This loop ignores duplicate elements by incrementing pos until it finds a unique position for item.

Put the Item in its Correct Position

        if pos != cycle_start:
            arr[pos], item = item, arr[pos]
            writes += 1

• The current element item is placed in its correct position, and the displaced element becomes the new item.
• The write counter writes is incremented.

Rotate the Rest of the Cycle

        while pos != cycle_start:
            pos = cycle_start
            for i in range(cycle_start + 1, len(arr)):
                if arr[i] < item:
                    pos += 1

            while item == arr[pos]:
                pos += 1

            if item != arr[pos]:
                arr[pos], item = item, arr[pos]
                writes += 1

• This loop continues to rotate the rest of the cycle until all elements are placed in their correct positions.
• The write counter writes is incremented for each write operation.

Return Statement

    return arr, writes

• The sorted array arr and the number of write operations writes are returned.

Example Usage

arr = [4, 3, 2, 1]
sorted_arr, num_writes = cycle_sort(arr)
print("Sorted array is:", sorted_arr)
print("Number of writes:", num_writes)

• An example list arr is sorted using the cycle_sort function, and the sorted list along with the number of write operations is printed.

Output

Sorted array is: [1, 2, 3, 4]
Number of writes: 4

• The final output is the sorted array in ascending order and the total number of write operations performed.