- Insertion sort:
def insertion(lis):
if len(lis) == 0:
return []
else:
return insert(lis[0], insertion(lis[1:]))
def insert(element, lis):
if len(lis)==0:
return [element]
elif element>lis[0]:
return [lis[0]] + insert(element, lis[1:])
else:
return [element] + lis
x = [1,3,4,9,10,11,17]
y = [5, 2, 16, 20, 1, 30, 2]
print x
print insert(6,x)
print insertion(y)
- List flattening
def flatten(lis):
if len(lis) == 0:
return []
elif type(lis[0]) != list:
return [lis[0]] + flatten(lis[1:])
else:
return flatten(lis[0]) + flatten(lis[1:])
y = [5, 2, [16, [20, 1]], 30, [[[2]]]]
print flatten(y)
- Partition function for quicksort
def partition(lis):
return part(lis[1:], lis[0]) #((<= part) part (> part)) will be returned
def part(lis, pivot):
if len(lis)==0:
return [[]] + [pivot] + [[]]
else:
r = part(lis[1:], pivot) # recursive call which will
# return a list with structure
# ( (< pivot) pivot (> pivot))
if lis[0] > pivot: # add to > list
return [r[0]] + [pivot] + [[lis[0]] + r[2]]
else: # add to <= list
return [[lis[0]] + r[0]] + r[1:]
x = [6,3,4,9,10,1,7]
print x
y = [1,2,10,12]
#print part(y,6)
print partition(x)
Now, using the above partition function, try to write quicksort. A
soln is here but don't look until you have tried it!