COP 2500 Spring 2012

Lab #7: Searching and Sorting

Home Labs Lecture Notes
 
Deliverables: To complete this assignment you must --

  1. Email your instructor showing what you have completed. You can get partial credit even if not fully completed with the lab.

Introduction: The goal of this assignment is to give you experience with implementing algorithms in code, specifically searching and sorting arrays. Start here. Save the page as your starting html document, before beginning the assignment.

Initialization: Randomly initialize a list of size 200 with integer values between 0 and 100.
Part 1: Search
You are to implement a function which searches a list for an occurence of a value. It should not depend on the list being pre-sorted. You may not use Array's indexOf().
or Array's sort().

Search

Section Specification Comments
INPUT: list, value An initialized list
COMPUTATION:
  1. Loop over all elements in list.
    • If current element equals value, store as index.
  2. If value not found, ensure index is -1.
RETURN: index -1 if value not found
  1. Prompt the user once for an element (an integer from 0 to 100) to search for.
  2. Call your search function with the number to search for and the list.
  3. Display whether the number was found, and if found, a location where it can be found within the list.
Part 2: Sort
You are to implement a function which sorts a list in ascending (0, 1, ...) order. You are not permitted to use Array's sort() method.
There are many ways to sort a list of which you may implement any method you see fit, provided it sorts a list in ascending order. Below describes Bubble Sort, one of the most straight-forward approaches to sorting.

Sort

Section Specification Comments
INPUT: list An initialized list
OTHER VARIABLES: swap
n 		Indicates if swap occurred.
How far to search in the list.
COMPUTATION:
  1. Set n to size of list - 1.
  2. Set swap to FALSE.
  3. Loop over element 0 through element n in the list.
    • If current element > next element
      1. Swap current element and next element.
      2. Set swap to TRUE.
  4. If swap is TRUE, repeat from step 2. n -= 1.
  5. If swap is FALSE, return the now sorted list.
 Gradually sorts a list.
nth item is correctly placed.
RETURN: list
  1. Call your sort function for your list. You are not permitted to call JavaScript's sort() method.
  2. Display the (sorted) list.