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

Question 2

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

• A sequence is initialized when it is declared.
• The program lets the user to choose the sorting method.
• The program displays both the result and sorting process.

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:

• Number of a data is 100000.
• The data are constructed by random numbers.
• The same data is used in the case of insertion sort and the case of shell
• The program has not to display the result and the sorting process.
• Use the function gethrtime() for the actual time measurement.

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