# Sorting by Nguyen Ngoc Huy

### Snippet options

Copy snippet: For this you need a free my code stock.com account.
Embed code : You will find the embed code for this snippet at the end of the page, if you want to embed it into a website or a blog!

```'''
Insertion sort (2.2.2)
Start from 2nd element (i=1). As long as the elem to the left is bigger than the current value, the current value become the larger value. The smaller value keeps going back to the left until it hits a smaller elem.
'''
import random

def insertion_sort(unsorted):
for i in range(len(unsorted)-1):
smallest = min(unsorted[i:len(unsorted)])
for j in range(i, len(unsorted)):
if unsorted[j] == smallest:
unsorted[i], unsorted[j] = unsorted[j], unsorted[i]
continue
return unsorted

a = random.sample(range(100), 10)
print('beginning: %s' %a)
new_a = insertion_sort(a)
print('result: %s' %new_a)

'''
Merge sort (recursive)
Have a helper function which merges 2 lists into 1, sorted. it does so by taking each candidate from each list and compare them. the smaller goes into the result list, the bigger stays and faces the next candidate from the other team. both have a infinity at the end to indicate the end of list.
Then, in the main function, split the array into 2 halves, then recursively call helper to sort those 2.
'''
a = [1,6,2,3,5,7,8,4,7,9]

def merge(left, right):
left_length = len(left)
right_length = len(right)
left.append(float('inf'))
right.append(float('inf'))
result = []
i = 0
j = 0
while i < left_length or j < right_length:
if left[i] > right[j]:
result.append(right[j])
j += 1
else:
result.append(left[i])
i += 1
return result

def merge_sort(an_array):
if len(an_array) == 1: return an_array
elif len(an_array) == 2:
if an_array[0] > an_array[1]:
return [an_array[1], an_array[0]]
else: return an_array
elif len(an_array) >= 3:
mid = int(len(an_array) / 2)
left = an_array[:mid]
right = an_array[mid:]
return merge(merge_sort(left), merge_sort(right))

print(merge_sort(a))

'''
bubble sort
'''
def bubble(a):
not_sorted = True
while not_sorted:
not_sorted = False
for x in range(len(a)-1):
if a[x] > a[x+1]:
not_sorted = True
a[x], a[x+1] = a[x+1], a[x]
return a

'''
Quicksort
'''
def qs(a):
if len(a) > 1:
less = []
equal = []
bigger = []
pivot = a[0]
for x in a:
if x < pivot:
less.append(x)
elif x == pivot:
equal.append(x)
else:
bigger.append(x)
return qs(less) + equal + qs(bigger)

'''
Selection sort
start by taking the entire array. Find smallest. Then find index of smallest and swap smallest with the first elem. Then narrow down the array, now excluding the first elem in the previous array.
'''
def selection_sort(unsorted):
for i in range(len(unsorted)-1):
smallest = min(unsorted[i:len(unsorted)])
for j in range(i, len(unsorted)):
if unsorted[j] == smallest:
unsorted[i], unsorted[j] = unsorted[j], unsorted[i]
continue
return unsorted

```

### Create a free my code stock.com account now.

my code stok.com is a free service, which allows you to save and manage code snippes of any kind and programming language. We provide many advantages for your daily work with code-snippets, also for your teamwork. Give it a try!

You can customize the height of iFrame-Codes as needed! You can find more infos in our API Reference for iframe Embeds.