Home > Blockchain >  Sort List with duplicates based on related list
Sort List with duplicates based on related list

Time:08-11

Shortened the scenario for brevity.

I have three arrays

A1 = [A,B,C,D,E,F]
A2 = [20,30,45,60,20,10]
A3 = [30,30,15,20,40,60]

where there is a relationship between the elements at i-th position between the three arrays..

for eg A1[0] is related to A2[0] and also A3[0] and so on ...

I want to sort the three arrays BASED ON THE A2 (in ascending order).

so after sorting, the arrays become

A1 = [F,A,E,B,C,D]
A2 = [10,20,20,30,45,60]
A3 = [60,30,40,30,15,20]

One thing I am not able to figure out is while sorting, if there is a duplicate record in A2 (20 in this case), then the sort should take the value in A2 which has a lesser corresponding value in A3.. Thats is why A should come before E in the final A1 list.

Any help would be appreciated.

As of now, I am trying to do this using quick sort, Please find my code below

    def partition(self, A1, A2, A3, low, high):
        pivot = A2[high]
        i = low - 1
        for j in range(low, high):
            if A2[j] <= pivot:
                i = i   1
                (A2[i], A2[j]) = (A2[j], A2[i])
                (A3[i], A3[j]) = (A3[j], A3[i])
                (A1[i], A1[j]) = (A1[j], A1[i])
        (A2[i   1], A2[high]) = (A2[high], A2[i   1])
        (A3[i   1], A3[high]) = (A3[high], A3[i   1])
        (A1[i   1], A1[high]) = (A1[high], A1[i   1])
        return i   1

    def quickSort(self, A1, A2, A3, low, high):
        if low < high:
            pi = self.partition(A1, A2, A3, low, high)
            self.quickSort(A1, A2, A3, low, pi - 1)
            self.quickSort(A1, A2, A3, pi   1, high)

Please note: I have to do this without using inbuilt functions

CodePudding user response:

A2, A3, A1 =  map(list, zip(*sorted(zip(A2, A3, A1))))

And since you need it without built-in functions:

A1 = ['A', 'B', 'C', 'D', 'E', 'F']
A2 = [20, 30, 45, 60, 20, 10]
A3 = [30, 30, 15, 20, 40, 60]

def myzip(*iterables):
    myiters = [myiter(it) for it in iterables]
    try:
        while True:
            yield tuple(mynext(it) for it in myiters)
    except RuntimeError:
        pass

def mymap(func, *iterables):
    myiters = [myiter(it) for it in iterables]
    try:
        while True:
            yield func(*(mynext(it) for it in myiters))
    except RuntimeError:
        pass  

def mylist(*args):
    return [*args]

def myiter(iterable):
    for item in iterable:
        yield item
    raise StopIteration()

def mynext(it):
    return it.__next__()

def _partition(l, r, arr):
    pivot, ptr = arr[r], l
    for i in range(l, r):
        if arr[i] <= pivot:
            arr[i], arr[ptr] = arr[ptr], arr[i]
            ptr  = 1
    arr[ptr], arr[r] = arr[r], arr[ptr]
    return ptr

def _quicksort(l, r, arr):
    if len(arr) == 1: 
        return arr
    if l < r:
        pi = _partition(l, r, arr)
        _quicksort(l, pi-1, arr) 
        _quicksort(pi 1, r, arr) 
    return arr

def quicksort(arr):
    arr = list(arr)
    return _quicksort(0, len(arr)-1, arr)

A2, A3, A1 =  mymap(mylist, myzip(*quicksort(myzip(A2, A3, A1))))

print(A1, A2, A3, sep='\n')

Resulting in

['F', 'A', 'E', 'B', 'C', 'D']
[10, 20, 20, 30, 45, 60]
[60, 30, 40, 30, 15, 20]

Note: I took some shortcuts in my reimplementation of the built-ins. Their exception handling is less than ideal, some features are missing, and the behavior isn't exactly the same, but they work for their intended purposes.

Note 2: range() and print() were not reimplemented.

  • Related