Question

In Python please!

Given an unsorted list (ls) of values (you do not know the datatype). Only two values appear in the list but they appear many times and are not sorted. Without using any significant additional space (i.e. you cannot copy the list) sort the elements in linear time going through the list only once. For example:

Given the list [‘a’, ‘a’, ‘b’, ‘a’, ‘a’, ‘b’, ‘b’, ‘a’] after the function, the list is [‘a’, ‘a’, ‘a’, ‘a’, ‘a’, ‘b’, ‘b’, ‘b’] Given the list [1, 0, 1, 0, 1, 1] after the function, the list is [0,0,1,1,1,1]

Answer 1

Python Code:

#function to sort list in 1 traverse:
def sort(arr, size): 
    # Initializing left and right index 
    left, right = 0, size-1
    #taking 1 value in x to distinguish between 2 values in list
    x=arr[0]
      
    while left < right: 
        # Increment left index while we see 0 at left 
        while arr[left] == x and left < right: 
            left += 1
  
        # Decrement right index while we see 1 at right 
        while arr[right] != x and left < right: 
            right -= 1
  
        # If left is less than right, then there is no x at left 
        # and x at right. Exchange arr[left] and arr[right] 
        if left < right: 
            temp=arr[left]
            arr[left] = arr[right]
            arr[right] = temp
            left += 1
            right -= 1
  
    return arr 

#list arr initialized
arr = ['a','a','b','a','a','b','a','b','a','b']
#length of list arr
arr_size = len(arr) 

#fuction call and print returned value
print(sort(arr, arr_size)) 

OUTPUT: