Algorithms and Data Structures
Excercise 9
Sort 2 (The Fastest Method)

This exercise explains the quick sort.

Problem 1PostScript for printing

(1) Sort the following sequence by using merge sort. Also, write the state of sequence at all stages of the calculation process.

5 1 4 3 8 2 6 7

(2) The following code is a function which performs quick sort and comment lines. Write which comment corresponds to which portion of the program for every comment.
クイックソート関数

(3) Divide the following sequence using partition procedure equivalent to that of function (2).

5 7 3 6 2 8 1

マージソートの性質

マージソート


クイックソートの分割

Problem 2

Write the function which performs quick sort. A program should fulfill the following conditions:

Problem 3

There is a mistake in the quicksort function written in the textbook. When data fulfills certain conditions, it may be unable to sort well. Consider conditions in case of which the function doesn't work well. And correct the program.


The original Japanese document was written by Naoki Wakamatsu.
The translated document was written by Kenichi Maezu <m5061121@u-aizu.ac.jp>
and Hajime Matsui <m5061122@u-aizu.ac.jp> and checked by L. Pichl.