Algorithms -- 2009-2010 -- info.uvt.ro/Laboratory 4

Quick links: front; laboratories agenda, 1, 2, 3, 4, 5, 6, 7, evaluation, tools, references.

Exercises

Start solving the assignment below.

Assignment

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

---

Ciprian Dorin Crăciun, ccraciun@info.uvt.ro