# sorting.py
# Walker M. White (wmw2)
# November 20, 2012
"""Contains functions methods for sorting, together with their helpers.
Included are:

    min_of, to find the minimum of b[h..k].

    insert_value, to insert a value into its sorted position in b[h..k-1].

    linear_search, to find a value in an sequence.

    partition0, used in quicksort, as done in class.

    partition, used in quicksort, done a bit more efficiently.

    median_of_3, used in quicksort.

    merge, used in mergesort.

    binary_search, binary search in a list.

    selection_sort, to sort a list.

    selection_sort1, to sort a list.

    insertion_sort, to sort a list.

    mergesort, to sort a list recursively.

    quicksort0, the basic quicksort algorithm.

    quicksort, quicksort changed to fix inefficiencies.

    Dutch National Flag."""


def min(b,h,k):
    """Returns: the position of the minimum value of b[h..k].

    Precondition: h <= k are valid positions in sequence b"""
    p = h 
    i = h
    # inv: b[p] is the minimum of b[h..i], i.e.
    #
    #    h-------p------------i---------k
    # b | b[p] is min of this  |    ?    |
    #    --------------------------------
    while (i != k):
        i= i+1
        if (b[i] < b[p]):
            p = i
    
    return p


def insert_value(b, h, k):
    """Sort b[h..k]; put its elements in ascending order.
    
    Precondition: b[h..k-1] is sorted, and b[k] contains a value."""
    v = b[k]
    i = k
    # inv P: (1) Placing v in b[i] makes b[h..k] a
    #            permutation of its initial value
    #        (2) b[h..k] with b[i] removed is initial b[h..k-1]
    #        (3) v < b[i+1..k]
    while ((i != h) and v < b[i-1]):
        b[i] = b[i-1]
        i = i-1
    
    b[i] = v


def linear_search(b, x):
    """Returns: index of x in b; or -1 if x is not in b. 
    
    Precondition: b is a sequence"""
    # invariant: x is not in b[0..i-1]
    i = 0
    while i != len(b) and b[i] != x:
        i = i+1
        
    return i if i < len(b) else -1


def partition0(b, h, k):
    """Permute b[h..k] and return integer j satisfying R:<br><br>
    
        b[h..j-1] <= b[j] = x <= b[j+1..k],<br><br>
    
        where x stands for the value initially in b[h].
    
    Precondition: b[h..k] has at least three elements."""
    #
    #          h---------------------------k
    # pre:  b |x|     ?                     |  for some x
    #          -----------------------------
    # 
    #          h-------------j-------------k
    # post: b |   <= x      |x|     >= x    |
    #          -----------------------------

    j = h
    i = k
    # inv P: b[h..j-1] <= b[j] = x <= b[i+1..k], i.e.
    #  
    #          h---------j-------i------------k
    # post: b |   <= x  |x|  ?    |    >= x    |
    #          --------------------------------
    while (j < i):
        if (b[j+1] <= b[j]):
            temp = b[j]; b[j] = b[j+1]; b[j+1] = temp
            j = j+1
        else:
            temp = b[j+1]; b[j+1] = b[i]; b[i] = temp
            i = i-1
        
    return j


def partition(b, h, k):
    """Permute b[h..k] and return integer j satisfying R:<br><br>
    
        b[h..j-1] <= b[j] = x <= b[j+1..k]<br><br>
    
    where x stands for the value initially in b[h].

    Precondition: b[h..k] has at least three elements."""

    # Truthify R1: b[h+1..j] <= b[h] = x <= b[j+1..k];
    i = h+1
    j = k
    # inv P: b[h+1..i-1] <= b[h] = x <= b[j+1..k], i.e.
    #  
    #
    #    h---------i------j----------k
    # b |x| <= x  |    ?   |  >= x    |
    #    -----------------------------
    while (i <= j):
        if (b[i] < b[h]):
            i = i+1
        elif (b[j] > b[h]):
            j = j-1
        else:   # b[j] < x < b[i]
            t1 = b[i]; b[i] = b[j]; b[j] = t1
            i = i+1; j = j-1
    t = b[h]; b[h] = b[j]; b[j] = t
    return j


def median_of_3(b, h, k):
    """Permute b[h], b[(h+k)/2], and b[k] to put their median in b[h].
    
    Precondition: h <=k are valid positions in b."""
    e = (h+k)/2     # index of middle element of array
    m = e           # index of median

    # Return if b[h] is median; else store index of median in m
    if (b[h] <= b[e]):
        if (b[h] >= b[k]):
            return
        # b[h] is smallest of the three
        if (b[e] <= b[k]):
            m = e
        else:
            m = k
    else:
        if (b[h] <= b[k]):
            return
        # b[h] is largest of the three
        if (b[e] <= b[k]):
            m = k
        else:
            m = e

    t = b[h]; b[h] = b[m]; b[m] = t


def merge(b, h, e, k):
    """Sort b[h..k]; put its elements in ascending order.

    Precondition: Segments b[h..e] and b[e+1..k] are already sorted."""
    
    c= b[h:e+1];
    # c is a copy of original b[h..e]

    i = h; j = e+1; m = 0
    # inv: b[h..i-1] contains its final, sorted values
    #      b[j..k] remains to be transferred
    #      c[m..e-h] remains to be transferred
    while i != k+1:
        if (j <= k and (m > e-h or b[j] <= c[m])):
            b[i] = b[j]; j = j+1;
        else:
            b[i] = c[m]; m = m+1

        i = i+1


def binary_search(b, x):
    """Returns: the index i that satisfies R: b[i] <= x < b[i+1].

    Precondition: b is in non-descending order."""
    
    i = -1; j = len(b)
    # inv: b[0..i] <= x < b[j..] and -1 <= i < j <= len(b), i.e.
    #          0--------i----------j---------- len(b)
    #       b |     <=x  |    ?   |   >x      |
    #          -------------------------------
    while (j != i+1):
        e = (i+j)/2
        # -1 <= i < e < j <= len(b)
        if (b[e] <= x) :
            i = e
        else:
            j = e
    
    return i if b[i] == x else -1


def selection_sort(b):
    """Sort b: put its elements in ascending order."""

    j = 0
    # inv P:  b[0..j-1] is sorted and b[0..j-1] <= b[j..], i.e.
    #          0---------------j--------------- len(b)
    # inv : b |  sorted, <=   |    >=          |
    #          --------------------------------
    while (j != len(b)):
        p = min(b, j, len(b)-1)
        # b[p] is minimum of b[j..len(b)-1]
            
        # Swap b[j] and b[p]
        t = b[j]; b[j] = b[p]; b[p] = t
        j = j+1


def selection_sort1(b):
    """Sort b: put its elements in ascending order."""
    j = 0
    # inv P: b[0..j-1] is sorted and b[0..j-1] <= b[j..], i.e.
    #          0---------------j--------------- len(b)
    # inv : b |  sorted, <=   |    >=          |
    #          --------------------------------
    while (j != len(b)):
        # Put into p the index of smallest element in b[j..]
        p = j
        i = j+1
        while (i != len(b)):
            if (b[i] < b[p]):
                p = i
            i = i+1
    
            
        # Swap b[j] and b[p]
        t = b[j]; b[j] = b[p]; b[p] = t
        j = j+1


def insertion_sort(b, h, k):
    """Sort b[h..k]: put its elements in ascending order."""

    # inv: h <= j <= k+1  and  b[h..j-1] is sorted, i.e.
    #          h---------------j--------------k
    # inv : b |  sorted,      |     ?          |
    #          --------------------------------
    j = h
    while (j <= k):
        # Sort b[0..j], given that b[0..j-1] is sorted
        insert_value(b,0,j)
        j = j+1


def mergesort(b, h, k):
    """Sort b[h..k]: put its elements in ascending order."""
    if (h >= k):
        return
    
    e = (h+k)/2
    mergesort(b, h, e);    # Sort b[h..e]
    mergesort(b, e+1, k);  # Sort b[e+1..k]
    merge(b, h, e, k);     # Merge the 2 segments


def quicksort0(b, h, k):
    """Sort b[h..k]  --put its elements in ascending order."""
    if (k+1-h < 2):
        return
    
    j = partition(b,h,k)
    # b[h..j-1] <= b[j] <= b[j+1..k]
    quicksort0(b,h,j-1)
    quicksort0(b,j+1,k)


def quicksort(b, h, k):
    """Sort b[h..k]: put its elements in ascending order."""

    # Tail recursive loop
    while (True):
        if (k+1-h < 10):
            insertion_sort(b,h,k)
            return
        median_of_3(b,h,k)
        
        # b[h] is between b[(h+k)/2] and b[k]
        j = partition(b,h,k)
        # b[h..j-1] <= b[j] <= b[j+1..k], i.e.
        #
        #    h---------j---------k
        # b |   <= x  |x|  >= x   |   for some x
        #    ---------------------
        if (j-h <= k-j):
            quicksort(b,h,j-1);
            # quicksort(b,j+1,k);
            h = j+1
            continue 
        else:
            quicksort(b,j+1,k)
            # quicksort(b,h,j-1);
            k = j-1
            continue


def dutch_national_flag(b):
    """Swap the values of b so that the negative ones are
    first, then the 0's, and finally the positive ones.
    In the original problem, the negative values are red
    balls, 0's are white balls, positive values are blue balls
    
    Precondition: b is a list of integers"""
    #        0------------------------------------ len(b)
    # pre: b|              ?                      |
    #        -------------------------------------
    # 
    #        0------------------------------------ len(b)
    # post:b|   <0    |    = 0     |    >0        |
    #        -------------------------------------
    
    h = 0
    k = 0
    t = len(b)-1;
    
    #        0-------h-------k------t------------- len(b)
    # inv :b|  <0   |  = 0  |   ?    |    >0      |
    #        -------------------------------------
    
    while (k <= t):
        if (b[k] < 0):
            temp = b[k]; b[k] = b[h]; b[h] = temp
            h = h+1;  k = k+1
        elif (b[k] == 0):
            k = k+1
        else:
            temp = b[k]; b[k] = b[t]; b[t] = temp
            t = t-1