1.1 Bubble Sort
Category Algorithm
Bubble Sort is also a simple and intuitive sorting algorithm. It repeatedly visits the list to be sorted, compares two elements at a time, and if their order is incorrect, it swaps them. The process of visiting the list is repeated until no more swaps are needed, meaning the list is sorted. The name of this algorithm comes from the fact that smaller elements will gradually "float" to the top of the list through swaps.
As one of the simplest sorting algorithms, Bubble Sort feels to me like the word "Abandon" appearing in a vocabulary book, always on the first page and first position, making it the most familiar. There is also an optimized version of Bubble Sort, which is to set a flag. If no elements are swapped during a pass through the sequence, it proves that the sequence is already ordered. However, this improvement does not enhance performance.
1. Algorithm Steps
Compare adjacent elements. If the first is larger than the second, swap them.
Do the same for each pair of adjacent elements, from the first to the last pair. After this step, the last element will be the largest number.
Repeat the above steps for all elements, except the last one.
Continue to repeat the above steps for fewer and fewer elements each time, until no pair of numbers needs to be compared.
2. Animated Demonstration
3. When is it the fastest
When the input data is already in ascending order (since it's already in order, why do I need Bubble Sort?).
4. When is it the slowest
When the input data is in reverse order (why use Bubble Sort when I can just write a for loop to output the data in reverse order, am I just bored?).
5. JavaScript Implementation
Example
function bubbleSort(arr) {
var len = arr.length;
for (var i = 0; i < len - 1; i++) {
for (var j = 0; j < len - 1 - i; j++) {
if (arr[j] > arr[j+1]) { // Compare adjacent elements
var temp = arr[j+1]; // Swap elements
arr[j+1] = arr[j];
arr[j] = temp;
}
}
}
return arr;
}
6. Python Implementation
Example
def bubbleSort(arr):
for i in range(1, len(arr)):
for j in range(0, len(arr)-i):
if arr[j] > arr[j+1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arr
7. Go Implementation
Example
func bubbleSort(arr []int) []int {
length := len(arr)
for i := 0; i < length; i++ {
for j := 0; j < length-1-i; j++ {
if arr[j] > arr[j+1] {
arr[j], arr[j+1] = arr[j+1], arr[j]
}
}
}
return arr
}
8. Java Implementation
Example
public class BubbleSort implements IArraySort {
@Override
public int[] sort(int[] sourceArray) throws Exception {
// Make a copy of arr, do not change the content of the argument
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
for (int i = 1; i < arr.length; i++) {
// Set a flag, if true, it means no swap has been made in this loop, which means the array to be sorted is already in order, and the sorting is complete.
boolean flag = true;
for (int j = 0; j < arr.length - i; j++) {
if (arr[j] > arr[j + 1]) {
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
flag = false;
}
}
if (flag) {
break;
}
}
return arr;
}
}
9. PHP Implementation
Example
function bubbleSort($arr)
{
$len = count($arr);
for ($i = 0; $i < $len - 1; $i++) {
for ($j = 0; $j < $len - 1 - $i; $j++) {
if ($
This is a Chinese to English translation, please provide the English translation for this text. Do not provide any explanations or text apart from the translation.
Chinese: puts [22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70].bubble_sort!
### 14. Swift
## Example
import Foundation
func bubbleSort (arr: inout [Int]) { for i in 0..<arr.count - 1 { for j in 0..<arr.count - 1 - i { if arr[j] > arr[j+1] { arr.swapAt(j, j+1) } } } }
// Test call
func testSort () { // Generate a random number array for sorting var list:[Int] = [] for _ in 0...99 { list.append(Int(arc4random_uniform(100))) } print("(list)") bubbleSort(arr:&list) print("(list)") }
>
Original article link: https://github.com/hustcc/JS-Sorting-Algorithm/blob/master/1.bubbleSort.md
Reference address: https://zh.wikipedia.org/wiki/Bubble_sort
##
-
** rookie
** esh***[email protected]
Improved Bubble Sort
- The first pass of the bubble sort will place the maximum value on the far right, and this maximum value is also the global maximum.
- Standard bubble sort compares all elements in each pass, although the value on the far right is already the maximum.
- After improvement, the maximum value, the second maximum, etc., will be fixed on the right after each pass, avoiding redundant comparisons.
Python implementation:
def bubbleSort(arr): for i in range(len(arr) - 1, 0, -1): # Reverse traversal for j in range(0, i): # Since the value on the far right is already sorted, no need to compare, reduce the number of traversals each time if arr[j] > arr[j + 1]: arr[j], arr[j + 1] = arr[j + 1], arr[j] return arr
Go implementation:
func bubbleSort(arr []int) []int { for i := len(arr) - 1; i > 0;i-- { // Reverse traversal for j := 0; j < i; j++ { if arr[j] > arr[j + 1){ arr[j], arr[j + 1] = arr[j + 1], arr[j] } } } return arr }
** rookie
** esh***[email protected]
-
** muen
** zha***[email protected]
Wow~~~ Just added a table where it's already sorted, the performance has improved a lot~~~
def bubble_sort(list): k = len(list) - 1 pos = 0 for i in range(len(list) - 1): flag = False for j in range(k): if list[j] > list[j + 1]: tmp = list[j] list[j] = list[j + 1] list[j + 1] = tmp flag = True pos = j k = pos if flag == False: break return list import threading from random import * from time import *
class Thread(threading.Thread):
def __init__(self,f):
threading.Thread.__init__(self)
self.input = None
self.returnval = None
self.f = f
def run(self):
if self.input != None:
self.returnval = self.f(self.input)
else:
self.returnval = self.f()
Let's add multi-threading~~~ And add a condition to open multi-threading~~~ The performance has improved a lot~~~
** muen
** zha***[email protected]
-
** kezhuoquan
** kez***[email protected]
Rust version implementation:
fn bubble_sort<T:Ord + Debug>(array: &mut [T]) { for i in 0..array.len() { for j in 0..array.len() - i - 1 { if array[j] > array[j + 1] { array.swap(j, j + 1); } println!("{:?}", array); } } } ```