Bubble Sort: A Comparison Algorithm
Bubble Sort takes an iterative approach — looping through elements in a matrix-like fashion — to sorting, and is a great place to start with implementing your first sorting algorithm.
Here’s how it works: given an unsorted array, for the full length of that array, we pass over each element; comparing it with the element next to it. If the first element is larger than the second, we swap the two elements.
This creates a “bubbling” effect, where the smallest elements (in our case
numbers) migrate their way to the front of the list with every pass.
As I mentioned earlier, using helper functions to implement bubble sort makes the code more readable, so I’ll start with implementing those:
A Pair-wise comparator function . First, we’ll define a pure helper function — a function that that takes in input and gives us output without changing anything — called inAscendingOrder. This function will take two elements in a given array, compare them, and return a boolean based on the result.
code:
//let's call it inAscendingOrder var inAscendingOrder = function(array, index) { //check edge case for end of array, since it won't have a neighbor to compare to if(index === array.length - 1) return true; //will return a truthy value if consecutive items are in proper ascending order return array[index] < array[index + 1]; };
A swapping function
Next, we’ll define a function that swaps two elements in a list. We can’t call this a pure function. Why? Because it will actually have an effect on the external scope (our bubble sort implementation) when we use it later on.
code:
var swap = function(array, index) { //create a variable that points to the same value as the current index var tmp = array[index]; //point the current index to the value of its next index array[index] = array[index + 1]; //point that next index to the value saved in our temporary storage array[index + 1] = tmp; //now the two elements in the array are swapped out! };
The actual bubble sort implementation
And finally, we want to define the actual bubble sorting algorithm.
Before I bring in the code, I want to mention a couple of things that might be helpful to understand:
(1) I’m going to be using the concept of “state”, which basically means my function will keep metadata on itself, and let us know when it finishes sorting the input array;
(2) I’m going to pass through the array backwards. What does this mean? Well, we use nested loops to implement bubble sort. The outer loop handles the direction and length of our passes, so I’ll start my loop from the last element of the array and work my way to index 0. Why are we looping backwards? This makes it so that the inner for loop, the loop that will be handling the swapping, requires less work to do its job; avoiding the added task of passing
over elements it has already sorted. Hopefully, you’ll see what I mean below:
code:
var bubbleSort = function(arr) { //initialize a flag variable to help indicate whether the arr is sorted or not (state) var sorted = false; //how nested for loops work: //(in this case, looping backwards,) passing over our array until it's sorted, for(var i = arr.length; i > 0 && !sorted ; i--){ //we'll toggle the state of our sorted flag to be true for each pass sorted = true; //with each element in the array for(var j = length; j > i; j++){ //do the following: //check if each element is in proper descending order, if not... if(!inAscendingOrder(arr, j)) { //use helper function to swap elements swap(arr, j); //and since we had to swap, we know it's not sorted yet, so toggle state back to false... sorted = false; } } } //return array return arr; };
Merge Sort: A Recursive Sorting Algorithm
Merge Sort, on the other hand, takes a divide-and-conquer approach to sorting; recursively breaking the input array down until we have sorted tuple-sized subarrays that we can then merge back together at the end.
I’ll also use helper functions in implementing merge sort (again, to keep the code declarative):
A split helper function
code:
function split(arr) { var middle = array.length / 2; var left = array.slice(0, middle); //won't include the end point passed var right = array.slice(middle); return [left, right]; //returns tuple of split arrays }
A merge helper function
code:
function merge(left, right) { var merged = [],//setup empty storage for our merging leftIndex = 0, //initialize vars to help point to current index in left && right subarrays rightIndex = 0; while(leftIndex < left.length && rightIndex < right.length) { //iterate through both subarrays if(left[leftIndex] < right[rightIndex]) { //if left element > than right at sameIndex merged.push(left[leftIndex]); //push the lesser of the two into our merge storage leftIndex++; //move left index pointer over one (keeps things linear) } else { //otherwise merged.push(right[rightIndex]); //if right element >, push that one to merge storage rightIndex++; //move right index pointer over one } } //in the case of inbalanced subarrays, one of these for loops will be triggered //pushes all of the remaining values of the longer array into merge storage //if our split function works well, we'd only be passing over a couple (if not only one) element for(; leftIndex < left.length; leftIndex++) merged.push(left[leftIndex]); for(; rightIndex < right.length; rightIndex++) merged.push(right[rightIndex]); return merged; //return subarrays merged }
Note: in analyzing the code, you might be wondering: wait, why didn’t she just use javascript’s built-in shift method to implement this merge function. That’s because using shift would require more work of our algorithm, having to pass over every element and shift each over one, thereby slowing things down. To optimize efficiency of mergeSort, we’ll want to keep this as a linear operation (more on this later).
And finally, here’s our recursive merge sort solution that utilizes both helper functions…
code:
function mergeSort (arr) { if(arr.length < 2) return arr; //base case var splits = split(arr), //(1)split the array with helper function leftArr = splits[0], //(2)store left subarray in var rightArr = splits[1];//(3)store right subarray in var return merge(mergeSort(leftArr), mergeSort(rightArr)); //merge sorted subarrays }
Comparing Bubble Sort and Merge Sort: Time-Complexity Analysis
So why choose one over the other?
Both have their pros and cons, but ultimately bubble sort quickly becomes less efficient when it comes to sorting larger data sets (or ‘big data’). Where as, Merge Sort becomes more efficient as data sets grow.
This makes more sense once you familiarize yourself with Big-O Notationand the concept of time complexity. What’s time complexity? Basically, we use time complexity to analyze the performance of an algorithm, or how long it takes to solve the problem for a given input. Here’s a cheat sheet to help you dig deeper into this.
At best, with smaller data sets, bubble sort has O(n), and worst case scenario, it has O(n²) time complexity (which is pretty bad).
On the other hand, merge sort performs pretty consistently, with a time complexity of O(n log(n)). The time complexity of our helper functions for merge sort make this possible.
There are many more sorting algorithms to explore, and I hope this helps others venturing into software engineering, machine learning, and other disciplines get a better understanding of the two most popular ones.
// Thank you
Compare and Contrast Bubble Sort with Merge Sort. Discuss about the efficiency of both.
1. Compare and contrast: SORTING -a bubble sort through an array -a selection sort through an array Explain how each works and what the advantages and disadvantages are. Note the efficiency of each. 2. Compare and contrast: SEARCHING -a sequential search through a file -a sequential search through an array -a binary search through an array Explain how each works and what the advantages and disadvantages are. Note the efficiency of each.
6
6. Merge Bubble Sort: a) How does the merge bubble sort break the array into sublists? b) What does it need to use for each sublist and then what does it do with all of the sublists? c) What is the Big-O notation for this sort? 7. Merge Sort: a) How does the merge sort use recursion to break the array into sublists? b) What happens to each of these sublists to get the final sorted list? c) What...
Implement a parallel version of a sorting algorithm (bubble sort or merge sort). Done in java and a minimum of two threads utilised.
Which, if any, of the algorithms bubble-sort, heap-sort, merge-sort, and quick- sort are stable? ( use the algorithms as presented in the text, without special tie-breaking rules; answer separately for the three-way quicksort and the two-way in-place quicksort . )
Write a program that obtains the execution time of selection sort, radix sort, bubble sort, merge sort, quick sort, and heap sort for input size 50000, 100,000, 150,000, 200,000, 250,000, and 300,000. Your program should create data randomly and print a table like this: In the same program, obtain the execution time of selection sort, radix sort, bubble sort, and heap sort for input size 2,000,000, 3,000,000, 4,000,000, and 5,000,000. (Hint: You can use the code template below to obtain...
Which of the following statements about the Merge Sort algorithm is True? Select one: Merge Sort uses list concatenation to join sublists. Merge Sort runs in O(na) time. Merge Sort only works if the input list is in sorted order. O Merge Sort will take longer to sort a given list into descending order than into ascending order. None of the above, they are all False.
need help!! java eclipse
Write a program to implement bubble sort, insertion sort, selection sort, merge sort and quick sort (pivot - first index) algorithms. a) Compute the CPU processing time for all the algorithms for varying input sizes as follows: N-10, 103, 10, 10, and 106 b) Use a random number generator to generate the inputs. Obtain the inputs from the following input ranges: 1- 10, 1 -10, 1 - 10, 1 12 10 c) Write down your results...
Exercise 1.12. (Difficulty 2) Bubblesort and oblivious merge-sort each give a sequence of compare-exchange operations which sorts any array A0..3]. Write down both sequences.
Exercise 1.12. (Difficulty 2) Bubblesort and oblivious merge-sort each give a sequence of compare-exchange operations which sorts any array A0..3]. Write down both sequences.
What action do merge sort, quick sort, and heap sort perform that so radically reduces their complexity? (From O(n2) for the other sorts that we looked at earlier–selection sort, bubble sort, and insertion sort–to O(n log n) for these)? Hint: they all employ a strategy that has to do with how many things they look at in a pass. Describe a situation where merge sort would be a better choice for sorting than quick sort.
Write a JAVA Program: Compare the performance of bubble sort and selection sort over several arrays. - Write two methods that sort arrays of doubles. One method should use selection sort, and the other should use bubble sort. - In each of the sort methods, add code that counts the total number of comparisons and total number of swaps performed while sorting the entire array (be careful; don't count each pass through the array separately) - Each time an array...