lab 6: searching and sorting

COMP10, Summer 2010

Out: Tuesday, August 3, 9:00 AM
Due: Thursday, August 5, 12:30 PM

overview

In this lab, you will write a program to animate searching in and sorting of an array. The user will enter 10 integers between 0 and 20 in a random order. Your program should sort the integers into ascending order using the bubble sort algorithm and print the sorted array. You should also enable the user to search for a particular number in the array. Your program should use linear search and report the position in the array where the number was found (the array index). The program interaction should look something like below: 

    This program will first sort an array of 10 integers and then allow
    the user to search for values within the array.

    Please enter 10 integers between 0 and 20, followed by RETURN:
    4 2 7 10 5 9 5 8 1 2

    Sorted data: [1 2 2 4 5 5 7 8 9 10 ]

    Enter a number to search for: 8
    8 was found at position 7.

    Search for another number? (y/n) y

    Enter a number to search for: 6
    6 was not found.

    Search for another number? (y/n) n

Please refer to your class notes for sample pseudocode for these two algorithms. As in Lab 5, you will use LEDA to animate your algorithms. You should visualize your array as a histogram (bar chart) in which the height of each bar corresponds to the value of an element in the array.

Your program is worth 20 points. Submit your code to be graded by emailing your .cpp files to mary_c.sullivantufts.edu, and also hand in a code print-out in class.

the program

As the focus of this lab is on the searching and sorting algorithms, we are providing some working code so that you will only have to implement the following two functions: bubble_sort() and linear_search().

  1. To get started, create a directory for today's lab (lab6) and a cd into it. Copy the starter files into your lab6 directory, either from the website or by using the command

    cp /comp/10EXP/public_html/hw/lab6/* .

    This will copy four files into your directory: bubbles.cpp, visualize.cpp, lab6_sol, and Makefile.

  2. For LEDA to be loaded correctly, run the following instructions once at the command line: use leda
  3. Open bubbles.cpp. This will be the file that you edit and hand in. Right now it contains some skeleton code.
  4. Before making any changes, try compiling the skeleton code by typing make at the command line. This creates an executable program named bubbles in your current directory. Run the program by typing ./bubbles at the command line. You will be prompted to enter the values for an array, and then you should see the histogram appear in a LEDA window.

There is one new LEDA function, draw_histogram, that you will use to create graphics. This function draws a histogram (or bar chart) representing the values of the integers in an array. The height of each bar corresponds to the value of an element in the array. The parameters of the function are an array, its size, and the current position (i.e. which element you are pointing to at this iteration of the searching or sorting algorithm). The current bar will be drawn in a different color than the other bars. Run the sample solution (./lab6_sol) to see what the animation looks like.

Test your code with a variety of inputs. Try an array that is already sorted and try an array that is sorted in reverse order. Test your search function as well. Does it always find an answer, even if the target is the first or last element in the array?

extra credit

  1. After one iteration of the bubble sort algorithm, we know that the largest element will have bubbled its way to the last position in the array. Likewise, after the second iteration, we know that the second largest element will occupy the second to last position. In general, after every iteration, we can safely ignore another element in the array. For 2 points of extra credit, modify your bubble sort to be more efficient. Instead of sorting the entire array every time, change your algorithm so that it sorts one less element every iteration.
  2. For an additional 1 point of extra credit, modify your bubble sort algorithm so that it keeps track of the total number of comparisons and swaps necessary to sort the array. Your bubble_sort function should print these statistics after it finishes sorting:

    Total comparisons: 45
    Total swaps: 24

Make any extra credit changes in a copy of your code: bubbles_extra.cpp. Compile this program with the command make extra. This creates an executable named bubbles_extra which you can run by typing ./bubbles_extra.