2016-12-13

posted Dec 13, 2016, 6:55 AM by Samuel Konstantinovich   [ updated Dec 13, 2016, 9:05 AM ]
Quiz Friday!
-Some ArrayList problems
-Some runtime problems
-Some general Java problems
-Nothing specific to Barcode 

Here are some more examples about the various runtimes we spoke on yesterday:
https://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/


Sorts!  
You will be creating a class Sorts, that will contain many different static sorting methods.

New Git Folder:
MKS21X/04Sorts/ 
Note - This will be updated throughout the semester, and you will copy it over to start an assignment next semester.

Here are visualizations to help you see what is going on:
You should probably bookmark this page for future sorting assignments.

Note: We should write this as a sort that works on an array of comparables, but that adds an extra layer of difficulty. We will deal with this later and only focus on the sorting algorithm now. 

Schedule:
Today: Selection Sort
Tomorrow: Insertion Sort

Selection Sort
The selection sort is an in-place sorting algorithm. It modifies an array in the following way:

For each index i of the array, starting with the first index:
-Find the smallest element located at index i or any of the higher indicies.
-Swap that value into index i.
-Increase i and repeat until the last index.

Example on an array with 5 pieces of data:
[   64 25 12 22 11] // this is the initial, starting state of the array 
[11    25 12 22 64] // sorted sublist = {11} 
[11 12    25 22 64] // sorted sublist = {11, 12} 
[11 12 22    25 64] // sorted sublist = {11, 12, 22} 
[11 12 22 25    64] // sorted sublist = {11, 12, 22, 25} 
[11 12 22 25 64   ] // sorted sublist = {11, 12, 22, 25, 64}

public class Sorts{
  /**EDIT THIS METHOD TO MATCH YOUR NAME 
  */
  public static String name(){
    return "01.Last.First"; 
  }

  /**Selection sort of an int array. 
  *Upon completion, the elements of the array will be in increasing order.
  *@param data  the elements to be sorted.
  */
  public static void selectionSort(int[] data){  }

}




Comments