Bubble Sort is a simple comparison-based algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. It’s ideal for learning sorting concepts but is inefficient for large datasets.
function bubbleSort(arr) {
let n = arr.length;
for (let i = 0; i < n - 1; i++) {
for (let j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
}
}
}
return arr;
}
console.log(bubbleSort([64, 34, 25, 12, 22, 11, 90]));
def bubble_sort(arr):
n = len(arr)
for i in range(n - 1):
for j in range(n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arr
print(bubble_sort([64, 34, 25, 12, 22, 11, 90]))
Selection Sort improves upon Bubble Sort by finding the minimum (or maximum) element and swapping it with the first unsorted element. It is more efficient than Bubble Sort but still not suitable for large datasets.
function selectionSort(arr) {
let n = arr.length;
for (let i = 0; i < n - 1; i++) {
let minIndex = i;
for (let j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
}
return arr;
}
console.log(selectionSort([64, 25, 12, 22, 11]));
def selection_sort(arr):
n = len(arr)
for i in range(n - 1):
min_index = i
for j in range(i + 1, n):
if arr[j] < arr[min_index]:
min_index = j
arr[i], arr[min_index] = arr[min_index], arr[i]
return arr
print(selection_sort([64, 25, 12, 22, 11]))
Insertion Sort builds the final sorted array one item at a time. It is more efficient than Bubble and Selection Sort for nearly sorted or small datasets.
function mergeSort(arr) {
if (arr.length < 2) return arr;
const middle = Math.floor(arr.length / 2);
const left = mergeSort(arr.slice(0, middle));
const right = mergeSort(arr.slice(middle));
return merge(left, right);
}
function merge(left, right) {
let result = [], leftIndex = 0, rightIndex = 0;
while (leftIndex < left.length && rightIndex < right.length) {
if (left[leftIndex] < right[rightIndex]) {
result.push(left[leftIndex++]);
} else {
result.push(right[rightIndex++]);
}
}
return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}
console.log(mergeSort([38, 27, 43, 3, 9, 82, 10]));
def merge_sort(arr):
if len(arr) < 2:
return arr
middle = len(arr) // 2
left = merge_sort(arr[:middle])
right = merge_sort(arr[middle:])
return merge(left, right)
def merge(left, right):
result = []
left_index, right_index = 0, 0
while left_index < len(left) and right_index < len(right):
if left[left_index] < right[right_index]:
result.append(left[left_index])
left_index += 1
else:
result.append(right[right_index])
right_index += 1
result.extend(left[left_index:])
result.extend(right[right_index:])
return result
print(merge_sort([38, 27, 43, 3, 9, 82, 10]))
Quick Sort is a divide-and-conquer algorithm that selects a ‘pivot’ element and partitions the array into elements less than the pivot and elements greater than the pivot.
function quickSort(arr) {
if (arr.length <= 1) return arr;
const pivot = arr[arr.length - 1];
const left = [], right = [];
for (let i = 0; i < arr.length - 1; i++) {
if (arr[i] < pivot) left.push(arr[i]);
else right.push(arr[i]);
}
return [...quickSort(left), pivot, ...quickSort(right)];
}
console.log(quickSort([10, 7, 8, 9, 1, 5]));
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quick_sort(left) + middle + quick_sort(right)
print(quick_sort([10, 7, 8, 9, 1, 5]))
Heap Sort converts the array into a heap structure and then sorts the array by repeatedly extracting the maximum element from the heap.
function shellSort(arr) {
let n = arr.length;
let gap = Math.floor(n / 2);
while (gap > 0) {
for (let i = gap; i < n; i++) {
let temp = arr[i];
let j = i;
while (j >= gap && arr[j - gap] > temp) {
arr[j] = arr[j - gap];
j -= gap;
}
arr[j] = temp;
}
gap = Math.floor(gap / 2);
}
return arr;
}
console.log(shellSort([5, 2, 9, 1, 5, 6]));
def heap_sort(arr):
def heapify(arr, n, i):
largest = i
left = 2 * i + 1
right = 2 * i + 2
if left < n and arr[left] > arr[largest]:
largest = left
if right < n and arr[right] > arr[largest]:
largest = right
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
n = len(arr)
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)
for i in range(n - 1, 0, -1):
arr[0], arr[i] = arr[i], arr[0]
heapify(arr, i, 0)
return arr
print(heap_sort([12, 11, 13, 5, 6, 7]))
Shell Sort generalizes Insertion Sort to allow the exchange of items that are far apart. It is an in-place comparison-based algorithm.
function shellSort(arr) {
let n = arr.length;
let gap = Math.floor(n / 2);
while (gap > 0) {
for (let i = gap; i < n; i++) {
let temp = arr[i];
let j = i;
while (j >= gap && arr[j - gap] > temp) {
arr[j] = arr[j - gap];
j -= gap;
}
arr[j] = temp;
}
gap = Math.floor(gap / 2);
}
return arr;
}
console.log(shellSort([5, 2, 9, 1, 5, 6]));
def shell_sort(arr):
n = len(arr)
gap = n // 2
while gap > 0:
for i in range(gap, n):
temp = arr[i]
j = i
while j >= gap and arr[j - gap] > temp:
arr[j] = arr[j - gap]
j -= gap
arr[j] = temp
gap //= 2
return arr
print(shell_sort([5, 2, 9, 1, 5, 6]))
Counting Sort is an integer sorting algorithm that counts the occurrences of each value and uses this count to determine the position of each element in the output array.
function countingSort(arr) {
let max = Math.max(...arr);
let count = new Array(max + 1).fill(0);
let output = new Array(arr.length);
for (let i = 0; i < arr.length; i++) {
count[arr[i]]++;
}
for (let i = 1; i < count.length; i++) {
count[i] += count[i - 1];
}
for (let i = arr.length - 1; i >= 0; i--) {
output[count[arr[i]] - 1] = arr[i];
count[arr[i]]--;
}
return output;
}
console.log(countingSort([4, 2, 2, 8, 3, 3, 1]));
def counting_sort(arr):
max_val = max(arr)
count = [0] * (max_val + 1)
output = [0] * len(arr)
for num in arr:
count[num] += 1
for i in range(1, len(count)):
count[i] += count[i - 1]
for num in reversed(arr):
output[count[num] - 1] = num
count[num] -= 1
return output
print(counting_sort([4, 2, 2, 8, 3, 3, 1]))
Radix Sort processes numbers digit by digit starting from the least significant digit (LSD) or most significant digit (MSD). It’s suitable for sorting large datasets of integers.
function radixSort(arr) {
const getMax = (arr) => Math.max(...arr);
const countingSort = (arr, exp) => {
let n = arr.length;
let output = new Array(n);
let count = new Array(10).fill(0);
for (let i = 0; i < n; i++) {
count[Math.floor(arr[i] / exp) % 10]++;
}
for (let i = 1; i < 10; i++) {
count[i] += count[i - 1];
}
for (let i = n - 1; i >= 0; i--) {
output[count[Math.floor(arr[i] / exp) % 10] - 1] = arr[i];
count[Math.floor(arr[i] / exp) % 10]--;
}
for (let i = 0; i < n; i++) {
arr[i] = output[i];
}
};
let max = getMax(arr);
for (let exp = 1; Math.floor(max / exp) > 0; exp *= 10) {
countingSort(arr, exp);
}
return arr;
}
console.log(radixSort([170, 45, 75, 90, 802, 24, 2, 66]));
def radix_sort(arr):
def counting_sort(arr, exp):
n = len(arr)
output = [0] * n
count = [0] * 10
for i in range(n):
index = arr[i] // exp
count[index % 10] += 1
for i in range(1, 10):
count[i] += count[i - 1]
i = n - 1
while i >= 0:
index = arr[i] // exp
output[count[index % 10] - 1] = arr[i]
count[index % 10] -= 1
i -= 1
for i in range(n):
arr[i] = output[i]
max_val = max(arr)
exp = 1
while max_val // exp > 0:
counting_sort(arr, exp)
exp *= 10
return arr
print(radix_sort([170, 45, 75, 90, 802, 24, 2, 66]))
Bucket Sort divides the elements into a number of buckets, sorts each bucket, and then concatenates the sorted buckets. It is efficient for uniformly distributed data.
10. Bucket Sort: Efficient for Uniform Distributions
Overview
Bucket Sort divides the elements into a number of buckets, sorts each bucket, and then concatenates the sorted buckets. It is efficient for uniformly distributed data.
JavaScript Example
javascript
Copy code
function bucketSort(arr) {
if (arr.length === 0) return arr;
let minValue = Math.min(...arr);
let maxValue = Math.max(...arr);
let bucketCount = Math.floor((maxValue - minValue) / arr.length) + 1;
let buckets = Array.from({ length: bucketCount }, () => []);
arr.forEach(value => {
buckets[Math.floor((value - minValue) / arr.length)].push(value);
});
return buckets.flat().sort((a, b) => a - b);
}
console.log(bucketSort([0.78, 0.17, 0.91, 0.43, 0.32, 0.56, 0.60]));
Python Example
python
Copy code
def bucket_sort(arr):
if len(arr) == 0:
return arr
min_val = min(arr)
max_val = max(arr)
bucket_count = (max_val - min_val) // len(arr) + 1
buckets = [[] for _ in range(bucket_count)]
for num in arr:
index = (num - min_val) // len(arr)
buckets[index].append(num)
sorted_arr = []
for bucket in buckets:
sorted_arr.extend(sorted(bucket))
return sorted_arr
print(bucket_sort([0.78, 0.17, 0.91, 0.43, 0.32, 0.56, 0.60]))
Time Complexity
Best Case: O(n + k)
Average Case: O(n + k)
Worst Case: O(n^2)def bucket_sort(arr):
if len(arr) == 0:
return arr
min_val = min(arr)
max_val = max(arr)
bucket_count = (max_val - min_val) // len(arr) + 1
buckets = [[] for _ in range(bucket_count)]
for num in arr:
index = (num - min_val) // len(arr)
buckets[index].append(num)
sorted_arr = []
for bucket in buckets:
sorted_arr.extend(sorted(bucket))
return sorted_arr
print(bucket_sort([0.78, 0.17, 0.91, 0.43, 0.32, 0.56, 0.60]))
This guide provides an in-depth look at various sorting algorithms, including JavaScript and Python examples, their time complexities, and their ideal use cases. For more detailed insights and advanced applications, consider exploring each algorithm's strengths and limitations in different scenarios.
Subscribe to our newsletter for updates and notifications on the latest in algorithms and technology trends!
