Bubble Sort and Quick Sort in JavaScript
Algorithms are the step-by-step methods behind everyday JavaScript tasks, from searching arrays to sorting data for a user interface. Choosing an appropriate algorithm matters because the amount of work can grow quickly as data sets get larger, affecting application speed and responsiveness. Comparing Bubble Sort and Quick Sort offers a practical way to see how different strategies solve the same problem—and why their performance can differ so dramatically.
Big O notation describes how an algorithm's resource requirements grow with input size, commonly written as n. It is not a promise of an exact runtime; instead, it highlights the dominant growth pattern. For example, an O(n) algorithm generally does work proportional to the number of items, while an O(n²) algorithm can require roughly four times as much work when the input doubles. Understanding these complexity classes helps developers reason about scalability and choose implementations that remain practical as their applications grow.
The examples below sort arrays of numbers in ascending order and return a new array, leaving the input unchanged. They work with empty arrays, duplicates, and negative values. The complete, dependency-free JavaScript example is also available in code/bubble-sort-vs-quicksort.js.
Bubble Sort: compare neighbors
Bubble Sort repeatedly scans an array and compares adjacent values. If the left value is greater than the right value, it swaps them. At the end of each pass, the largest value in the still-unsorted section has moved to its final position. The next pass can stop one element earlier.
For example, start with [5, 1, 4, 2, 8]. Comparing 5 and 1 causes a swap, giving [1, 5, 4, 2, 8]. The next comparison swaps 5 and 4, then 5 and 2. At the end of that pass, 5 is in its final place, just before 8. More passes sort the remaining prefix.
function bubbleSort(values) {
const result = values.slice();
for (let end = result.length - 1; end > 0; end -= 1) {
let swapped = false;
for (let index = 0; index < end; index += 1) {
if (result[index] > result[index + 1]) {
const current = result[index];
result[index] = result[index + 1];
result[index + 1] = current;
swapped = true;
}
}
if (!swapped) {
break;
}
}
return result;
}
const scores = [5, 1, 4, 2, 8];
console.log(bubbleSort(scores)); // [1, 2, 4, 5, 8]
console.log(scores); // [5, 1, 4, 2, 8]
The end index marks the last value that still needs to be considered. The inner loop stops there because every value beyond it has already been placed by an earlier pass. The swapped flag records whether the pass changed the array. If it did not, every adjacent pair was already in order, so the algorithm can stop without doing redundant passes.
That early exit gives Bubble Sort a best-case time complexity of O(n) when the input is already sorted: it makes one pass and finds no swaps. On average and in the worst case, it takes O(n²) time. A reverse-sorted array is especially demanding because many pairs must be swapped over many passes. Doubling the input size can therefore require roughly four times the work.
Bubble Sort is stable when implemented with the strict > comparison shown here. Equal values are not swapped, so their relative order is retained. Its in-place sorting process needs O(1) working space, but this function copies its input first, so the returned-result version requires O(n) additional memory. Keeping the input unchanged is often a useful API choice, but it must be included in the space analysis.
Quick Sort: partition, then recurse
Quick Sort uses a divide-and-conquer strategy. It selects a pivot, partitions the current section into values below, equal to, and above the pivot, then sorts the lower and upper sections recursively. Once a section has fewer than two values, it is already sorted and recursion stops.
The implementation below uses the middle-position element as its pivot and a three-way partition. It groups all values equal to the pivot together, which is helpful for input containing many duplicates.
function quickSort(values) {
const result = values.slice();
function sortRange(low, high) {
if (low >= high) {
return;
}
const pivot = result[Math.floor((low + high) / 2)];
let less = low;
let current = low;
let greater = high;
while (current <= greater) {
if (result[current] < pivot) {
[result[less], result[current]] = [result[current], result[less]];
less += 1;
current += 1;
} else if (result[current] > pivot) {
[result[current], result[greater]] = [result[greater], result[current]];
greater -= 1;
} else {
current += 1;
}
}
sortRange(low, less - 1);
sortRange(greater + 1, high);
}
sortRange(0, result.length - 1);
return result;
}
const values = [9, 3, 7, 3, -1, 8];
console.log(quickSort(values)); // [-1, 3, 3, 7, 8, 9]
console.log(values); // [9, 3, 7, 3, -1, 8]
The three indexes define the partition as it is built. Values before less are below the pivot. Values from less up to, but not including, current are equal to it. Values after greater are above it. Between current and greater are values that have not yet been classified.
When the current value is less than the pivot, it is moved into the lower region and both less and current advance. If it is greater, it is exchanged with the value at greater, and greater moves left. In that case current does not advance: the value moved into its position has not been examined yet. Equal values simply advance current. When the partition loop ends, the equal region is in place, so recursion is needed only for the lower and upper regions.
The base condition low >= high handles ranges of zero or one item, including the initial call for an empty array. It also guarantees that recursive calls eventually stop. Because the function sorts a copy, its returned array is independent of the original.
With reasonably balanced partitions, Quick Sort runs in O(n log n) average time. Each partition examines the values in its section, and balanced recursion creates approximately log₂(n) levels. However, its worst-case time is O(n²) if each pivot produces highly uneven partitions—for example, one empty side and one side containing nearly every other value. Choosing the item at the middle index is straightforward, but does not ensure that the pivot's value is near the median.
Partitioning itself uses O(1) additional space, but recursive calls consume stack space: about O(log n) for balanced partitions and up to O(n) in the worst case. This implementation also copies the input, adding O(n) memory. Quick Sort is generally not stable; partition swaps may change the relative order of values that compare equally.
Comparing the trade-offs
| Algorithm | Best time | Average time | Worst time | Stable? | Extra space in these examples |
|---|---|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | Yes | O(n) for the copied result |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | No | O(n) copy plus recursion stack |
Big O describes how resource use grows as the input gets larger; it does not predict exact elapsed time for every array. The values' distribution, the JavaScript engine, and allocation costs also affect measured performance. The three-way Quick Sort partition is particularly useful when many elements are equal: it places the entire equal group in one pass instead of sorting those values repeatedly.
Bubble Sort's small amount of code makes it a good teaching tool for nested loops, comparisons, swaps, and loop bounds. It is rarely appropriate for a large production collection because its quadratic growth becomes costly quickly. Quick Sort is usually much faster on average for larger inputs, but the pivot strategy and recursion depth matter. Its simpler recursive implementation is best understood as an algorithm example, not a universal guarantee of fast or safe sorting.
When to use each algorithm
Choose Bubble Sort for learning or tiny, nearly sorted collections—not as a general-purpose production sort. Its implementation is easy to follow when teaching comparison-based sorting, loop invariants, or why quadratic algorithms scale poorly. The early-exit optimization can also make it reasonable for a very small collection that is already sorted or needs only a few local adjustments. Even then, the benefit is narrow: for typical application data, JavaScript's built-in sort is clearer and more thoroughly optimized.
Choose Quick Sort when you need to understand or implement an in-memory general-purpose sort and average-case speed matters. Its average O(n log n) running time makes it a much better fit than Bubble Sort as input sizes grow, and a three-way partition can handle collections with many duplicate values efficiently. It can be useful in algorithm exercises or environments where the sorting strategy must be explicit. The implementation still needs a thoughtful pivot strategy, however; poor partitions can lead to O(n²) work and deep recursion.
For application code, these are usually educational trade-offs rather than a decision to write either algorithm yourself. Prefer JavaScript's built-in sort() with an appropriate comparator: it avoids maintaining a custom implementation and lets the JavaScript engine choose its sorting strategy. If stability, predictable worst-case performance, or memory limits are requirements, check the guarantees of the specific runtime or choose an algorithm designed to meet them instead of assuming Quick Sort provides them.
Big O notation: a simple guide to algorithmic complexity
Big O notation describes how an algorithm's time or extra memory grows as its input size grows. It does not predict an exact runtime in milliseconds; instead, it helps compare how approaches scale. The input size is usually written as n, and Big O focuses on the dominant growth rate rather than constant factors.
An operation that does not depend on the input length is O(1), or constant time. Reading an array element by index is one example:
function getFirst(values) {
return values[0];
}
console.log(getFirst(["red", "green", "blue"])); // "red"
A loop that visits each item once is O(n), or linear time. If the array doubles in size, the number of visits roughly doubles:
function sum(values) {
let total = 0;
for (const value of values) {
total += value;
}
return total;
}
console.log(sum([2, 4, 6])); // 12
Two loops that examine every pair typically produce O(n²), or quadratic time. Doubling the input can make the work roughly four times larger:
function countPairs(values) {
let count = 0;
for (let left = 0; left < values.length; left += 1) {
for (let right = left + 1; right < values.length; right += 1) {
count += 1;
}
}
return count;
}
console.log(countPairs(["a", "b", "c", "d"])); // 6
Binary search is O(log n) because each comparison eliminates about half of the remaining sorted range. It takes around 20 comparisons to search one million sorted values, while a linear search may need to inspect all one million. The input must already be sorted for binary search to work.
Complexity can describe memory as well as time. The sum function uses O(1) extra space because it keeps only one running total. Copying an array before processing it, by contrast, requires O(n) additional space. For a particular algorithm, best-, average-, and worst-case complexity may differ: Quick Sort, for example, averages O(n log n) time but can take O(n²) in its worst case. These examples and runnable search and duplicate-check implementations are available in code/algorithm-complexity-in-javascript.js.
Search algorithms: Linear vs Binary
Searching means locating a value in a collection and, often, returning its index. The right algorithm depends on how the data is arranged, how often it will be searched, and whether that arrangement can be maintained. Linear search works on any array. Binary search can be much faster, but it only works correctly when the array is sorted according to the same ordering used by the comparison.
Linear search: inspect items in order
A linear search starts at the first element and checks each value until it finds a match or reaches the end. It does not need preprocessing, and it works equally well on sorted and unsorted data:
function linearSearch(values, target) {
// Visit each element from left to right.
for (let index = 0; index < values.length; index += 1) {
// Return immediately when this element is the target.
if (values[index] === target) {
return index;
}
}
// No element matched the target.
return -1;
}
const unsortedScores = [42, 17, 8, 31, 17];
console.log(linearSearch(unsortedScores, 31)); // 3
console.log(linearSearch(unsortedScores, 99)); // -1
If the target is first, the search takes O(1) time. If it is last or absent, every element must be checked, so the worst-case time is O(n); an unsuccessful search also takes O(n). The implementation uses O(1) extra space. When duplicates exist, this version returns the index of the first matching value encountered from the left. Linear search is often the simplest choice for small lists, changing data, or a single lookup where sorting first would cost more than scanning.
Binary search: halve a sorted range
Binary search keeps a range of possible positions. It compares the target with the middle element; if they differ, sorted order tells it which half cannot contain the target. Repeating that step reduces the remaining range by roughly half each time:
function binarySearch(sortedValues, target) {
let low = 0;
let high = sortedValues.length - 1;
// Continue while at least one candidate index remains.
while (low <= high) {
// Find the middle without adding the two bounds directly.
const middle = low + Math.floor((high - low) / 2);
const value = sortedValues[middle];
if (value === target) {
// This returns a matching index; duplicates may have other matching indexes.
return middle;
}
if (value < target) {
// The target can only be in the portion to the right.
low = middle + 1;
} else {
// The target can only be in the portion to the left.
high = middle - 1;
}
}
// The candidate range is empty, so the target is not present.
return -1;
}
const sortedScores = [8, 17, 17, 31, 42, 56, 73];
console.log(binarySearch(sortedScores, 31)); // 3
console.log(binarySearch(sortedScores, 99)); // -1
The array must remain sorted in ascending order for this implementation. On each iteration, the bounds move past the middle index, ensuring that the search makes progress and does not examine that same element again. An empty array is handled naturally because its initial range has low greater than high. Binary search takes O(log n) time in the best, average, and worst cases: even for one million items, it needs only about 20 comparisons. It uses O(1) extra space because this iterative version does not create subarrays or use recursion.
There are two details to consider when adopting binary search. First, it does not necessarily return the first occurrence when duplicates are present; the example returns whichever matching middle element it encounters. If the requirement is specifically the first or last duplicate, adjust the algorithm to keep searching the appropriate half after a match. Second, keeping data sorted has a cost. Sorting an unsorted array usually takes O(n log n) time, and inserting into the middle of a JavaScript array can take O(n) because later elements must move. For one search, a linear scan may therefore be cheaper. For many searches against a mostly static, already-sorted array, binary search can substantially reduce lookup work.
| Approach | Data requirement | Worst-case search time | Useful when |
|---|---|---|---|
| Linear search | Any order | O(n) | The collection is small, unsorted, or searched infrequently |
| Binary search | Sorted by the searched value | O(log n) | The sorted collection is searched repeatedly |
In practice, choose the algorithm based on the full data lifecycle, not just the lookup step. If the collection changes often, the work of preserving sorted order can outweigh faster searches. If it is stable and searched frequently, paying once to sort and then using binary search may be a good trade-off. For lookups by a unique key in a frequently changing in-memory collection, a Map may be a more suitable structure than either repeated scanning or maintaining a sorted array.
Real-world use cases
Sorting algorithms are only part of everyday data processing. Interfaces and services also search collections, select records using several fields, and arrange nested objects for display. Built-in array methods express these tasks clearly; knowing the cost of their scans helps you decide when they are sufficient.
Searching an array for a record
For a small in-memory collection, find() is a direct way to retrieve the first record with a matching identifier. It returns undefined when no record matches:
const products = [
{ id: "p-101", name: "Notebook", price: 6.5 },
{ id: "p-102", name: "Pen", price: 1.25 },
{ id: "p-103", name: "Desk lamp", price: 24.0 },
];
function findProduct(products, productId) {
return products.find((product) => product.id === productId);
}
console.log(findProduct(products, "p-102"));
// { id: "p-102", name: "Pen", price: 1.25 }
console.log(findProduct(products, "p-999")); // undefined
This is a linear search: the worst case checks every item, so the time grows as O(n), while the search itself uses O(1) extra space. It is usually a sensible choice for a modest list or an occasional lookup. If an application repeatedly looks up items by ID in a large collection, a Map built once can provide typically O(1) lookups, at the cost of extra memory and keeping the map synchronized with changes.
Filtering and sorting complex objects
Real data often contains nested objects and arrays. For example, an order list can be filtered by a customer's name and by whether an order includes a requested product, then sorted by total:
const orders = [
{
id: "o-501",
customer: { name: "Avery Chen" },
items: [{ product: "Notebook", quantity: 2 }, { product: "Pen", quantity: 3 }],
total: 16.75,
},
{
id: "o-502",
customer: { name: "Jordan Rivera" },
items: [{ product: "Desk lamp", quantity: 1 }],
total: 24.0,
},
{
id: "o-503",
customer: { name: "Avery Chen" },
items: [{ product: "Pen", quantity: 1 }],
total: 1.25,
},
];
function findOrders(orders, customerQuery, productQuery) {
const customer = customerQuery.trim().toLowerCase();
const product = productQuery.trim().toLowerCase();
return orders
.filter((order) => {
const customerMatches = order.customer.name.toLowerCase().includes(customer);
const productMatches = order.items.some((item) =>
item.product.toLowerCase().includes(product)
);
return customerMatches && productMatches;
})
.sort((left, right) => left.total - right.total);
}
console.log(findOrders(orders, "avery", "pen").map((order) => order.id));
// ["o-503", "o-501"]
filter() checks each order, while some() stops checking an order's items as soon as it finds a match. In the worst case, the scan examines every item across every order. filter() creates a new array, so sorting its result does not rearrange the original orders array. The records themselves are shared, however; this example only reads them. If nested fields may be missing or have inconsistent types, validate or normalize them when data enters the application.
Prefer the built-in sort for application code
In ordinary JavaScript programs, prefer Array.prototype.sort() unless there is a specific reason to implement a custom algorithm. Supply a comparator for numeric ordering: without one, the default comparison is lexicographic, so numbers can be ordered like strings rather than by numeric value.
const numbers = [10, 2, 1];
const sorted = numbers.slice().sort((left, right) => left - right);
console.log(sorted); // [1, 2, 10]
console.log(numbers); // [10, 2, 1]
sort() mutates the array it is called on, which is why the example sorts a copy. For custom implementations, test empty and single-element arrays, sorted and reverse-sorted input, duplicates, and negative values. Confirm both the sorted result and the intended mutation behavior.
Bubble Sort teaches how repeated local changes can produce a global result. Quick Sort shows how partitioning can reduce a problem into smaller ones. Understanding their steps, invariants, and complexity helps you recognize the cost of an algorithm—and choose an appropriate tool instead of relying on a single example's performance.
Conclusion: choosing for real-world performance
For most JavaScript applications, start with the built-in Array.prototype.sort() and a comparator that matches the data. It is optimized by the runtime and is easier to maintain than a hand-written sorting algorithm. If the array should remain unchanged, sort a copy or use toSorted() where the supported runtime provides it. Choose another approach only when a measured requirement—such as predictable worst-case time, stability, memory use, or repeated lookups—calls for it.
Bubble Sort is appropriate for learning, or occasionally for a tiny collection where simplicity matters more than speed. Its O(n²) average and worst-case time makes it a poor choice as data grows. Quick Sort illustrates why divide-and-conquer algorithms often perform better on larger collections: its average time is O(n log n). But its worst case is O(n²), and the simple implementation here is not stable, so it is not automatically the best production choice.
In practice, choose based on the workload and the guarantees the application needs. For frequent lookups by key, build a Map rather than repeatedly scanning an array; for large datasets, consider whether sorting should happen in a database or on a server rather than blocking the browser's main thread. Measure with representative data, including already sorted input, duplicates, and unfavorable cases, and account for copying and memory as well as elapsed time. The fastest algorithm on a small benchmark is not necessarily the right choice if it violates ordering requirements or becomes costly to maintain.
Top comments (0)