1 month, 1 week

Coding Patterns: Cyclic Sort




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. 

  • It is based on the concept of dividing a sortable array into cycles. A graph can be used to represent a cycle.
  • We first consider the cycle that includes the first element. We find the correct position of the first element, and place it at its correct position, say j. We consider the old value of arr[j] and find its correct position, we keep doing this till all elements of current cycle are placed at the correct position, i.e., we don’t come back to cycle starting point.

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)                                        

  • Worst Case : O(n2)                                          
  • Average Case: O(n2)                                                       
  • Best Case : 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 ComplexityO(N) + O(N - 1) which is asymptotically equivalent to O(N)

Space ComplexityO(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                                                         

 


Responses(0)







Related