Bubble Sort

In this section, we'll talk about one of the most well-known algorithms sorting algorithms, Bubble Sort

Bubble Sort

So what is a Sorting Algorithm anyway? A Sorting Algorithm is a chunk of code that makes sorting as efficient as possible. Our end goal should be to sort an unsorted array.

Idea

We want to come up with an efficient way to Sort a random array. This will make the array much easier to work with, as we'll be able to know the order of the array.

Example: 

Write a program to order the array {1,3,6,2,9,3,7}

Selection Sort

We can simply do a "brute-force" sort, also known as selection sort.

Exercise: Write a program to order the array {1,3,6,2,9,3,7}

This algorithm divides the array into 2 parts. A sorted subarray from left to right of the original array, and a subarray of the remaining unsorted elements. The sorted subarray originally has no elements, and the unsorted array is simply the original array. Then, we'll find the smallest element in the unsorted array, place it into the sorted array, and continue this process until the unsorted array is empty. This method will always work, but can be inefficient.

See if you can write the code for this idea! Check your solution with the console to make sure your array is indeed sorted!

Bubble Sort

But what if our array is HUGE? Traversing through the entire array can be slow, even for a computer, when there are millions of entries. That's why Computer Scientists designed the Bubble Sort Algorithm. The main idea is that Bubble Sort works by repeatedly swapping the adjacent elements if they are in wrong order. If we continue to do this repeatedly though the entire array, surely we will end up with a sorted array.

Code:

void bubbleSort(int arr[])

    {

        int n = arr.length;

        for (int i = 0; i < n-1; i++)

            for (int j = 0; j < n-i-1; j++)

                if (arr[j] > arr[j+1])

                {

                    int temp = arr[j];

                    arr[j] = arr[j+1];

                    arr[j+1] = temp;

                }

    }

Explanation:

Here, we have a void method that sorts the array (given as a parameter) using bubble sort. It's useful to note the nested for loops. These are crucial for keeping track of adjacent entries, from which, the if statements do their magic to ensure that swapping is done correctly.

Exercises:

1. Write a Bubble Search Algorithm to sort an array, using while loops.

2. Quantify and compare the efficiencies of Selection and Bubble Sort

3. Use Binary Search to check if 15 is in the array {1,2,3,4,5,6,7,8,9,10,11,12,13,14,16,17,18,19,20}

70d6f4e10e2badb5ef394f00c17ad2bc1c14f6e7.jpg