<jupyter_start><jupyter_text>**Selection sort**<jupyter_code># Python program for implementation of Selection 
# Sort 
import sys 
A = [64, 25, 12, 22, 11] 

# Traverse through all array elements 
for i in range(len(A)): 
	
	# Find the minimum element in remaining 
	# unsorted array 
	min_idx = i 
	for j in range(i+1, len(A)): 
		if A[min_idx] > A[j]: 
			min_idx = j 
			
	# Swap the found minimum element with 
	# the first element		 
	A[i], A[min_idx] = A[min_idx], A[i] 

# Driver code to test above 
print ("Sorted array") 
for i in range(len(A)): 
	print("%d" %A[i]),<jupyter_output>Sorted array
11
12
22
25
64<jupyter_text>**Bubble sort**<jupyter_code># Python program for implementation of Bubble Sort

def bubbleSort(arr):
	n = len(arr)

	# Traverse through all array elements
	for i in range(n):

		# Last i elements are already in place
		for j in range(0, n-i-1):

			# traverse the array from 0 to n-i-1
			# Swap if the element found is greater
			# than the next element
			if arr[j] > arr[j+1] :
				arr[j], arr[j+1] = arr[j+1], arr[j]

# Driver code to test above
arr = [64, 34, 25, 12, 22, 11, 90]

bubbleSort(arr)

print ("Sorted array is:")
for i in range(len(arr)):
	print ("%d" %arr[i]), 

# Python program for implementation of Insertion Sort 

# Function to do insertion sort 
def insertionSort(arr): 

	# Traverse through 1 to len(arr) 
	for i in range(1, len(arr)): 

		key = arr[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 < arr[j] : 
				arr[j+1] = arr[j] 
				j -= 1
		arr[j+1] = key 


# Driver code to test above 
arr = [12, 11, 13, 5, 6] 
insertionSort(arr) 
for i in range(len(arr)): 
	print ("%d" %arr[i]) 

# Python program for implementation of MergeSort 
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 = [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
12 11 13 5 6 7 
Sorted array is: 
5 6 7 11 12 13<jupyter_text>**Dutch National Flag**<jupyter_code>import random
 
colours_in_order = 'Red White Blue'.split()
 
def dutch_flag_sort(items):
 
    lo, mid, hi = 0, 0, len(items)-1
    while mid <= hi:
        colour = items[mid]
        if colour == 'Red':
            items[lo], items[mid] = items[mid], items[lo]
            lo += 1
            mid += 1
        elif colour == 'White':
            mid += 1
        else:
            items[mid], items[hi] = items[hi], items[mid]
            hi -= 1
        print(items)
 
def dutch_flag_check(items, order=colours_in_order):
    'Return True if each item of items is in the given order'
    order_of_items = [order.index(item) for item in items]
    return all(x <= y for x, y in zip(order_of_items, order_of_items[1:]))
 
def random_balls(mx=5):
    'Select from 1 to mx balls of each colour, randomly'
    balls = sum(([[colour] * random.randint(1, mx)
                 for colour in colours_in_order]), [])
    random.shuffle(balls)
    return balls
 
def main():
    # Ensure we start unsorted
    while 1:
        balls = random_balls()
        if not dutch_flag_check(balls):
            break
    print("Original Ball order:", balls)
    dutch_flag_sort(balls)
    print("Sorted Ball Order:", balls)
    assert dutch_flag_check(balls), 'Whoops. Not sorted!'
 
if __name__ == '__main__':
    main()<jupyter_output>Original Ball order: ['Blue', 'Blue', 'Red', 'Red', 'White']
['White', 'Blue', 'Red', 'Red', 'Blue']
['White', 'Blue', 'Red', 'Red', 'Blue']
['White', 'Red', 'Red', 'Blue', 'Blue']
['Red', 'White', 'Red', 'Blue', 'Blue']
['Red', 'Red', 'White', 'Blue', 'Blue']
Sorted Ball Order: ['Red', 'Red', 'White', 'Blue', 'Blue']<jupyter_text>Jeremy's implementation<jupyter_code>import random
 
colours_in_order = 'Red White Blue'.split()

def dutch_flag_sort(items):
    r,w,b = 0,0,len(items)
    while w<b:
        if (items[w] == 'Red'):
            items[r], items[w] = items[w], items[r]
            r , w = r+1, w+1
        elif (items[w] == 'White'):
            w = w+1
        else:
            #item[w] == 'Blue'
            items[w], items[b-1] = items[b-1], items[w]
            b = b-1
            
 
def dutch_flag_check(items, order=colours_in_order):
    'Return True if each item of items is in the given order'
    order_of_items = [order.index(item) for item in items]
    return all(x <= y for x, y in zip(order_of_items, order_of_items[1:]))
 
def random_balls(mx=5):
    'Select from 1 to mx balls of each colour, randomly'
    balls = sum(([[colour] * random.randint(1, mx)
                 for colour in colours_in_order]), [])
    random.shuffle(balls)
    return balls
 
def main():
    # Ensure we start unsorted
    while 1:
        balls = random_balls()
        if not dutch_flag_check(balls):
            break
    print("Original Ball order:", balls)
    dutch_flag_sort(balls)
    print("Sorted Ball Order:", balls)
    assert dutch_flag_check(balls), 'Whoops. Not sorted!'
 
if __name__ == '__main__':
    main()<jupyter_output>Original Ball order: ['White', 'White', 'Red', 'Red', 'Red', 'Red', 'Red', 'White', 'White', 'Blue', 'Blue', 'Blue', 'Blue', 'White']
Sorted Ball Order: ['Red', 'Red', 'Red', 'Red', 'Red', 'White', 'White', 'White', 'White', 'White', 'Blue', 'Blue', 'Blue', 'Blue']<jupyter_text>**Counting Sort**<jupyter_code>colours_in_order = 'Red White Blue'.split()

def counting_sort(items):
    r,w,b = 0,0,0
    for i in range(len(items)):
        colour = items[i]
        if(colour == 'Red'):
            r= r+1
        elif(colour == 'White'):
            w= w+1
        else:
            b= b+1
    for i in range(0, r):
        items[i] = 'Red'
    for i in range(r, r+w):
        items[i] = 'White'
    for i in range(r+w,r+w+b):
        items[i] = 'Blue'

def counting_sort_check(items, order=colours_in_order):
    'Return True if each item of items is in the given order'
    order_of_items = [order.index(item) for item in items]
    return all(x <= y for x, y in zip(order_of_items, order_of_items[1:]))
 
def random_balls(mx=5):
    'Select from 1 to mx balls of each colour, randomly'
    balls = sum(([[colour] * random.randint(1, mx)
                 for colour in colours_in_order]), [])
    random.shuffle(balls)
    return balls
 
def main():
    # Ensure we start unsorted
    while 1:
        balls = random_balls()
        if not counting_sort_check(balls):
            break
    print("Original Ball order:", balls)
    counting_sort(balls)
    print("Sorted Ball Order:", balls)
    assert counting_sort_check(balls), 'Whoops. Not sorted!'
 
if __name__ == '__main__':
    main()<jupyter_output>Original Ball order: ['Blue', 'Blue', 'White', 'Blue', 'Red', 'White', 'Red', 'White', 'White', 'Blue', 'Red', 'Red', 'Blue']
Sorted Ball Order: ['Red', 'Red', 'Red', 'Red', 'White', 'White', 'White', 'White', 'Blue', 'Blue', 'Blue', 'Blue', 'Blue']<jupyter_text>**Quick Sort**<jupyter_code>def quicksort(items):
    less = []
    more = []
    pivotlist = []
    
    if(len(items)<=1):
        return items
    else:
        pivot = items[0]
        for i in items:
            if (i<pivot):
                less.append(i)
            elif (i>pivot):
                more.append(i)
            else:
                pivotlist.append(i)
        less = quicksort(less)
        more = quicksort(more)
        return less + pivotlist + more
                
a = [4, 65, 2, -31, 0, 99, 83, 782, 1]
a = quicksort(a)
print(a)<jupyter_output>[-31, 0, 1, 2, 4, 65, 83, 99, 782]<jupyter_text>Jeremy's version<jupyter_code>import statistics

def quicksort(myList, start, end):
    if start < end:
        # partition the list
        pivot = partition(myList, start, end)
        # sort both halves
        quicksort(myList, start, pivot-1)
        quicksort(myList, pivot+1, end)
    return myList

def partition(myList, start, end):
    pivot = 0
    left = start+1
    right = end
    done = False
    while not done:
        while left <= right and myList[left] <= pivot:
            left = left + 1
        while myList[right] >= pivot and right >=left:
            right = right -1
        if right < left:
            done= True
        else:
            # swap places
            temp=myList[left]
            myList[left]=myList[right]
            myList[right]=temp
    # swap start with myList[right]
    temp=myList[start]
    myList[start]=myList[right]
    myList[right]=temp
    return right

a = [-6, 65, 2, -31, 0, -99, 83, 782, 1]
a = quicksort(a, 0, len(a)-1)
print(a)<jupyter_output>[-99, -31, -6, 0, 2, 65, 83, 782, 1]<jupyter_text>**Shell Sort**<jupyter_code>def shell(seq):
    increment = len(seq) // 2
    while increment:
        for i, el in enumerate(seq):
            while i >= increment and seq[i - increment] > el:
                seq[i] = seq[i - increment]
                i -= increment
            seq[i] = el
        increment = 1 if increment == 2 else int(increment * 5.0 / 11)
 
data = [22, 7, 2, -5, 8, 4]
shell(data)
print(data)
def next_increment(i):
    return (i-1)//2
def first_increment(n):
    i =1
    while i<n:
        i=2*i+1
    return next_increment(i)
def shell(A):
    i = first_increment(len(A))
    while i >0:
        for j in range(0,len(A)-1):
            t,k = A[j], j
            while k >=i and t<A[k-i]:
                A[k], k = A[k-i], k-i
            A[k] = t
        i= next_increment(i)

data = [22, 7, 2, -5, 8, 4]
shell(data)
print(data)<jupyter_output>[-5, 2, 7, 8, 22, 4]<jupyter_text>**Exercises**<jupyter_code>def partition(A):
    u, p = 0,len(A)-1
    while(u!=p):
        if(A[u]<0):
            u = u+1
        else:
            A[u], A[p] = A[p], A[u]
            p = p-1
    return A

data = [-22, -7, -2, -5, 8, 4]
partition(data)
print(data)

def partition(a,p):    
    left = 1
    right= len(a)-1
    pivot = p
    while(True):
        while(a[left]< a[pivot]):
            left = left +1
        while (a[right]>a[pivot]):
            right = right -1
        if(left>=right):
            a[right], a[0] = a[0], a[right]
            return right
        a[left], a[right] = a[right], a[left]

data = [-22, 7, -22, -52, 8, 4]

print(partition(data,0))
print(data)
def quickselect(a,k):
    pivot = 0
    i = partition(a,pivot)
    left =i-1
    right =i+1
    if(k<left):
        quickselect(a[:i],k)
    elif(k<right):
        return a[k]
    else:
        quickselect(a[i:],k)

data = [-22, 7, -2, -52, 8, 4]
print(quickselect(data,3))<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.15370321210512344, 'fraction_numerical': 0.02477656844527033, 'mean_word_length': 2.535189239912418, 'pattern_counts': {'":': 0, '<': 52, '<?xml version=': 0, '>': 42, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, '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': '9', 'dir': 'jupyter-structured-clean-dedup', 'id': '237835', 'license': 'MIT', 'n_tokens_mistral': 4480, 'n_tokens_neox': 4123, 'n_words': 1214, 'path': '_site/notebooks/Theory Seminar 4.ipynb', 'repo_name': 'nmatra/nmatra.github.io', 'size': '11301'}