Python Program for Cycle Sort

Python Program for Cycle Sort

Cycle Sort is an in-place and non-comparison-based sorting algorithm. Its primary use is to minimize the number of writes to the input when it's necessary, such as with flash memory. Cycle Sort is optimal in terms of the number of writes to the input, as it minimizes them.

The idea of Cycle Sort is to cycle the elements into their correct positions until the entire array is sorted. One cycle moves an element to its correct place and another element to a different place, and this process continues until an element is moved to the original position.

Algorithm:

  1. Consider an element, find its correct position (i.e., count the number of smaller elements) and swap it with the element already present at that position.
  2. Continue this process for the element swapped out in the previous step, and so on, until the first element is placed in its correct position.

Python Program for Cycle Sort:

def cycle_sort(arr):
    writes = 0

    # Traverse the array to place the elements in their correct position
    for cycle_start in range(0, len(arr) - 1):
        item = arr[cycle_start]

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

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

        # Otherwise, put the element to the correct position
        while item == arr[pos]:
            pos += 1
        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
            arr[pos], item = item, arr[pos]
            writes += 1

    return writes

# Test the function
arr = [5, 2, 9, 1, 5, 6]
number_of_writes = cycle_sort(arr)
print("Sorted array:", arr)
print("Number of writes:", number_of_writes)

Time Complexity:

  • Best Case: O(n2)
  • Average Case: O(n2)
  • Worst Case: O(n2)

Space Complexity:

  • O(1)

Advantages:

  • Minimizes the number of writes.
  • In-place sorting.

Disadvantages:

  • Not efficient for large datasets due to its O(n2) time complexity.

Cycle Sort is not used for sorting if write operations are cheap. It can be useful in situations where write operations are costly, like in flash memory.

More Tags

text-alignment asp.net-web-api2 devops jsr310 chai firebase-cloud-messaging vue-directives jquery android-context selection

More Programming Guides

Other Guides

More Programming Examples