lab 6: searching and sorting

EN47/COMP9, Fall 2009

Out: October 29, 3:00pm
Due: November 12, 3:00pm

the problem

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). 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.

part 1: bubble sort

For the first part of this assignment, your 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 ]

Below is a generic outline of the bubble sort algorithm. Refer to your class notes for specific implementation details.

  • LOOP over all elements in the array (first to last)

    • LOOP over all elements in the array (first to last)

      • VISUALIZE the array
      • WAIT
      • IF the current element should be swapped with the next element
        • Swap the values of the current and next element
  • VISUALIZE the final array

part 2: linear search

For the second part of the assignment, you should enable the user to search for numbers in the sorted array. For example: 

    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

Below is an outline of the linear search algorithm. Note that this is slightly different from (but equivalent to) the one in the class notes.

  • INITIALIZE return value to -1
  • FOR each element in the array

    • VISUALIZE the array
    • WAIT
    • IF the current element is equal to the target value
      • Set the return value to the current position
      • BREAK out of loop
  • RETURN the return value

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:

  • void bubble_sort(int A[], int size): This function should use the bubble sort algorithm to sort all the elements of array A. The number of elements in the array is given by the size parameter.
  • int linear_search(int A[], int size, int target): This function should use the linear search algorithm to find target among the size elements of array a. The return value is the position of target, or -1 if it is not in the array.

getting started

  1. First, write down detailed pseudocode for the bubble sort and linear search algorithms on paper. You may start from the outlines given above. We will collect your write-ups for 10% of your lab grade.
  2. When you are ready to start writing code, create a directory for today's lab (lab6) and a cd into it. You will need to copy several files into your lab6 directory, either from the website or by using the command

    cp /comp/9/public_html/lab/lab6/* .

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

  3. For LEDA to be loaded correctly, run the following instructions once at the command line: use leda
  4. Open bubbles.cpp. This will be the file that you edit and hand in. Right now it contains some skeleton code.
  5. 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.

visualization

There is one new LEDA function that you will use to do all the visualization for this lab:

void draw_histogram(int A[], int size, int current)

This function draws a histogram representing the values of the integers in array A. The height of each bar corresponds to the value of an element in the array. The number of elements in the array is given by the size parameter. The current parameter tells the function which index of the array you are currently searching or sorting. The current bar will be drawn in a different color than the other bars.

testing & handing in

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? You can run the solution program (lab6_sol) with the same input to test your program. When you are satisfied with your program, submit it using provide:

provide comp9 lab6 bubbles.cpp

extra credit

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 10% 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.

For an additional 10% 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.

When you are confident that your extra credit program works correctly, submit it using provide:

provide comp9 lab6ec bubbles_extra.cpp