Algorithms -- 2009-2010 -- info.uvt.ro/Laboratory 4
Quick links: front; laboratories agenda, 1, 2, 3, 4, 5, 6, 7, evaluation, tools, references.
Exercises
[edit]Start solving the assignment below.
Assignment
[edit]For submission please follow: assignment 3.
From the 6'st course (for en), or 6'st course (for ro), implement the following sorting algorithms:
- 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