"Unsorting" a Quicksort

Question

(Quick note! While I know there are plenty of options for sorting in Python, this code is more of a generalized proof-of-concept and will later be ported to another language, so I won't be able to use any specific Python libraries or functions.

In addition, the solution you provide doesn't necessarily have to follow my approach below.)

Background

I have a quicksort algorithm and am trying to implement a method to allow later 'unsorting' of the new location of a sorted element. That is, if element A is at index x and is sorted to index y, then the 'pointer' (or, depending on your terminology, reference or mapping) array changes its value at index x from x to y.

In more detail:
You begin the program with an array, arr, with some given set of numbers. This array is later run through a quick sort algorithm, as sorting the array is important for future processing on it.

The ordering of this array is important. As such, you have another array, ref, which contains the indices of the original array such that when you map the reference array to the array, the original ordering of the array is reproduced.

Before the array is sorted, the array and mapping looks like this:

arr = [1.2, 1.5, 1.5, 1.0, 1.1, 1.8]
ref = [0,   1,   2,   3,   4,   5]
--------
map(arr,ref) -> [1.2, 1.5, 1.5, 1.0, 1.1, 1.8]

You can see that index 0 of ref points to index 0 of arr, giving you 1.2. Index 1 of ref points to index 1 of arr, giving you 1.5, and so on.

When the algorithm is sorted, ref should be rearranged such that when you map it according to the above procedure, it generates the pre-sorted arr:

arr = [1.0, 1.1, 1.2, 1.5, 1.5, 1.8]
ref = [2,   3,   4,   0,   1,   5]
--------
map(arr,ref) -> [1.2, 1.5, 1.5, 1.0, 1.1, 1.8]

Again, index 0 of ref is 2, so the first element of the mapped array is arr[2]=1.2. Index 1 of ref is 3, so the second element of the mapped array is arr[3]=1.5, and so on.

The Issue

The current implementation of my code works great for sorting, but horrible for the remapping of ref.

Given the same array arr, the output of my program looks like this:

arr = [1.0, 1.1, 1.2, 1.5, 1.5, 1.8]
ref = [3,   4,   0,   1,   2,   5]
--------
map(arr,ref) -> [1.5, 1.5, 1.0, 1.1, 1.2, 1.8]

This is a problem because this mapping is definitely not equal to the original:

[1.5, 1.5, 1.0, 1.1, 1.2, 1.8] != [1.2, 1.5, 1.5, 1.0, 1.1, 1.8]

My approach has been this:

1. When elements a and b, at indices x and y in arr are switched,
2. Then set ref[x] = y and ref[y] = x.

This is not working and I can't think of another solution that doesn't need O(n^2) time.

Thank you!

Minimally Reproducible Example

testing = [1.5, 1.2, 1.0, 1.0, 1.2, 1.2, 1.5, 1.3, 2.0, 0.7, 0.2, 1.4, 1.2, 1.8, 2.0, 2.1]

# This is the 'map(arr,ref) ->' function
def print_links(a,b):
    tt = [a[b[i]-1] for i in range(0,len(a))]
    print("map(arr,ref) -> {}".format(tt))

    # This tests the re-mapping against an original copy of the array
    f = 0
    for i in range(0,len(testing)):
        if testing[i] == tt[i]:
            f += 1

    print("{}/{}".format(f,len(a)))

def quick_sort(arr,ref,first=None,last=None):
    if first == None:
        first = 0
    if last == None:
        last = len(arr)-1

    if first < last:
        split = partition(arr,ref,first,last)
        quick_sort(arr,ref,first,split-1)
        quick_sort(arr,ref,split+1,last)

def partition(arr,ref,first,last):
    pivot = arr[first]

    left = first+1
    right = last

    done = False
    while not done:
        while left <= right and arr[left] <= pivot:
            left += 1

        while arr[right] >= pivot and right >= left:
            right -= 1

        if right < left:
            done = True
        else:
            temp = arr[left]
            arr[left] = arr[right]
            arr[right] = temp

            # This is my attempt at preserving indices part 1
            temp = ref[left]
            ref[left] = ref[right]
            ref[right] = temp

    temp = arr[first]
    arr[first] = arr[right]
    arr[right] = temp

    # This is my attempt at preserving indices part 2
    temp = ref[first]
    ref[first] = ref[right]
    ref[right] = temp

    return right

# Main body of code
a = [1.5,1.2,1.0,1.0,1.2,1.2,1.5,1.3,2.0,0.7,0.2,1.4,1.2,1.8,2.0,2.1]
b = range(1,len(a)+1)

print("The following should match:")
print("a = {}".format(a))
a0 = a[:]
print("ref = {}".format(b))
print("----")
print_links(a,b)

print("\nQuicksort:")
quick_sort(a,b)
print(a)

print("\nThe following should match:")
print("arr = {}".format(a0))
print("ref = {}".format(b))
print("----")
print_links(a,b)

Answer 1

You can do what you ask, but when we have to do something like this in real life, we usually mess with the sort's comparison function instead of the swap function. Sorting routines provided with common languages usually have that capability built in so you don't have to write your own sort.

In this procedure, you sort the ref array (called order below), by the value of the arr value it points to. The generates the same ref array you already have, but without modifying arr.

Mapping with this ordering sorts the original array. You expected it to unsort the sorted array, which is why your code isn't working.

You can invert this ordering to get the ref array you were originally looking for, or you can just leave arr unsorted and map it through order when you need it ordered.

arr = [1.5, 1.2, 1.0, 1.0, 1.2, 1.2, 1.5, 1.3, 2.0, 0.7, 0.2, 1.4, 1.2, 1.8, 2.0, 2.1]

order = range(len(arr))
order.sort(key=lambda i:arr[i])

new_arr = [arr[order[i]] for i in range(len(arr))]

print("original array = {}".format(arr))
print("sorted ordering = {}".format(order))
print("sorted array = {}".format(new_arr))

ref = [0]*len(order)
for i in range(len(order)):
    ref[order[i]]=i

unsorted = [new_arr[ref[i]] for i in range(len(ref))]
print("unsorted after sorting = {}".format(unsorted))

Output:

original array = [1.5, 1.2, 1.0, 1.0, 1.2, 1.2, 1.5, 1.3, 2.0, 0.7, 0.2, 1.4, 1.2, 1.8, 2.0, 2.1]
sorted ordering = [10, 9, 2, 3, 1, 4, 5, 12, 7, 11, 0, 6, 13, 8, 14, 15]
sorted array = [0.2, 0.7, 1.0, 1.0, 1.2, 1.2, 1.2, 1.2, 1.3, 1.4, 1.5, 1.5, 1.8, 2.0, 2.0, 2.1]
unsorted after sorting = [1.5, 1.2, 1.0, 1.0, 1.2, 1.2, 1.5, 1.3, 2.0, 0.7, 0.2, 1.4, 1.2, 1.8, 2.0, 2.1]