<jupyter_start><jupyter_text>SortingA frequent task in data science, engineering, etc. is the seemingly mundane task ofsorting or ordering things. Here we explore a couple of simple sorting algorithms,just to show some of the thoughts that go into such a task, then will ultimately resortto the internal sorting routines built into Python.Sorting is frequently necessary when data are being handled; for example in integrationand differentiation the data are usually presented to the various algorithms in ascending ordescending order (at least on the x-axis).One may have tables of numbers, representing one or more explanatory variables, and one ormore responses. At times we may need to arrange these tables in an order dictated by oneor another of these various variables. Alternatively we may want to nd the median valueor upper quartile of such a list { this task requires sorting.When sorting, one can also carry along operations to maintain correspondence with otherlists (for lack of better name lets call this sort-and-carry).Tasks that fall under the broad category of sorting are:- Sort ; rearrange an array of numbers into numerical order (ascending or descending).- Sort and carry along ; rearrange an array of numbers into numerical order while per-forming the same rearrangement of one or more additional arrays so that the correspon-dence between elements in all arrays is maintained (the sets of arrays are essentiallya relational database { so that each record (row) maintains the cross-record (elds;columns) relationship).- Index ; given an array, prepare an index table that is a table of pointers that indicateswhich number array element comes rst in numerical order, which is second, and soon.- Rank ; given an array, prepare a rank table that tells the numerical rank of an arrayelement.The task of sorting `N` elements requires on the order of $K \cdot Nlog2N$ operations. Thealgorithm inventor tries to make $K$ as small as possible (understanding that $K = 0$ ispractically impossible). Three useful sorting algorithms are:        1. Straight insertion sort;    2. Heapsort sort; and    3. Quicksort sort.    The choice of method depends on the size of the list that needs to be sorted. If the list isshort (perhaps $N < 50$ elements) then straight insertion is fast enough, concise, and simpleto program. For a long list ($N > 1000$ elements) Quicksort is faster, but achieves the speedby use of extra memory. Heapsort is also good for large lists, and is an in-place routine. Python lists have a built-in `sort()` method that modifies the list in-place and a `sorted()`built-in function that builds a new sorted list from an iterable. So when sorting needs tobe done, you should use the built-in tools. However, because it is a useful programmingconstruct, the three sorting algorithms are presented as Python primitive codes.  Bubble SortThe bubble sort is a place to start despite it's relative slowness. It is a pretty reviledalgorithm (read the Wikipedia entry), but it is the algorithm that a naive programmermight cobble together in a hurry, and despite its shortcomings (it's really slow andinefficient), it is robust.Here is a description of the sorting task as described by <NAME> (2016)(pg. 65):   "Imagine you want to alphabetize your unsorted collection of books. A    natural approach would be just to scan across the shelf looking for out-    of-order pairs - Wallace followed by Pynchon, for instance - and     flipping them around. Put Pynchon ahead of Wallace, then continue your scan,    looping around to the beginning of the shelf each time you reach the end.    When you make a complete pass without finding any more out-of-order    pairs on the entire shelf, then you know the job is done.    This process is a Bubble Sort, and it lands us in quadratic time. There    are n books out of order, and each scan through the shelf can move each    one at most one position. (We spot a tiny problem, make a tiny fix.) So    in the worst case, where the shelf is perfectly backward, at least one book    will need to be moved n positions. Thus a maximum of n passes through    n books, which gives us O(n2) in the worst case. For instance, it    means that sorting five shelves of books will take not five times as long as    sorting a single shelf, but twenty-five times as long."Converting the word description into Python is fairly simple. We will have a vector of nnumbers (we use a vector because its easy to step through the different positions),and we will scan through the vector once (and essentially find the smallest thing),and put it into the first position. Then we scan again from the second position andfind the smallest thing remaining, and put it into the second position, and so on untilthe last scan which should have the remaining largest thing. If we desire a decreasingorder, simply change the sense of the comparison.The algorithm defines an array and then sorts by repeated passes through the array.The program (outside of the sorting algorithm) is really quite simple.* Load contents into an array to be sorted.* Echo (print) the array (so we can verify the data are loaded as anticipated).* Loads the sorting function (the two loops)* Sort the array, put the results back into the array (an in-place sort).* Report the results.<jupyter_code>#array = [7,11,5,8,9,13,66,99,223]
#array = [7,11,5]
array=[1003 ,3.2 ,55.5 , -0.0001 , -6 ,666.6 ,102]
howMany = len(array)
print("Item Count = : ",howMany)
print("Unsorted List : ", array)
# insertion sort
for irow in range(0, howMany-1) : 
    for jrow in range(0,(howMany-1-irow)) :
        if array[jrow]> array[jrow+1] :
            swap = array[jrow]
            array[jrow]=array[jrow+1]
            array[jrow+1]=swap
        else:
            continue
#results  
print("Sorted List : ", array, end ="")<jupyter_output>Item Count = :  7
Unsorted List :  [1003, 3.2, 55.5, -0.0001, -6, 666.6, 102]
Sorted List :  [-6, -0.0001, 3.2, 55.5, 102, 666.6, 1003]<jupyter_text>In the script we see that the program (near the bottom of the file) assigns the values to the vector named array andthe initial order of the array is ${1003, 3.2, 55.5,-0.0001,-6, 666.6, 102}$. The smallestvalue in the example is -6 and it appears in the 5-th position, not the 1-st as itshould.The first pass through the array will move the largest value, 1003, in sequence to theright until it occupies the last position. Repeated passes through the array move theremaining largest values to the right until the array is ordered. One can consider thevalues of the array at each scan of the array as a series of transformations (irow-thscan) -- in practical cases we don't necessarily care about the intermediate values,but here because the size is manageable and we are trying to get our feet wet withalgorithms, we can look at the values.The sequence of results (transformations) after each pass through the array is shownin the following list:1. Initial value: [1003; 3,2; 55,5;-0,0001;-6; 666,6; 102].2. First pass: [3,2; 55,5;-0,0001;-6; 666,6; 102; 1003].3. Second pass: [3,2;-0,0001;-6; 55,5; 102; 666,6; 1003].4. Third pass: [-0,0001;-6; 3,2; 55,5; 102; 666,6; 1003].5. Fourth pass: [-6;-0,0001; 3,2; 55,5; 102; 666,6; 1003].6. Fifth pass: [-6;-0,0001; 3,2; 55,5; 102; 666,6; 1003]. Sorted, fast scan.7. Sixth pass: [-6;-0,0001; 3,2; 55,5; 102; 666,6; 1003]. Sorted, fast scan.We could probably add additional code to break from the scans when we have a singlepass with no exchanges (like the last two scans) -- while meaningless in this example, for larger collections ofthings, being able to break out when the sorting is complete is a nice feature.  Insertion SortThe next type of sorting would be to select one item and locate it either left or rightof an adjacent item based on its size { like sorting a deck of cards, or perhaps a betterdescription { again using the bookshelf analog from Christian and Griffths (2016)(pg. 65)You might take a different tack -- pulling all the books off the shelfand putting them back in place one by one. You'd put the ffrst book inthe middle of the shelf, then take the second and compare it to the first,inserting it either to the right or to the left. Picking up the third book,you'd run through the books on the shelf from left to right until you foundthe right spot to tuck it in. Repeating this process, gradually all of thebooks would end up sorted on the shelf and you'd be done. Computerscientists call this, appropriately enough, Insertion Sort. The good newsis that it's arguably even more intuitive than Bubble Sort and doesn'thave quite the bad reputation. The bad news is that it's not actually thatmuch faster. You still have to do one insertion for each book. And eachinsertion still involves moving past about half the books on the shelf, onaverage, to find the correct place.Although in practice Insertion Sort does run a bit faster than Bubble Sort,again we land squarely, if you will, in quadratic time. Sorting anythingmore than a single bookshelf is still an unwieldy prospect."Listing 8 is an R implementation of a straight insertion sort. The script is quitecompact, and I used indentation and extra line spacing to keep track of the scopingdelimiters. The sort works as follows, take the an element of the array (start with2 and work to the right) and put it into a temporary location (called swap in myscript). Then compare locations to the left of swap. If smaller, then break from theloop, exchange values, otherwise the values are currently ordered. Repeat (startingat the next element) , when all elements have been traversed the resulting vector issorted. Here are the transformations for each pass through the outer loop: Straight InsertionThe straight insertion sort is the algorithm a card player would use to sort cards. Pick outthe second card and put it into order with respect to the first; then pick the third cardand insert it into sequence with the first two; continue until the last card is picked out andinserted. Once the last card is sequenced, the result is a sorted deck (list).Python implementation of such an algorithm is:<jupyter_code>#array = [7,11,5,8,9,13,66,99,223]
array = [7,11,5]
howMany = len(array)
print("Item Count = : ",howMany)
print("Unsorted List : ", array, end ="")
# insertion sort
for i in range(1, len(array)): # Traverse through 1 to len(arr) 
    key = array[i] 
        # Move elements of arr[0..i-1], that are 
        # greater than key, to one position ahead 
        # of their current position 
    j = i-1
    while j >=0 and key < array[j] : 
            array[j+1] = array[j] 
            j -= 1
    array[j+1] = key 
#results  
print("Sorted List : ", array, end ="")<jupyter_output>Sorted List :  [5, 7, 11]<jupyter_text>Probably useful to put into a functional structure:<jupyter_code># Function to do insertion sort 
def insertionSort(array): 
    # Traverse through 1 to len(arr) 
    for i in range(1, len(array)): 
        key = array[i] 
        # Move elements of arr[0..i-1], that are 
        # greater than key, to one position ahead 
        # of their current position 
        j = i-1
        while j >=0 and key < array[j] : 
                array[j+1] = array[j] 
                j -= 1
        array[j+1] = key 
    return(array)
array = [7,11,5,8,9,13,66,99,223]
print("Unsorted List : ", array)
insertionSort(array)
print("Sorted List : ", array, end ="")<jupyter_output>Unsorted List :  [7, 11, 5, 8, 9, 13, 66, 99, 223]
Sorted List :  [5, 7, 8, 9, 11, 13, 66, 99, 223]<jupyter_text>Merge SortA practical extension of these slow sorts is called the Merge Sort. It is an incrediblyuseful method. One simply breaks up the items into smaller arrays, sorts those arrays -then merges the sub-arrays into larger arrays (now already sorted), and nally mergesthe last two arrays into the nal, single, sorted array.Here is a better description, again from Christian and Griffths (2016):" ... information processing began in the US censuses of the nineteenthcentury, with the development, by <NAME> and later by IBM, ofphysical punch-card sorting devices. In 1936, IBM began producing a lineof machines called \collators" that could merge two separately orderedstacks of cards into one. As long as the two stacks were themselves sorted,the procedure of merging them into a single sorted stack was incrediblystraightforward and took linear time: simply compare the two top cardsto each other, move the smaller of them to the new stack you're creating,and repeat until finished.The program that <NAME> wrote in 1945 to demonstrate thepower of the stored-program computer took the idea of collating to itsbeautiful and ultimate conclusion. Sorting two cards is simple: just putthe smaller one on top. And given a pair of two-card stacks, both of themsorted, you can easily collate them into an ordered stack of four. Repeatingthis trick a few times, you'd build bigger and bigger stacks, each one ofthem already sorted. Soon enough, you could collate yourself a perfectlysorted full deck - with a final climactic merge, like a riffe shuffle's order-creating twin, producing the desired result. This approach is known todayas Merge Sort, one of the legendary algorithms in computer science."There are several other variants related to Merge Sort; Quicksort and Heapsort beingclose relatives;<jupyter_code># Python program for implementation of MergeSort 
# https://www.geeksforgeeks.org/merge-sort/
# This code is contributed by <NAME> 
def mergeSort(arr): 
    if len(arr) >1: 
        mid = len(arr)//2 # Finding the mid of the array 
        L = arr[:mid] # Dividing the array elements  
        R = arr[mid:] # into 2 halves 
  
        mergeSort(L) # Sorting the first half 
        mergeSort(R) # Sorting the second half 
  
        i = j = k = 0
          
        # Copy data to temp arrays L[] and R[] 
        while i < len(L) and j < len(R): 
            if L[i] < R[j]: 
                arr[k] = L[i] 
                i+= 1
            else: 
                arr[k] = R[j] 
                j+= 1
            k+= 1
          
        # Checking if any element was left 
        while i < len(L): 
            arr[k] = L[i] 
            i+= 1
            k+= 1
          
        while j < len(R): 
            arr[k] = R[j] 
            j+= 1
            k+= 1
  
# Code to print the list 
def printList(arr): 
    for i in range(len(arr)):         
        print(arr[i], end =" ") 
    print() 
  
# driver code to test the above code 
#if __name__ == '__main__': 
arr=[1003 ,3.2 ,55.5 , -0.0001 , -6 ,666.6 ,102]
#arr = [12, 11, 13, 5, 6, 7]  
print ("Given array is", end ="\n")  
printList(arr) 
mergeSort(arr) 
print("Sorted array is: ", end ="\n") 
printList(arr)<jupyter_output>Given array is
1003 3.2 55.5 -0.0001 -6 666.6 102 
Sorted array is: 
-6 -0.0001 3.2 55.5 102 666.6 1003<jupyter_text>Heapsort<jupyter_code># Python program for implementation of heap Sort 
  
# To heapify subtree rooted at index i. 
# n is size of heap 
def heapify(arr, n, i): 
    largest = i  # Initialize largest as root 
    l = 2 * i + 1     # left = 2*i + 1 
    r = 2 * i + 2     # right = 2*i + 2 
  
    # See if left child of root exists and is 
    # greater than root 
    if l < n and arr[i] < arr[l]: 
        largest = l 
  
    # See if right child of root exists and is 
    # greater than root 
    if r < n and arr[largest] < arr[r]: 
        largest = r 
  
    # Change root, if needed 
    if largest != i: 
        arr[i],arr[largest] = arr[largest],arr[i]  # swap 
  
        # Heapify the root. 
        heapify(arr, n, largest) 
  
# The main function to sort an array of given size 
def heapSort(arr): 
    n = len(arr) 
  
    # Build a maxheap. 
    # Since last parent will be at ((n//2)-1) we can start at that location. 
    for i in range(n // 2 - 1, -1, -1): 
        heapify(arr, n, i) 
  
    # One by one extract elements 
    for i in range(n-1, 0, -1): 
        arr[i], arr[0] = arr[0], arr[i]   # swap 
        heapify(arr, i, 0) 
  
# Driver code to test above 
arr=[1003 ,3.2 ,55.5 , -0.0001 , -6 ,666.6 ,102]
#arr = [ 12, 11, 13, 5, 6, 7] 
heapSort(arr) 
n = len(arr) 
print ("Sorted array is") 
for i in range(n): 
    print ("%d" %arr[i]), 
# This code is contributed by <NAME> 

# Python program to sort the words in lexicographical 
# order 
  
def sortLexo(my_string): 
  
    # Split the my_string till where space is found. 
    words = my_string.split() 
      
    # sort() will sort the strings. 
    words.sort() 
  
    # Iterate i through 'words' to print the words 
    # in alphabetical manner. 
    for i in words: 
        print( i )  
  
# Driver code  
if __name__ == '__main__': 
      
    my_string = "hello this is example how to sort " \
              "the word in alphabetical manner"
    # Calling function 
    sortLexo(my_string)<jupyter_output>alphabetical
example
hello
how
in
is
manner
sort
the
this
to
word
{'fraction_non_alphanumeric': 0.07481665483794653, 'fraction_numerical': 0.03217411876035013, 'mean_word_length': 3.3223415132924337, 'pattern_counts': {'":': 0, '<': 33, '<?xml version=': 0, '>': 26, 'https://': 1, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '5', 'dir': 'jupyter-structured-clean-dedup', 'id': '98951', 'license': 'CC0-1.0', 'n_tokens_mistral': 5209, 'n_tokens_neox': 4655, 'n_words': 2465, 'path': '1-Lessons/Lesson04/Spring2021/src/SortingAsExampleOfFlowControl.ipynb', 'repo_name': 'dustykat/engr-1330-psuedo-course', 'size': '16956'}