Algorithms -- 2009-2010 -- info.uvt.ro/Laboratory 4
Jump to navigation Jump to search
Start solving the assignment below.
For submission please follow: assignment 3.
- insertion1 / inserţie;
- selection / selecţie;
- bubblesort1 / interschimbări1;
- bubblesort2 / interschimbări2;
And for each run of the algorithm, you should count and display:
- the resulting sorted vector;
- the number of comparisons (related to the vector elements);
- the number of assignments (related to the vector elements);
Source code skeleton (rough idea, not mandatory):
def insertion1 (v) : # we make a copy of the initial vector in order not to modify it v = list (v) cc = 0 # comparison count ac = 0 # assignment count ... # algorithm implementation return (v, cc, ac) def selection (v) : ... # the same as above def bubblesort1 (v) : ... # the same as above def bubblesort2 (v) : ... # the same as above v = input ("v = ") r1, cc1, ac1 = insertion1 (v) r2, cc2, ac2 = selection (v) r3, cc3, ac3 = bubblesort1 (v) r4, cc4, ac4 = bubblesort2 (v) print "for insertion" print " -> number of comparisons =", cc1 print " -> number of assignments =", ac1 ... # the same prints for each algorithm