#!/usr/bin/env python

# -*- coding:UTF-8 -*-

‘‘‘CLRS p10‘‘‘

def insertion_sort(A):

    for j in range(1,len(A),1):

        key = A[j]

        i = j-1

        while i >= 0 and A[i] > key:

            A[i+1] = A[i]

            i = i-1

        A[i+1] = key

if  __name__ == ‘__main__‘:

    A = [9,3,5,2,3,5,7,8,9,1]

    insertion_sort(A)

#!/usr/bin/env python

# -*- coding:UTF-8 -*-

‘‘‘CLRS p16‘‘‘

def selection_sort(A):

    i = 0

    while i < len(A)-1:

        minIndex = i

        minA = A[i]

        for j in range(i,len(A),1):

            if minA > A[j]:

                minA = A[j]

                minIndex = j

        tmp = A[i]

        A[i] = A[minIndex]

        A[minIndex] = tmp

        i += 1

if  __name__ == ‘__main__‘:

    A = [9,3,5,2,3,5,7,8,9,1]

    selection_sort(A)

#!/usr/bin/env python

# -*- coding:UTF-8 -*-

import math

‘‘‘CLRS p16‘‘‘

def merge(A,p,q,r):

    n1 = q - p + 1

    n2 = r - q

    L = A[p:q+1]

    R = A[q+1:r+1]

    L.append(float("inf"))

    R.append(float("inf"))

    i = 0

    j = 0

    for k in range(p,r+1,1):

        if L[i] <= R[j]:

            A[k] = L[i]

            i +=1

        else:

            A[k] = R[j]

            j += 1

def merge_sort(A,p,r):

    if p < r:

        q = math.floor((p+r)/2)

        merge_sort(A,p,q)

        merge_sort(A,q+1,r)

        merge(A,p,q,r)

if  __name__ == ‘__main__‘:

    A = [9,3,5,2,3,5,7,8,9,1,11,20,0,2]

    print(A)

    merge_sort(A,0,len(A)-1)

    print(A)

#!/usr/bin/env python

# -*- coding:UTF-8 -*-

‘‘‘CLRS p23‘‘‘

def bubble_sort(A):

    for i in range(0,len(A)-1,1):

        for j in range(len(A)-1, i,-1):

            if A[j] < A[j-1]:

                tmp = A[j]

                A[j] = A[j-1]

                A[j-1] = tmp

if  __name__ == ‘__main__‘:

    A = [9,3,5,2,3,5,7,8,9,1,11,20,0,2]

    bubble_sort(A)