Tina Comston
Comp-111 Week 12
Franklin University
Week 12
Preparation
    • Read Chapter 14 (sections 14.1 - 14.3, 14.6 - 14.8) in the COMP 111 Reading Guide.
      Guided Learning Activity
      Assignment - no homework assignment this week

      Concepts - Sorting and Searching

      In the reading this week you are presented with several sorting algorithms.  Each algorithm takes a different approach to sorting items, and each has a different efficiency associated with it - BUT each of the algorithms works.  You can copy the code directly from the book or reading guide, modify it to work with whatever you are sorting and it will work.

      Selection Sort YouTube example:
      https://www.youtube.com/watch?v=f8hXR_Hvybo

      Insertion Sort YouTube example:
      https://www.youtube.com/watch?v=DFG-XuyPYUQ

      Bubble Sort YouTube example:
      https://www.youtube.com/watch?v=8Kp-8OGwphY

      Using the Bubble Sort Algorithm

      Here is the third version of the Bubble Sort Algorithm copied directly from the reading guide:

      public static int[] bblSort3(int arr[], int left, int right)
      {
      boolean didSwap = true;
      int last = right-1;
      // continue as long as a swap happened in the last pass,
      // didSwap is a sentinel
      while (didSwap)
      {
      // assume the array is sorted
      didSwap = false;
      // Look at all the unsorted elements per pass
      for (int i=left; i<last; ++i)
      {
      // detect if the array was actually unsorted
      if (arr[i] > arr[i+1])
      {
      didSwap = true;
      int temp = arr[i];
      arr[i] = arr[i+1];
      arr[i+1] = temp;
      }
      }
      --last;
      }
      return arr;
      }


      Here's an explanation of the algorithm:

      public static int[] bblSort3(int arr[], int left, int right)
      • int[] - returns a sorted array of data type integer  (this can be changed to match whatever data type you have
      • int arr[] - the array that needs to be sorted of data type integer (again this can be changed)
      • int left - the lower boundary of the array (should be 0 if sorting the entire array)
      • int right - the upper boundary of the array (should be length - 1 if sorting the entire array)
      ***Note that the array can be changed to be an ArrayList.


      boolean didSwap = true;
      int last = right-1;
      // continue as long as a swap happened in the last pass,
      // didSwap is a sentinel
      while (didSwap)
      • didSwap - this boolean variable is used to indicate that some values have been reordered.  When the variable is false it indicates that nothing has been changed and the sort is complete.
      • last - this variable keeps track of the end of the array.  As items are sorted they "bubble" up to the end.  The end, therefore, doesn't need to be checked everything through as it is already sorted.  This variable says to only go this far in the array.

      didSwap = false;
      // Look at all the unsorted elements per pass
      for (int i=left; i<last; ++i)
      {
      • didSwap - inside the loop the didSwap variable is immediately set to false.  It will be set back to true if values are reordered.
      • for loop - work through all of the elements in the array from the left boundary up to the last variable

      // detect if the array was actually unsorted
      if (arr[i] > arr[i+1])
      {
      didSwap = true;
      int temp = arr[i];
      arr[i] = arr[i+1];
      arr[i+1] = temp;
      }
      • if statement - check to see if the value at position i is greater than the value at position i+1
      • didSwap - if the condition is true a swap will occur, set the variable to true
      • temp - put the value in position i into a temporary variable
      • arr[i] - set the element in position i equal to the element in position i+1
      • arr[i+1] - set the element in position i+1 equal to the value in the temp variable

      --last;
      • decrement the last variable, the value in position last has been sorted so it does not need to be checked any longer

      Using the algorithm

      The above algorithm works great with integer data stored in an array, but what if you have string data?
      You would need to:
      • Change the definition of the arr from int to String
      • Change the if statement to use the .compareTo() method which will return 1 if you need to swap the values.
      • Change the temp variable to have a data type of String
      What if you have an ArrayList and not an array?
      You would need to:
      • Change the definition of the array to be an ArrayList
      • Change the references of the array from arr[i] to use the .get(i) method.
      • When changing the values you would need to use the .set() method
      What if you have an object and you want to sort on an instance variable in the object?
      You would need to:
      • Change the definition of the array or ArrayList from int to the object data type.
      • Retrieve the value of the object from the element at position i.
      • Retrieve the value of the object from the element at position i+1
      • Compare the two values
      • Change the temp variable to have the data type of the object.
      Reflection Paper
      • Keep journaling.  It's almost type to take all of those journal entries and write your reflection paper.
      Lab 5
      • Although you have a couple of weeks to complete this lab, it's never a good idea to wait until the last minute.  Read through the instructions. Make sure you have a clear understanding of what is needed.