LAB 10

Bubble Sort using lists and random numbers and Pseudo code

For this lab, download lab10.a2w to your Z-drive, or some other place on your hard drive. This is an incomplete file that you have to finish.

Extra information on BubbleSort

• Wikipedia page
• Bubble sort in 29 languages
• Bubble sort demo

• At the start six guys are presented on the screen all standing in the same place.
• Each guy is assigned a unique random distance between 0 and 5 meters. The guys then spread out a meter apart and backup the assigned distance.
• The program then rearranges (sorts) the guys by their distance with the closet on the left and the farthest away on the right.
• The program will use a Bubble sort algorithm to sort the guys. The pseudo code is given in part 3.

Part 1 - Build a random list of unique numbers

The first thing is to build a random list for the assigned values. There is an empty list declared in the file named movList. This list will hold the random amount for each guy to move backward. You job is to write code to fill this list with unique random numbers.

For example [2,4,0,5,1,3]. No repeating numbers.

1. Take out a piece of paper and write pseudo code for creating the list.
   
   Hint:
   Remember Lists can have elements inserted and removed from them. You cannot set the value of an item in a list (that I have found). There are hints in other methods of the code.
2. Class discussion for pseudo code.
3. Write the Alice code to implement the pseudo code and complete the rndList method already started in the supplied program.

Part 2 - Create a swap method

Part of sorting a list requires the ability to swap the places of elements within a list. For example; [2,1,3] becomes [1,2,3] if we swap the positions of the first two elements. The swap method will take in two numbers representing the two elements in the list that you want to swap places. The final method will need to take in two element positions, a list of numbers and a list of objects. The method will swap the elements in the numbers list and then perform the same swap in the objects list. You job is to write code to complete the swap method already started in the supplied program.

For example: list = [2,4,0,5,1,3]; calling swap(1,2, list) will give list = [2,0,4,5,1,3].

1. Take out a piece of paper and write pseudo code for creating the swap method.
   
   Hint:
   Remember Lists can have elements inserted and removed from them. You cannot set the value of an item in a list (that I have found).
2. Class discussion for pseudo code.
3. Write the Alice code to implement the pseudo code and complete the swap method already started in the supplied program.

Most examples of swap are shown using arrays.

  For array A[]:
      temp = A[i]
      A[i] = A[i+1]
      A[i+1] = temp

Alice has a bug in its array methods that does not allow setting an array element to a variable value. We are using lists with insert and remove instead of arrays with set value.

Part 3 - Bubble Sort (Extra Credit)

A sorting algorithm takes a list of numbers and sorts them into numerical order. Bubble sort is a simple sorting algorithm. It works by repeatedly stepping through the list to be sorted, comparing two items at a time and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which means the list is sorted.

Example: 5 1 4 2 8 - unsorted array; 1 4 2 5 8 - after one pass; 1 2 4 5 8 - sorted array

  Sort all the elements of a list
  Loop through all the elements till sorted
      Sort a single element
      For a given element, if the next element is smaller swap places
      Keep checking the element till it stops moving
  Grab the next element and repeat

  Boolean swapped = true     // Need a variable to tell when the list is sorted.
  bubbleSort Method;
    while swapped            // this will loop till all elements are sorted
      set swapped to false   // to stop loop if nothing gets swapped = list sorted
      //sort a single element
      for each element in the list
        if the next element is smaller
          have the guys on screen change positions  // specific to this Alice problem
          swap places of the elements in the list   // call the swap method
          set swapped to true to check again
        end of if
      end of for loop
    end of while loop
  end of method

1. Class discussion for pseudo code.
2. Write the Alice code to implement the pseudo code and complete the bubbleSort method already started in the supplied program.