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

Jump to navigation
Jump to search

**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
```