sorting algorithms

https://www.youtube.com/watch?v=GUDLRan2DWM&index=2&list=PL2_aWCzGMAwKedT2KfDMB9YA5DgASZb3U

#Bubble sort: O(n^2)
http://www.geekviewpoint.com/python/sorting/bubblesort
#!/usr/bin/env python
def bubblesort( A ):
  for i in range( len( A ) ):
    for k in range( len( A ) - 1, i, -1 ):
      if ( A[k] < A[k - 1] ):
        swap( A, k, k - 1 )
        #break

def swap( A, x, y ):
  tmp = A[x]
  A[x] = A[y]
  A[y] = tmp

A = [3,1,5,4]

def main():
    bubblesort(A)
    print A

if __name__ == '__main__':
    main()

# insertion sort : O(n^2)

#!/usr/bin/env python
def insertionsort( aList ):
  for i in range( 1, len( aList ) ):
    tmp = aList[i]
    k = i
    while k > 0 and tmp < aList[k - 1]:
        aList[k] = aList[k - 1]
        k -= 1
    aList[k] = tmp
A = [3,1,5,4]

def main():
    insertionsort(A)
    print A

if __name__ == '__main__':
    main()

# Selection sort : O(n^2):
#!/usr/bin/env python
def selectionsort( aList ):
  for i in range( len( aList ) ):
    least = i
    for k in range( i + 1 , len( aList ) ):
      if aList[k] < aList[least]:
        least = k

    swap( aList, least, i )


def swap( A, x, y ):
  tmp = A[x]
  A[x] = A[y]
  A[y] = tmp

A = [3,1,5,4]

def main():
    selectionsort(A)
    print A

if __name__ == '__main__':
    main()

# Merge sort: Time complexity: O(n log n):


# Quick Sort
import random

 

def quicksort( aList ):

    _quicksort( aList, 0, len( aList ) - 1 )

 

def _quicksort( aList, first, last ):

    if first < last:

      pivot = partition( aList, first, last )

      _quicksort( aList, first, pivot - 1 )

      _quicksort( aList, pivot + 1, last )

 

 

def partition( aList, first, last ) :

    pivot = first + random.randrange( last - first + 1 )

    swap( aList, pivot, last )

    for i in range( first, last ):

      if aList[i] <= aList[last]:

        swap( aList, i, first )

        first += 1

 

    swap( aList, first, last )

    return first

 

 

def swap( A, x, y ):

  A[x],A[y]=A[y],A[x]