Bubble Sort (Numbers Arrays)

Credit: Iterative Algorithms 1

Eventually, your goal will be to familiarize yourself with the following sort algorithms

• Bubble Sort (aka exchange sort)
• Selection Sort
• Insertion Sort

Part 1 - Altering and Using the Code

1. Create a new file called IA3_IntegerBubbleSort.java
2. Set up an empty int array that will hold 50 numbers.
3. Use a FOR loop and a random number generator to fill the 50 slots with random numbers up to 1000.
4. Println(“Unsorted Array”)
5. Print this array out on one line, separated by commas.
6. You should already have a BubbleSort method in your examples but it sorts in Descending order.  You must change this BubbleSort method to sort in Ascending order. Don’t have the example code, scroll down to Appendix B.
7. Use your BubbleSort method to sort the array
8. Print a couple of empty lines.
9. Println(“Sorted Array”)
10. Print the now sorted array out on one line, separated by commas.

Part 2 - Think about the following: (Not For Marks)

The question is, how to do you Bubble Sort an object?  The algorithm works the same but you must decide what to sort by and build a specific method for that type of sort.  Eg. For a Student class, you need a ‘Sort By Name’ and a ‘Sort by ID’.  

The other wrinkle is that more often than not, when using OOP, you use ArrayLists rather than Arrays.  ArrayList algorithms are sometimes shorter different than array algorithms as you can insert and delete items.  Find a Bubble Sort algorithm that sorts an ArrayList and just look for differences.  

Appendix A

Set Up for Students Doing these Assignments on their own time.

We will start with the bubble sort algorithm.  Begin by watching this visualization of many different algorithms: https://www.youtube.com/watch?v=kPRA0W1kECg 

Open your SearchAndSort.java file and add a comment section such as the following:

/***************************** Sort Algorithms *******************************************/.

//Bubble Sort

Read about Bubble Sort, watch a video and read a fun story using the algorithm:

The explanation: http://mathbits.com/MathBits/Java/arrays/Bubble.htm

The video is: Bubble Sort - http://www.youtube.com/watch?v=P00xJgWzz2c

The story is: Bullies, Bubble Sort and Soccer Tickets

1. In your own words explain how the BubbleSort works in a comment in your SearchAndSort.java class.   It should look like:  /* BubbleSort Question 1:  ___*/
2. In another comment, explain why the method in the first link does not need to RETURN the sorted array.
3. The first website (mathbits) has the code for sorting an array in DESCENDING order.  

1. Add this code to your SearchAndSort file
2. Change the j loop to be an i loop as using i for single loops are a better practice

Appendix B - Bubble Sort Start Code

Note that this sorts integer arrays from LARGEST to smallest.  The assignments require you to reverse the sort.

public static void bubbleSort(int[] array){

        boolean swap = true;

        while (swap){

            swap = false;

            for (int i = 0; i < array.length-1; i++) {

                if(array[i] < array[i+1]){

                    int temp = array[i];

                    array[i] = array[i+1];

                    array[i+1] = temp;

                    swap = true;

                }              

            }

        }

    }