In [16]:
alist = [5,3,5,0,54,2,6,26,6,2,66,2,1,9]
print "Original list: ", alist
bubble_sort(alist)
print "Sorted list: ", alist
In [15]:
def swap(alist,i,j):
temp = alist[i]
alist[i] = alist[j]
alist[j] = temp
def bubble_sort(alist):
length = len(alist)
for i in range(length):
for j in range(i+1,length):
if alist[i] > alist[j]:
swap(alist,i,j)
return alist
In [17]:
alist = [5,3,5,0,54,2,6,26,6,2,66,2,1,9]
print "Original list: ", alist
selection_sort(alist)
print "Sorted list: ", alist
In [13]:
def selection_sort(alist):
lenght = len(alist)
for i in range(lenght):
current_min_pos = i
for j in range(i+1,lenght):
if alist[current_min_pos] > alist[j]:
current_min_pos = j
swap(alist,i,current_min_pos)
In [5]:
alist = [5,3,5,0,54,2,6,26,6,2,66,2,1,9]
print "Original list: ", alist
merge_sort(alist,0,len(alist)-1)
print "Sorted list: ", alist
In [2]:
def merge_sort(alist, lower_limit, upper_limit):
if lower_limit < upper_limit:
middle = (lower_limit+upper_limit)//2
merge_sort(alist,lower_limit,middle)
merge_sort(alist,middle+1,upper_limit)
merge(alist,lower_limit,middle,upper_limit)
def merge(alist,low,middle,high):
helper = [0]*len(alist)
for i in range(low,high+1):
helper[i] = alist[i]
helperLeft = low
helperRight = middle+1
current = low
while helperLeft<=middle and helperRight<=high:
if helper[helperLeft] <= helper[helperRight]:
alist[current] = helper[helperLeft]
helperLeft += 1
else:
alist[current] = helper[helperRight]
helperRight += 1
current += 1
remaining = middle - helperLeft
for i in range(0,remaining+1):
alist[current+i] = helper[helperLeft+i]
In [9]:
alist = [5,3,5,0,54,2,6,26,6,2,66,2,1,9]
print "Original list: ", alist
merge_sort(alist,[0]*len(alist), 0,len(alist)-1)
print "Sorted list: ", alist
In [7]:
def merge_sort(alist, helper, lower_limit, upper_limit):
if lower_limit < upper_limit:
middle = (lower_limit+upper_limit)//2
merge_sort(alist,helper,lower_limit,middle)
merge_sort(alist,helper,middle+1,upper_limit)
merge(alist,helper,lower_limit,middle,upper_limit)
def merge(alist,helper,low,middle,high):
for i in range(low,high+1):
helper[i] = alist[i]
helperLeft = low
helperRight = middle+1
current = low
while helperLeft<=middle and helperRight<=high:
if helper[helperLeft] <= helper[helperRight]:
alist[current] = helper[helperLeft]
helperLeft += 1
else:
alist[current] = helper[helperRight]
helperRight += 1
current += 1
remaining = middle - helperLeft
for i in range(0,remaining+1):
alist[current+i] = helper[helperLeft+i]
In [20]:
alist = [5,3,5,0,54,2,6,26,6,2,66,2,1,9]
print "Original list: ", alist
quick_sort(alist,0,len(alist)-1)
print "Sorted list: ", alist
In [19]:
def quick_sort(lista, left, right):
if left < right:
index = partition(lista, left, right)
quick_sort(lista,left,index-1)
quick_sort(lista,index+1,right)
def partition(lista, left, right):
pivotIndex = left
pivot = lista[pivotIndex]
for index in range(left+1,right+1):
if lista[index]<pivot:
pivotIndex += 1
swap(lista,pivotIndex,index)
swap(lista,left,pivotIndex)
return pivotIndex
def swap(lista, left, right):
temp = lista[left]
lista[left] = lista[right]
lista[right] = temp
In [22]:
alist = [5,3,5,0,54,2,6,26,6,2,66,2,1,9]
print "Original list: ", alist
radix_sort(alist)
print "Sorted list: ", alist
In [21]:
def radix_sort(alist):
RADIX = 10
digit , placement = -1, 1
maxLength = False
while not maxLength:
maxLength = True
buckets = [list() for _ in range(10)]
for item in alist:
digit = item / placement
buckets[digit % RADIX].append(item)
if maxLength and digit>0:
maxLength = False
index = 0
for bucket in buckets:
for item in bucket:
alist[index] = item
index += 1
placement *= RADIX