Week11:Sorting and Efficiency

In this week, we talked about a lot of sorting and its efficiency, such as merge_sort, quick_sort and tim-sort(Python's built-in sort).

Most sorting algorithms work by comparing the data being sorted. In some cases, it may be desirable to sort a large chunk of data (for instance, a struct containing a name and address) based on only a portion of that data. The piece of data actually used to determine the sorted order is called the key. 

Sorting algorithms are usually judged by their efficiency. In this case, efficiency refers to the algorithmic efficiency as the size of the input grows large and is generally based on the number of elements to sort. Most of the algorithms in use have an algorithmic efficiency of either O(n^2) or O(n*log(n)). A few special case algorithms can sort certain data sets faster than O(n*log(n)). These algorithms are not based on comparing the items being sorted and rely on tricks. It has been shown that no key-comparison algorithm can perform better than O(n*log(n)). 

Many algorithms that have the same efficiency do not have the same speed on the same input. Algorithms must be judged based on their average case, best case, and worst case efficiency. Some algorithms, such as quick sort, perform exceptionally well for some inputs, but horribly for others. Other algorithms, such as merge sort, are unaffected by the order of input data. Even a modified version of bubble sort can finish in O(n) for the most favorable inputs. 

Here are examples of merge_sort and quick_sort that Danny provided:

"def quick(L):

    if len(L) > 1:
        pivot = L[0] # there are much better ways of choosing the pivot!
        smaller_than_pivot = [x for x in L[1:] if x < pivot]
        larger_than_pivot = [x for x in L[1:] if x >= pivot]
        return quick(smaller_than_pivot) + [pivot] + quick(larger_than_pivot)
    else:
        return L
    


def merge2(L1:list, L2:list) -> list:
    """return merge of L1 and L2
    NOTE: modifies L1 and L2

    >>> merge2([1, 3, 5], [2, 4, 6])
    [1, 2, 3, 4, 5, 6]
    >>> merge2([1, 2, 3], [0, 4, 5])
    [0, 1, 2, 3, 4, 5]
    >>> merge2([0], [1, 2, 3, 4])
    [0, 1, 2, 3, 4]
    """
    L = []
    L1.reverse()
    L2.reverse()
    while L1 and L2:
        if L1[-1] < L2[-1]:
            L.append(L1.pop())
        else:
            L.append(L2.pop())
    L1.reverse()
    L2.reverse()
    return L + L1 + L2


def merge(L1:list, L2:list) -> list:
    """return merge of L1 and L2
    NOTE: modifies L1 and L2

    >>> merge([1, 3, 5], [2, 4, 6])
    [1, 2, 3, 4, 5, 6]
    >>> merge([1, 2, 3], [0, 4, 5])
    [0, 1, 2, 3, 4, 5]
    >>> merge([0], [1, 2, 3, 4])
    [0, 1, 2, 3, 4]
    """
    decreasing_from_largest = []
    while L1 and L2:
        if L1[-1] > L2[-1]:
            decreasing_from_largest.append(L1.pop())
        else:
            decreasing_from_largest.append(L2.pop())
    decreasing_from_largest.reverse() 
    return L1 + L2 + decreasing_from_largest


def merge_sort(L):
    """Produce copy of L in non-decreasing order

    >>> merge_sort([1, 5, 3, 4, 2])
    [1, 2, 3, 4, 5]
    """
    if len(L) < 2 :
        return L
    else :
        left_sublist = L[:len(L)//2]
        right_sublist = L[len(L)//2:]
        return merge2(merge_sort(left_sublist), 
                      merge_sort(right_sublist))"

Time

Sort
Average
Best
Worst
Space
Stability
Remarks

Merge Sort
O(n*log(n))
O(n*log(n))
O(n*log(n))
Depends
Stable
On arrays, merge sort requires O(n) space; on linked lists, merge sort requires constant space
Quicksort
O(n*log(n))
O(n*log(n))
O(n^2)
Constant
Stable
Randomly picking a pivot value (or shuffling the array prior to sorting) can help avoid worst case scenarios such as a perfectly sorted array.