Cycle sort is an in-place sorting Algorithm, unstable sorting algorithm, a comparison sort that is theoretically optimal in terms of the total number of writes to the original array. Cycle sort is the most efficient in terms of memory writes. It reduces the amount of memory writes required to sort. If a value is already in the proper location, it is written zero times; otherwise, it is written once to the correct spot.
If a sorting algorithm is said to be "unstable", this means that for any items that rank the same, the order of the tied members is not guaranteed to stay the same with successive sorts of that collection. For a 'stable' sort, the tied entries will always end up in the same order when sorted. Selection sort, Heap sort, Shell sort, Cycle sort and Quicksort algorithm are not stable. Some Sorting Algorithms are stable by nature, such as Bubble sort, Insertion sort, Merge sort, Count sort etc.
Minimizing the number of writes is useful when making writing to some huge data set is very expensive, such as with EEPROMs which stands for electrically erasable programmable read-only memory and is a type of non-volatile memory used in computers, integrated into microcontrollers for smart cards and remote keyless systems, and other electronic devices to store relatively small amounts of data by allowing individual bytes to be erased and reprogrammed or Flash memory, where each write reduces the lifespan of the memory. Cycle sort is useful when the array is stored in EEPROM or FLASH.
def cycleSort(array):
writes = 0
# Loop through the array to find cycles to rotate.
for cycleStart in range(0, len(array) - 1):
item = array[cycleStart]
# Find where to put the item.
pos = cycleStart
for i in range(cycleStart + 1, len(array)):
if array[i] < item:
pos += 1
# If the item is already there, this is not a cycle.
if pos == cycleStart:
continue
# Otherwise, put the item there or right after any duplicates.
while item == array[pos]:
pos += 1
array[pos], item = item, array[pos]
writes += 1
# Rotate the rest of the cycle.
while pos != cycleStart:
# Find where to put the item.
pos = cycleStart
for i in range(cycleStart + 1, len(array)):
if array[i] < item:
pos += 1
# Put the item there or right after any duplicates.
while item == array[pos]:
pos += 1
array[pos], item = item, array[pos]
writes += 1
return writes
Time Complexity : O(n2)
This method is only applicable when given array values or elements are in range of 1 to N or 0 to N. In this method, we do not need to rotate the array.
LeetCode 268 - Missing Number [easy]
Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.
Solution 1:
class Solution:
def missingNumber(self, nums: List[int]) -> int:
start = 0
while start < len(nums):
num = nums[start]
if num < len(nums) and num != start:
nums[start], nums[num] = nums[num], nums[start]
else:
start += 1
for i in range(len(nums)):
if nums[i] != i:
return i
return len(nums)
Time Complexity: O(N) + O(N - 1) which is asymptotically equivalent to O(N)
Space Complexity: O(1), algorithm runs in constant space.
This pattern is quite useful when dealing with numbers in a given range and asking to find the duplicates/missing ones etc.
Solution 2:
class Solution:
def missingNumber(self, nums: List[int]) -> int:
res = len(nums)
for i in range(len(nums)):
res += (i - nums[i])
return res
Solution 3:
class Solution:
def missingNumber(self, nums: List[int]) -> int:
target_sum = len(nums) * (len(nums) + 1) // 2
cur_sum = 0
for n in nums:
cur_sum += n
return target_sum - cur_sum
LeetCode 41. First Missing Positive
Given an unsorted integer array nums, return the smallest missing positive integer.
You must implement an algorithm that runs in O(n) time and uses constant extra space.
Example 1: Input: nums = [1,2,0] Output: 3
Explanation: The numbers in the range [1,2] are all in the array.
Hint 1: Think about how you would solve the problem in non-constant space. Can you apply that logic to the existing space?
Hint 2: We don't care about duplicates or non-positive integers
Hint 3: Remember that O(2n) = O(n)
Solution 1:
class Solution:
def firstMissingPositive(self, nums: [int]) -> int:
for i in range(len(nums)):
while nums[i]> 0 and nums[i] < len(nums) and nums[i] - 1 != i and nums[i] != nums[nums[i]-1]:
nums[nums[i]-1], nums[i] = nums[i], nums[nums[i]-1]
for i in range(len(nums)):
if i + 1 != nums[i]:
return i + 1
return len(nums) + 1
Solution 2:
class Solution:
def firstMissingPositive(self, nums: List[int]) -> int:
s = set(nums)
maxv = max(nums)
if maxv < 0:
return 1
for i in range(1,maxv):
if i not in s:
return i
return maxv + 1
