CS3364 - Design and analysis of Algorithms, Summer I / 2004

Homework 2

This is due Friday, June 18, 2004, 10 am

Introduction

Professor M. need nice graphics to show his students how different sorting algorithms perform on different input. He uses gnuplot for the visualization. Unfortunately, he has no data available. You, his assistant, have been chosen to help him with this task.

Operation

Your program will read either from stdin or from a text file named sort.txt. The first line will contain a number n (where 1 < n < 10000). The next n lines will contain numbers x[i] to be sorted (where 0 < x[i] < 10000000).

The following lines will contain instructions for your program. Each line will contain two integer values a, b seperated by a space. The first value selects the sort algorithm according to this table:

  1. Insertion (with stop on found)
  2. Binary Insertion
  3. Bubble
  4. Selection
  5. Merge (In-Place)
  6. Quick (No optimizations, chose first as pivot()
  7. Heap
  8. Shell

The second value selects how much of the input data should actually be sorted. You should sort the first b elements from the input.

After sorting, your output should be:

  • A line starting with the # charachter and a space, followed by the sorted array (b elements)
  • A line containing the size of the sorted array (b), a space, the number of data comparisons, a space and the number of data read/writes (1 exchange = 2 readwrites)

You program should forget the sorted array after each output and use the unsorted for the next command

As a termination signal, the last line will contain 0 0

Sample Input

5
9
263
90
123
42
1 2
1 5
4 5
4 4
0 0

Sample Output

# 9 263
2 1 0
# 9 42 90 123 263
5 8 8
# 9 42 90 123 263
5 10 2
# 9 90 123 263
4 6 4

Misc notes

If you use the advance or exchange function from the notes, and it is called with the same parameter, exit, do not do anything, and do not count it

If you don't end up with exactly the same values, don't worry. I'll look at the code

Submission

Submit the programming part eletronically, either by putting them on the unix accounts in the cs department in a folder that I can read, or by sending them via email to max@berger.name