0

I want to implement this without using the sorted function (perhaps by using a priority queue):

nums = [2,3,1,3,2]

dic=collections.Counter(nums)

sorted_dic= dict(sorted(dic.items(),key=lambda x: x[1]))

I have written a custom sort function to sort array/dictionary in ascending/descending order.

def bubble_sort(arr):   #You can use any sort - for the sake of simplicity I have used bubble sort
    for i in range(len(arr)-1):
        for j in range(len(arr)-1-i):
            if arr[j] > arr[j + 1]: 
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

def my_custom_sort(obj,key=None,reverse=False):  
    if type(obj)==dict:
        if key==0:
            arr = list(map(lambda x:x[0], obj.items())) #fetch the list of keys
        else:
            dic = {y:x for x,y in obj.items()}  #reverse the key value pairs, so that it is easy to match key/values
            arr = list(map(lambda x:x[0], dic.items()))  
    else:
        arr=obj
    
    sorted_arr = bubble_sort(arr)
    if reverse: sorted_arr =sorted_arr[::-1]
           
    if type(obj)==dict:
        if key==0:
            res = [(key,obj[key]) for key in sorted_arr] 
            return res
        else:
            return [(dic[key],key) for key in sorted_arr] 
            return res
    else:
        return sorted_arr

arr=[4,2,6,7,1]
dic={3:1,2:4,1:0,0:8}
print(my_custom_sort(arr))    #sort array in increasing order
print(my_custom_sort(arr,reverse=True))   #sort array in decreasing order
print(my_custom_sort(dic,key=0))  #sort dictionary by key in inreasing order
print(my_custom_sort(dic,key=1))  #sort dictionary by values in increasing order
print(my_custom_sort(dic,key=0,reverse=True))  #sort dictionary by key in  decreasing order
print(my_custom_sort(dic,key=1,reverse=True))  #sort dictionary by values in  decreasing order

Output:
[1, 2, 4, 6, 7]
[7, 6, 4, 2, 1]
[(0, 8), (1, 0), (2, 4), (3, 1)]
[(1, 0), (3, 1), (2, 4), (0, 8)]
[(3, 1), (2, 4), (1, 0), (0, 8)]
[(0, 8), (2, 4), (3, 1), (1, 0)]

I hope this is helpful for someone who wants to implement his own custom sort function (if asked in the interview)

Sushil K
  • 11
  • 1
  • 4
    Reimplement your own `sorted()` function and then do `dict(sorted(dic.items(), key=lambda x: x[1]))`. So your question is just "how do I implement sorting in Python?" – Boris Verkhovskiy Jan 12 '21 at 16:54
  • 5
    Why are you against using `sorted()`? – Boris Verkhovskiy Jan 12 '21 at 16:57
  • 1
    What is your criteria for rejecting ``sorted``? How about using ``list.sort``? – MisterMiyagi Jan 12 '21 at 17:01
  • 1
    You could use `OrderedDict`, then add in the items in the order you want – OneCricketeer Jan 12 '21 at 17:06
  • 1
    Does this answer your question? [Python lambda function to sort list according to dictionary](https://stackoverflow.com/questions/40428273/python-lambda-function-to-sort-list-according-to-dictionary) – demokritos Jan 12 '21 at 17:17
  • 1
    @OneCricketeer: You don't need to use an `OrderedDict`, dictionaries have maintained insertion order since Python 3.7. – martineau Jan 12 '21 at 17:47
  • 1
    You can use the `bisect` module, See [How to use bisect.insort_left with a key?](https://stackoverflow.com/questions/27672494/how-to-use-bisect-insort-left-with-a-key) for an example and more information. – martineau Jan 12 '21 at 17:52
  • 1
    @martineau True, but Python version wasn't stated. – OneCricketeer Jan 12 '21 at 18:14
  • 1
    I wanted to understand how python internally sorts the value in the dictionary based on frequency. Sorting a dictionary is straight forward (similar to sort functionality), but I couldn't find anywhere on the internet to sort based on the specific key condition. In this case, sorting based on the frequency. – Sushil K Jan 13 '21 at 12:42
  • 2
    If you want to "understand how python internally sorts", you should probably look at the source code of Python's sorting, not at *some* sorting implementation provided on the internet. – MisterMiyagi Jan 13 '21 at 13:16
  • If you really want to go crazy, create an augmented bst with a reference to the dictionary key added to the tree nodes and the value the BST value. – Union find Feb 23 '21 at 09:16
  • Don't add solutions inside the question. You are free to answer your own question – Tomerikoo Feb 23 '21 at 09:28
  • Does this answer your question? [sort a dictionary without using built-in functions](https://stackoverflow.com/questions/27085960/sort-a-dictionary-without-using-built-in-functions) – Tomerikoo Feb 23 '21 at 09:37

0 Answers0