Courses‎ > ‎AP Computer Science‎ > ‎Konstantinovich‎ > ‎

2018-12-07

posted Dec 7, 2018, 6:03 AM by Konstantinovich Samuel   [ updated Dec 7, 2018, 6:33 AM ]
GOAL: Bubble sort


Recap: 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:
a-Find the smallest element located at index i or any of the higher indices.
b-Swap that value into index i.
c-Increase i
d- repeat a,b,c 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}


Bubble Sort

The bubble sort is really a bad sort, it is so bad that even politicians know it is bad

Here is a video of the bubble sort:

When writing sorts, you must debug by testing a known set of values and predicting the results as they happen.
Here are some bubble sort examples:



SLOW CASE:



FAST CASE:







Update your repo to include the bubble sort:

public class Sorts{
  /**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){  }


  /**Bubble 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 bubbleSort(int[] data){  }

}



Comments