Nerd Paradise : Coding Interview 9: Sorting a List with just Swaps

Nerd Paradise : Coding Interview 9: Sorting a List with just Swaps
Sort list of integers. But now suppose this list is a weird data structure. The only way you can modify/move elements in this array is to swap them one pair at a time using a function that's already been provided for you.

swap(mysterylist, indexA, indexB)

These pairs can be any two arbitrary elements in the list. They don't have to be adjacent neighbors.

And don't allocate new memory.

def sort(mysterylist):
    qsort(mysterylist, 0, len(mysterylist) - 1)

def qsort(list, start, end):
    if end <= start: return

    # if you want to avoid the problem of nearly-sorted lists     # not performing very well with quick sort, you can swap      # the first element in the sorting range with a random     # element in the sorting range before using the first element     # as the pivot value.      pivot = list[start]

    lower_ends = start # points at the last element below the pivot     upper_begins = end + 1 # points at the first element above pivot 
    while lower_ends != upper_begins - 1:
        index = lower_ends + 1
        if list[index] > pivot:
            # add to the larger list             swap(list, upper_begins - 1, index)
            upper_begins = upper_begins - 1
        else:
            # add to the smaller list             lower_ends = lower_ends + 1
    # move the pivot into the middle by swapping it      # with the last smaller number     swap(list, start, lower_ends)

    # recurse on the smaller list     qsort(list, start, lower_ends - 1)

    # recurse on the larger list     qsort(list, upper_begins, end)

Another valid approach is heap sort which is also swap-based. It might be a bit easier to visualize, but creates more code. 

# convert the list into a largest-first heap by # iterating through the list and bubbling each # element up as far as it needs to go until its # parent is larger than itself.  # This is O(n log n) def heapify(list):
    i = 1
    while i < len(list):
        j = i
        while j > 0:
            parent_index = int((j - 1) / 2)
            if list[j] > list[parent_index]:
                swap(list, j, parent_index)
            j = parent_index
        i += 1

# the list of the given length may have a value # at the index might be smaller than one of its # children, if it has any. Swap it with its  # largest child if that's the case, and recurse # down and repeat until you reach the end of the # list or until both of its children are smaller. # This is O(log n) def reheapify(list, index, length):
    left = index * 2 + 1
    right = index * 2 + 2
   
    # find the index of the child which is largest     if right < length:
        if list[left] > list[right]:
            larger_child = left
        else:
            larger_child = right
    elif left < length:
        # there is no right child         larger_child = left
    else:
        # there are no children.          return
   
    # if the largest child is larger than the item      # at the index, swap them and recurse     if list[index] < list[larger_child]:
        swap(list, index, larger_child)
        reheapify(list, larger_child, length)

# Turn the list into a heap with the largest number in front # Then pop the largest number off the heap and build up a  # virtual list at the end of the list structure. Re-heapify # the remainder of the list between each time you pick off # the largest.  def heap_sort(list):
    heapify(list)
    i = len(list) - 1
    while i > 0:
        swap(list, 0, i)
        reheapify(list, 0, i)
        i -= 1

Read full article from Nerd Paradise : Coding Interview 9: Sorting a List with just Swaps