list<int> insert(int element, list<int> lis) { if (lis.size() == 0) { lis.push_front(element); return lis; } else if (element > *lis.begin()) { int first = *lis.begin(); lis.pop_front(); list<int> inserted = insert(element, lis); inserted.push_front(first); return inserted; } else { lis.push_front(element); return lis; } } list<int> insertionsort(list<int> lis) { if (lis.size()==0) return lis; else { int first = *lis.begin(); lis.pop_front(); list<int> sorted = insertionsort(lis); return insert(first, sorted); } }
NOT YET IMPLEMENTED IN CPP def flatten(lis) if lis.length == 0 then [] elsif lis[0].class != Array then [lis[0]] + flatten(lis[1..lis.length-1]) else return flatten(lis[0]) + flatten(lis[1..lis.length-1]) end end y = [5, 2, [16, [20, 1]], 30, [[[2]]]] print flatten(y), "\n"
def partition(lis) part(lis[1..lis.length-1], lis[0]) #((<= part) part (> part)) will be returned end def part(lis, pivot) if lis.length==0 then [[]] + [pivot] + [[]] else r = part(lis[1..lis.length-1], pivot) # recursive call which will # return a list with structure # ( (<= pivot) pivot (> pivot)) #r if lis[0] > pivot then # add to > list [r[0]] + [pivot] + [[lis[0]] + r[2]] else # add to <= list [[lis[0]] + r[0]] + r[1..r.length-1] end end end x = [6,3,4,9,10,1,7] #OR from irb: partition(x) will print the answer as a list print x, "\n" #y = [1,2,10,12] y = [] part(y,6) #print partition(x), "\n"Now, using the above partition function, try to write quicksort. A soln is here but don't look until you have tried it!