W1352 Bubble Sort
- Read Bubble Sort (Wikipedia)
- View Bubble Sort 1- Algorithm (YouTube)
- View Bubble Sort Algorithm (YouTube)
The bubble sort algorithm is one of the simplest sorting algorithms. Here's an overview of how it works:
- Iterate over all array elements
- If the element on the left is bigger than the element on the right swap them
- Repeat steps 1 & 2 until there are no more swaps to complete
Although the algorithm is simple, the implementation takes a bit more thought. Here are some things to keep in mind:
- You'll need a variable to count the number of swaps you made
- Before a swap, you'll need to store one of the values in a variable
- You'll need a nested loop (the outer loop to continue until the array is sorted, and the inner loop to iterate over the array)
- Consider which type of loop is the best option (Hint: you'll need the outer loop to always run at least once)
You can either complete the swap in the loop or write a separate function. Note that if you choose to write a separate function, you'll want to pass the array by reference to avoid making a copy of the array each time you need to make a swap. However you choose to implement the swap, you'll need to store at least one of the values (the left or the right) outside of the array. If you just swap without storing one of the values:
arr[i-1] = arr[i] arr[i] = arr[i-1]
You'll just end up with both the element at i and i - 1 being equal to whatever the element at i originally was. In order to solve this, you'll need to store either side as a variable, swap the values, then assign the remaining side to your stored value.
Here's an example of a bubble sort for an array with 3 elements:
Array: [42, 82, 40] | Initial Array: [42, 40, 82] | Swaps: 1 Array: [40, 42, 82] | Swaps: 1 Array: [40, 42, 82] | Swaps: 0 Sorted in 3 iterations
- The array was initially set to
[42, 82, 40]. Remember that we compare each element with the one before it, so the algorithm will compare 42 and 82 first. Since 42 < 82, there there's nothing to swap. However, for the next two elements 82 and 40, 82 > 40 so the elements are swapped.
- For the second iteration, the array starts at
[42, 40, 82]. The first two elements, 42 and 40 are compared. Because 42 > 40, the first two elements are swapped. Then, the next two elements: 42 and 82 are compared. Because 42 < 82, they are already in order and no swaps need to be made.
- For the third iteration, the array start at
Array: [40, 42, 82]. The first two elements, 40 and 42 are compared. Because 40 < 42, no swaps need to be made. Then, the next two elements, 42 and 82 are compared. Because 42 < 82, no swaps need to be made. Because no swaps were made at all in this iteration, we know the array is sorted and we can exit the loop.
Although bubble sort is a simple algorithm to implement, it is rarely used for real-world applications because of its poor performance, and is usually seen in an academic environment.