<jupyter_start><jupyter_text>Bubble Sort<jupyter_code>def bubble_sort(l):
    n = len(l)
    # print(n)
    
    # Outer loop. Goes over the whole thing 'n' times
    # (because each time, one 'highest' will have moved to the end)
    
    for i in range(n):
        swapped = False
        
        # try to bubble the highest one up
        for j in range(0, (n-i)-1):
            
            # compare pairs, move higher one up (the highest will always reach the end this way!)
            if l[j] > l[j+1]:
                l[j], l[j+1] = l[j+1], l[j]
                swapped = True
        if not swapped:
            break
l = [1, 2, 4, 1, 2, 5, 5, 6, 1, 110, 15]
bubble_sort(l)
print(l)<jupyter_output>[1, 1, 1, 2, 2, 4, 5, 5, 6, 15, 110]<jupyter_text>Insertion Sort<jupyter_code>def insertion_sort(l):
    # Go through all elements (except  first).
    # Call it 'Key'.
    # Each time, the key would be 'inserted' in its place.
    # At each iteration, stuff less than i would be sorted already.
    
    for i in range(1, len(l)):
        
        key = l[i] # hold this key
        
        # start comparing keys to things on its left!
        # stop when less or equal value found (or we reach left end)
        
        j =i-1

        while j >= 0 and key < l[j]:
            l[j+1] = l[j] # move this to right. Slot left on j
            j -= 1
            
        l[j+1] = key # Place key in free slot..(j+1 because we decrement j above)
l = [1, 2, 4, 1, 2, 5, 5, 6, 1, 110, 15]
insertion_sort(l)
print(l)<jupyter_output>[1, 1, 1, 2, 2, 4, 5, 5, 6, 15, 110]<jupyter_text>Selection Sort<jupyter_code>def selection_sort(l):
    n = len(l)
    
    # for each element in the list (starting from left)
    for i in range(n):
        min_idx = i # find the minimum ...
        # ... in the *rest* of the list
        for j in range(i+1, n):
            
            if l[j] < l[min_idx]:
                min_idx = j
        
        # swap the minimum  with current element, now we have (sorted stuff till i)
        l[i] , l[min_idx] = l[min_idx], l[i]
l = [1, 2, 4, 1, 2, 5, 5, 6, 1, 110, 15]
selection_sort(l)
print(l)<jupyter_output>[1, 1, 1, 2, 2, 4, 5, 5, 6, 15, 110]<jupyter_text>Qucik Sort<jupyter_code>import random

def qsort(l, fst, lst):
    if fst >= lst: return
    
    i, j = fst, lst
    pivot = l[random.randint(fst, lst)]
    
    while i <= j:
        while l[i] < pivot: i += 1
        while l[j] > pivot: j -= 1
        if i <= j:
            l[i], l[j] = l[j], l[i]
            i, j = i + 1, j-1
    
    qsort(l, fst, j)
    qsort(l, i, lst)
l = [1, 2, 4, 1, 2, 5, 5, 6, 1, 110, 15]
qsort(l, 0, len(l)-1)
print(l)<jupyter_output>[1, 1, 1, 2, 2, 4, 5, 5, 6, 15, 110]<jupyter_text>Sorting in the Rel World  Descending Sorts<jupyter_code>def selection_sort(l):
    n = len(l)
    
    # for each element in the list (starting from left)
    for i in range(n):
        idx = i # find the replacement ...
        
        # ... in the *rest* of the list
        for j in range(i+1, n):
            
            if l[j] > l[idx]:  # change to > for descending
                idx = j
                
        # swap the replacement with current element, now we have ( sorted stuff till i)
        l[i] , l[idx] = l[idx], l[i]
l = [1, 2, 4, 1, 2, 5, 5, 6, 1, 110, 15]
selection_sort(l)
print(l)<jupyter_output>[110, 15, 6, 5, 5, 4, 2, 2, 1, 1, 1]<jupyter_text>But there's better way!<jupyter_code>def less_than(a, b):
    return a < b
def selection_sort(l, compare_with):
    n = len(l)
    
    # for each element in the list (starting from left)
    for i in range(n):
        min_idx = i   # find the minimum ...
        
        # ... in the *rest* of the list
        for j in range(i+1, n):
            
            if compare_with(l[j], l[min_idx]):  # now the "comparison" is out-sourced !
                min_idx = j
                
        # swap the minimum with current element, now we have ( sorted stuff till i)
        l[i] , l[min_idx] = l[min_idx], l[i]
l = [1, 2, 4, 1, 2, 5, 5, 6, 1, 110, 15]
selection_sort(l, less_than)
print(l)
def greater_than(a, b):
    return a > b
l = [1, 2, 4, 1, 2, 5, 5, 6, 1, 110, 15]
selection_sort(l, greater_than)
print(l)<jupyter_output>[110, 15, 6, 5, 5, 4, 2, 2, 1, 1, 1]<jupyter_text>Taking it Even FutherNow we can do all sorts of stuff with this without making a single change to our selcetion sort code.<jupyter_code>all_tuples = [
    (24, 25),
    (1, 2),
    (2, 4),
    (3, 5),
]
def tuple_less_than(a, b):
    return sum(a) < sum(b)
def tuple_greater_than(a, b):
    return sum(a) > sum(b)
print("Ascending:\t", end="")
selection_sort(all_tuples, tuple_less_than)
print(all_tuples)

print("Descending:\t", end="")
selection_sort(all_tuples, tuple_greater_than)
print(all_tuples)<jupyter_output>Ascending:	[(1, 2), (2, 4), (3, 5), (24, 25)]
Descending:	[(24, 25), (3, 5), (2, 4), (1, 2)]<jupyter_text>Sorting in PythonIf you have a list of dictionaries -- each representing a student, for instance.<jupyter_code>d = [
    { 'name': 'Khalid', 'age': 5},
    { 'name': 'Usman',  'age': 12},
    { 'name': 'Ali',    'age': 7},
    { 'name': 'Farooq', 'age': 3},
]
def d_less_than(a, b):
    return a['age'] < b['age']

selection_sort(d, d_less_than)
print(d)
def student_age(a):
    return a['age']
print(d)
d.sort(key=student_age, reverse=True)
print(d)<jupyter_output>[{'name': 'Farooq', 'age': 3}, {'name': 'Khalid', 'age': 5}, {'name': 'Ali', 'age': 7}, {'name': 'Usman', 'age': 12}]
[{'name': 'Usman', 'age': 12}, {'name': 'Ali', 'age': 7}, {'name': 'Khalid', 'age': 5}, {'name': 'Farooq', 'age': 3}]<jupyter_text>Sorting Objects of Custom Classes<jupyter_code>class Student:
    def __init__(self, name, age):
        self.name = name
        self.age = age
    def __str__(self):
        return self.name + ': ' + str(self.age)
s1 = Student('Wajid', 5)
s2 = Student('Usman', 7)
s3 = Student('Ali', 3)

s = [s1, s2, s3]<jupyter_output><empty_output><jupyter_text>You don't even have to give the function a name -- just use an anonymous function like so:<jupyter_code>for i in s:
    print(i)<jupyter_output>Wajid: 5
Usman: 7
Ali: 3<jupyter_text>Anonymous Function<jupyter_code>s.sort(key=lambda x: x.age) # reverse
for i in s:
    print(i)<jupyter_output>Ali: 3
Wajid: 5
Usman: 7
{'fraction_non_alphanumeric': 0.15635957921581128, 'fraction_numerical': 0.041919030921262354, 'mean_word_length': 2.4997211377579474, 'pattern_counts': {'":': 0, '<': 43, '<?xml version=': 0, '>': 43, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '11', 'dir': 'jupyter-structured-clean-dedup', 'id': '12777', 'license': 'MIT', 'n_tokens_mistral': 2697, 'n_tokens_neox': 2430, 'n_words': 787, 'path': '15-Sorts.ipynb', 'repo_name': 'zexhan17/Data-Structures-and-Algorithms-using-Python', 'size': '6274'}