CODEWITHSUNDEEP
sortingquicksort
OzB
OzB

Reputation: 2221

Quick-Sort two N-sized, same values array, by comparing one to another

I have two arrays, A and B, with the same values (so both of them in size N) but they're ordered differently. I need to sort both arrays so A[i]==B[i] for every i. The issue is that I can't compare A to itself and B to itself. The sorting must be by comparing A[i] to values in B and B[i] to values in A.

I tried this version of randomized quick-sort (updated code that reflect using leftmark instead leftmark + 1):

import random
import sys

def swap(a, l, r):
    a[l], a[r] = a[r], a[l]


def partition(arr, left, right, pivot):
    leftmark = left
    rightmark = right

    while 1:
        while leftmark <= rightmark and arr[leftmark] <= pivot:
            leftmark = leftmark + 1

        while arr[rightmark] >= pivot and rightmark >= leftmark:
            rightmark = rightmark -1

        if rightmark < leftmark:
            break
        temp = arr[leftmark]
        arr[leftmark] = arr[rightmark]
        arr[rightmark] = temp

    temp = arr[left]
    arr[left] = arr[rightmark]
    arr[rightmark] = temp

    return rightmark

def sort_arrays(arr1, arr2, low1, high1, low2, high2):
    if low1 < high1:
        # v = low2
        # pivotB = partition(arr2, low2, high2, arr1[v])
        # pivotA = partition(arr1, low1, high1, arr1[low1])
        # pivotB=0

        a1 = arr1[low1]
        pivotB = partition(arr2, low2, high2, a1)
        pivotA = partition(arr1, low1, high1, arr2[pivotB])

        sort_arrays(arr1, arr2, low1, pivotA - 1, low2, pivotB - 1)
        sort_arrays(arr1, arr2, pivotA + 1, high1, pivotB + 1, high2)

arr1 = [4, 2, 1, 5, 6, 3]
arr2 = [2, 3, 1, 4, 5, 6]

sort_arrays(arr1, arr2, 0, len(arr1) - 1, 0, len(arr2) - 1)
print('arr1', arr1)
print('arr2', arr2)

Unfortunately, I don't get it right and can't find out what am I missing.

Upvotes: 1

Views: 204

Answers (3)

rcgldr
rcgldr

Reputation: 28826

The questions partition code is a variation of Hoare partition scheme, which separates an array into elements <= pivot, and elements => pivot. Elements == pivot can be scattered and end up anywhere, so leftmark or rightmark may or may not point to an element == pivot. Swapping arr[left] is an issue, since the first pivot is arr2[low2], and arr1[low1] may not be equal to the pivot.

What is needed is a partition function that returns an index to an element equal to the pivot given as input, in which case pivot out will equal pivot in, so A and B will be partitioned using the same pivot value. If A and B can have duplicate values, then a 3 way quicksort {values < pivot, values == pivot, values > pivot} is probably needed (to handle the case when multiple values == pivot).

Upvotes: 1

mangusta
mangusta

Reputation: 3544

After you have set your pivot value as a1 = arr1[low1], calling partition(arr2, low2, high2, a1) is simply wrong because a1 is not necessarily the same with arr2[low2] and partitioning function assumes that the pivot actually IS arr2[low2] so when the final swap is performed, arr2[low2] wrongly takes place of a real pivot (a1) inside of arr2. The only situation when it works is if arr1[low1]=arr2[low2]

Upvotes: 0

RobertBaron
RobertBaron

Reputation: 2854

In the partition function, the initial value of leftmark should be left, not left + 1.

Upvotes: 1

Related Questions