Tölvunarfræði 2

Weekly note 9

Now we will start looking at simple sorting methods from Chapter 6 in the textbook. We will cover Selection sort, Insertion sort, and Bubble sort. These methods are easy to describe, but they are not very fast. We will analyse their performance, and then we will go onto a faster (but more complicated) method called Shell sort.

In the sections this week we will cover the last homework.

Problem set 8

Solve the following problems and put the solutions into your section teacher's box before noon monday March 14th. They will not accept solutions that arrive later.

Exercise 5.79 on page 249 in the textbook.
Exercise 1 on page 9 in CDSI.
Exercise 2 a) and c) on page 9 in CDSI.
Exercise 6.3 on page 272 in the textbook.
Implement in C++ binary insertion sort, which is just like normal insertion sort, except we use binary search to find the right location of the next item in the sorted part of the array. Compare its speed to the insertion sort given in the textbook (Program 6.3) on large enough arrays containing random numbers.
[Hint: See sample solution (only in icelandic) from last year. ]

Those that want more practice should try solving the following problems. Their solutions are all availableon the old homepages of the course. If you want an explanation of the solutions you can ask about them in your section.

Exercise 2 on weekly note 10 from spring 2002. This is a comparison between two versions of Insertionsort.
Exercise 3 on weekly note 10 from spring 2002. This is a comparison between two version of Bubblesort.
Exercise 5 on weekly note 10 from spring 2003. This is exercise 6.26 in the textbook.
Exercise 4 on weekly note 10 from spring 2001. This is exercise 6.30 in the textbook.

hh (hja) hi.is, March 7th, 2005.