Bubble Sort#
Bubble sort is a simple sorting algorithm. It repeatedly visits the elements in the list to be sorted, compares two elements at a time, and swaps them if they are in the wrong order. The process of visiting the list is repeated until no more swaps are needed, which means the list is sorted. The name of this algorithm comes from the fact that smaller elements gradually "bubble" to the top of the list through the swaps.
The operation of the bubble sort algorithm is as follows:
- Compare adjacent elements. If the first element is greater than the second element, swap them.
- Perform the same operation for each pair of adjacent elements, from the first pair 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.
- Repeat the above steps for an increasingly smaller number of elements until no more pairs need to be compared.
The average time complexity of bubble sort is O(n^2). In the best case, when the list is already sorted, the time complexity is O(n). In the worst case, the time complexity is O(n^2).
Classic Bubble Sort Algorithm#
The classic bubble sort algorithm uses nested loops to perform the sorting. The outer loop represents the current round of sorting, and the inner loop represents the current iteration of the round. The algorithm compares and swaps elements to sort the list.
function bubbleSort(nums) {
const len = nums.length
for (let i = 0; i < len; i++) {
for (let j = 0; j < len - 1 - i; j++) {
if (nums[j] > nums[j + 1]) {
;[nums[j], nums[j + 1]] = [nums[j + 1], nums[j]] // Swap positions
}
}
}
return nums
}
Improved Bubble Sort Algorithm#
The improved bubble sort algorithm uses a flag variable called "pos" to record the last position where a swap occurred in each round of sorting. Since the elements after the "pos" position are already in their correct places, in the next round of sorting, we only need to scan up to the "pos" position.
function bubbleSort(nums) {
const len = nums.length
let i = len - 1
while (i > 0) {
let pos = 0
for (let j = 0; j < i; j++) {
if (nums[j] > nums[j + 1]) {
pos = j // Record the position of the swap
;[nums[j], nums[j + 1]] = [nums[j + 1], nums[j]] // Swap positions
}
}
i = pos
}
return nums
}
Ultimate Bubble Sort Algorithm#
The ultimate bubble sort algorithm can find both the maximum and minimum values in each round of sorting. It performs a forward pass to find the maximum value and a backward pass to find the minimum value. This reduces the number of rounds required to sort the list by almost half.
function bubbleSort(nums) {
let low = 0
let high = nums.length - 1
let i
while (low < high) {
// Forward pass to find the maximum value
for (i = low; i < high; ++i) {
if (nums[i] > nums[i + 1]) {
;[nums[i], nums[i + 1]] = [nums[i + 1], nums[i]] // Swap positions
}
}
--high // Move the high position one step back
// Backward pass to find the minimum value
for (i = high; i > low; --i) {
if (nums[i] < nums[i - 1]) {
;[nums[i], nums[i - 1]] = [nums[i - 1], nums[i]] // Swap positions
}
}
++low // Move the low position one step forward
}
return nums
}
Selection Sort#
Selection sort is a simple and intuitive sorting algorithm. It works by repeatedly finding the minimum (or maximum) element from the unsorted part of the list and putting it at the beginning of the sorted part. This process is repeated until the entire list is sorted.
The operation of the selection sort algorithm is as follows:
- Initial state: the unsorted part is R[1..n], and the sorted part is empty.
- In each round of sorting, the current sorted part and unsorted part are R[1..i-1] and R[i..n], respectively. Find the minimum value from the current unsorted part and swap it with the first value of the unsorted part. This adds one element to the sorted part and reduces one element from the unsorted part.
- Repeat steps 2 until the end of the list is reached, i.e., n-1 rounds of sorting.
The average time complexity of selection sort is O(n^2).
Classic Selection Sort Algorithm#
The classic selection sort algorithm divides the list into a sorted part and an unsorted part. In each round of sorting, it selects the minimum value from the unsorted part and adds it to the sorted part. After n - 1 rounds of sorting, the entire list becomes sorted.
function selectionSort(nums) {
const len = nums.length
let min = 0
for (let i = 0; i < len - 1; i++) {
min = i
for (let j = i + 1; j < len; j++) {
if (nums[min] > nums[j]) {
min = j // Save the index of the minimum value
}
}
;[nums[i], nums[min]] = [nums[min], nums[i]] // Swap positions
}
return nums
}
Insertion Sort#
Insertion sort is a simple sorting algorithm that works by building a sorted sequence, one element at a time. It scans the unsorted part of the list from right to left and inserts each element into its correct position in the sorted part. Insertion sort is usually implemented as an in-place sorting algorithm, which means it rearranges the elements within the list without requiring additional memory.
The operation of the insertion sort algorithm is as follows:
- Start with the first element, which is considered already sorted.
- Take the next element and scan through the sorted part of the list from right to left. If the element is greater than the current element in the sorted part, move the current element one position to the right.
- Repeat step 2 until you find the correct position for the element, and then insert it.
- Repeat steps 2 and 3 for all remaining elements until the entire list is sorted.
The average time complexity of insertion sort is O(n^2). In the best case, when the list is already sorted, the time complexity is O(n). In the worst case, the time complexity is O(n^2).
Classic Insertion Sort Algorithm#
The classic insertion sort algorithm divides the list into a sorted part and an unsorted part. In each iteration, it takes an element from the unsorted part and inserts it into the correct position in the sorted part. This process continues until all elements are sorted.
function insertionSort(nums) {
const len = nums.length
for (let i = 1; i < len; i++) {
let k = nums[i]
let j = i - 1
while (j >= 0 && nums[j].num > k.num) {
nums[j + 1] = num[j]
j--
}
nums[j + 1] = k
}
return nums
}
Binary Insertion Sort Algorithm#
The binary insertion sort algorithm uses binary search to find the correct position for inserting an element in the sorted part of the list. This reduces the number of comparisons required in each iteration, especially for large lists.
function insertionSort(nums) {
const len = nums.length
for (let i = 1; i < len; i++) {
let k = nums[i]
let left = 0
let right = i - 1
while (left <= right) {
let middle = ~~((left + right) / 2)
if (k < nums[middle]) {
right = middle - 1
} else {
left = middle + 1
}
}
for (let j = i - 1; j >= left; j--) {
nums[j + 1] = nums[j]
}
nums[left] = k
}
return nums
}
Merge Sort#
Merge sort is an efficient sorting algorithm based on the concept of merging. It works by dividing the unsorted list into smaller sublists, sorting those sublists, and then merging them back into a single sorted list. Merge sort has a time complexity of O(nlogn). It is a classic example of the divide-and-conquer paradigm, and the recursive nature of the algorithm allows multiple levels of merging to be performed simultaneously.
The operation of the merge sort algorithm is as follows:
- Divide the list of length n into n/2 sublists of length 2.
- Recursively sort each sublist by performing steps 1 and 2 until each sublist contains only one element.
- Merge the sorted sublists back into a single sorted list by repeatedly comparing and merging adjacent sublists.
The average time complexity of merge sort is O(nlogn).
Classic Merge Sort Algorithm#
The classic merge sort algorithm divides the list into two halves, recursively sorts each half, and then merges the sorted halves back into a single sorted list.
function mergeSort(nums) {
const len = nums.length
if (len <= 1) return nums
let middle = ~~(len / 2)
let left = nums.slice(0, middle)
let right = nums.slice(middle)
return merge(mergeSort(left), mergeSort(right))
}
function merge(left, right) {
const result = []
while (left.length && right.length) {
if (left[0] < right[0]) {
result.push(left.shift())
} else {
result.push(right.shift())
}
}
return result.concat(left, right)
}
}