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.
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.
