Algorithms and Data Structures
Exercise
Exercise 8 Sort (Slow methods)

Question 1 [PostScript for printing]

(1) Write the results and processes of sorting of the following sequence by
(a) bubble sort, (b) insertion sort and (c) selection sort.

9 6 7 1 2

(2) Write the result and process of sorting of the following sequence by shell sort.

5 1 4 3 8 2 6 7

Bubble Sort
Bubble
First scan
Bubble

Insertion sort
Insertion

Selection sort
Selection

Shell sort
Shell

Question 2

Write a program that sorts by bubble sort, insertion sort and selection sort. The program must fulfill the following conditions:

Example of executing¡§
% ./a.out
Before:  7 1 6 5 2 

Select a method (1:buble, 2:insertion: 3: selection) >  1
1 7 2 6 5 
1 2 7 5 6 
1 2 5 7 6 
1 2 5 6 7 
% ./a.out
Before:  7 1 6 5 2 

Select a method (1:buble, 2:insertion: 3: selection) >  2
1 7 6 5 2 
1 6 7 5 2 
1 5 6 7 2 
1 2 5 6 7 
% ./a.out
Before:  7 1 6 5 2 

Select a method (1:buble, 2:insertion: 3: selection) >  3
1 7 6 5 2 
1 2 6 5 7 
1 2 5 6 7 
1 2 5 6 7 
Question 3

Write a program that sorts by shell sort, and compare the calculation speed to insertion sort. The program must fulfill the following conditions:

Example of executing:
% ./a.out
insertion sort: elapsed time 316.239708.
shell sort: elapsed time ********.

Written by Naoki Wakamatsu.