03. Bubble Sort
Algorithm Pseudocode
- Start at the outer loop, i = 0.
- Within the inner loop, compare each two consecutive values.
- If the value of the right cell has a key index lower than that of the left cell, swap.
- Repeat inner/outer loops until smaller values bubble to the top.
- *If no swaps occur in one entire inner loop, list is already sorted and you're done.
Visualization
Here's a good visualization as to what's exactly happening.
Complexity
Time: O(n2) but O(n) when nearly sorted.
Space: O(1)
Characteristics
Bubble sort is a stable sorting algorithm.
Bubble sort has a high overhead. In the case where the given input is reversed, the algorithm will take O(n2) time.
Implementation in Java
Here's a sample implementation written in Java. Note that it extends the Sort.java class.
import java.util.Arrays;
public class BubbleSort extends Sort {
public static void main(String[] args) {
int[] testInt = {1,6,2,3,6,7,4,2,5};
bubbleSort(testInt);
System.out.println(Arrays.toString(testInt));
}
public static void bubbleSort(int[] testInt) {
/**
* If flag keeps false, then no swaps occurred, meaning
* our list is already sorted
*/
boolean flag;
do {
flag = false;
for (int j = 0; j < testInt.length-1; j++) {
if (testInt[j+1] < testInt[j]) {
swap(testInt, j, j+1);
flag = true;
}
}
} while (flag);
}
Ace your Technical Interview
Programming Interviews: Exposed
In today's tight job market, competition for programming jobs is hotter than ever. This third edition of a popular guide to programming interviews includes new code examples, information on the latest languages, new chapters on sorting and design patterns, tips on using LinkedIn, and a downloadable app to help prepare applicants for the interview.
$ Check price
(94+ reviews) Learn how data is stored
Data Structures and Algorithms in Java
Algorithms are the procedures that software programs use to manipulate data structures. Besides clear and simple example programs, the author includes a workshop as a small demonstration program executable on a Web browser. The programs demonstrate in graphical form what data structures look like and how they operate.
$ Check price(97+ reviews) Ad