Benchmark: Versions of Quick Sort vs. .sort

Script Preparation code:

var array = [0, 213, 2, 55312, 322, 1312, 12311123, 54642 ];
function quickSort(arr){
  if(arr.length <= 1) return arr
  const pivot = arr[arr.length - 1]
  let left = []
  let right = []
  for(let i = 0; i < arr.length-1; i++){
    if (arr[i] < pivot) {
      left.push(arr[i])
    } else {
      right.push(arr[i])
    }
  }
  return [].concat(quickSort(left),pivot,quickSort(right))
}
function quickSort2(arr){
  if(arr.length <= 1) return arr
  const pivot = arr.pop()
  let left = []
  let right = []
  while(arr[0]){
    if (arr[0] < pivot) {
      left.push(arr.shift())
    } else {
      right.push(arr.shift())
    }
  }
  return [].concat(quickSort(left),pivot,quickSort(right))
}

Tests:

quickSort
quickSort(array);
quickSort2
quickSort2(array);
built in sort
array.sort(function (a, b) { return a - b });

Rendered benchmark preparation results:

Suite status: <idle, ready to run>

Previous results

Test case name	Result
quickSort
quickSort2
built in sort

Fastest: N/A

Slowest: N/A

Latest run results:

Run details: (Test run date: 2 months ago)

User agent: Mozilla/5.0 (X11; Ubuntu; Linux x86_64; rv:134.0) Gecko/20100101 Firefox/134.0

Browser/OS: Firefox 134 on Ubuntu

View result in a separate tab

Test name	Executions per second
quickSort	2465510.5 Ops/sec
quickSort2	273207392.0 Ops/sec
built in sort	86784912.0 Ops/sec

Autogenerated LLM Summary (model llama3.2:3b, generated 6 months ago):

LLMs can make mistakes. Check important info.

Let's break down the provided benchmark definition and test cases.

**Benchmark Definition**

The benchmark is to compare three different implementations of the Quick Sort algorithm:

1.  `quickSort` (Implementation 1)
2.  `quickSort2` (Implementation 2)

Both implementations are sorting an array of numbers in ascending order.

The third implementation, `.sort`, is a built-in JavaScript method for sorting arrays.

**What's being tested?**

Each test case measures the performance of one specific implementation:

*   Test Case 1: `quickSort`
*   Test Case 2: `quickSort2` (an alternative implementation of Quick Sort)
*   Test Case 3: `.sort`

The benchmark is designed to compare these three implementations on the same dataset, array `[0, 213, 2, 55312, 322, 1312, 12311123, 54642]`.

**Options compared**

Here are the options being compared:

*   **Quick Sort**: Two different implementations (`quickSort` and `quickSort2`). These implementations differ in their pivot selection strategies.
    *   **Pros of Quick Sort:**
        *   Generally faster than other sorting algorithms like Insertion Sort or Selection Sort, especially for large datasets.
        *   Good performance even with a small number of elements.
    *   **Cons of Quick Sort:**
        *   Can be slow if the input array is already sorted (leading to many unnecessary comparisons).
        *   Requires extra memory for recursion stack when using iterative implementation like `quickSort2`.
*   **Built-in sort**: The JavaScript method `.sort()`, which uses a modified merge sort algorithm.
    *   **Pros of built-in sort:**
        *   Convenient and easy to use (no need to implement from scratch).
        *   Handles edge cases well, such as duplicate values or NaNs.
    *   **Cons of built-in sort:**
        *   Can be slower than Quick Sort for large datasets due to its overhead.
        *   May not perform as well on certain types of data (e.g., unsorted arrays).

**Library and libraries' purpose**

In this benchmark, the following library is used:

*   **None**, since all implementations are custom-written JavaScript code.

However, in general, when working with JavaScript or other programming languages, some libraries might be useful for specific tasks:

*   **Lodash**: A popular JavaScript utility library that provides many helpful functions, such as `forEach`, `map`, and `sort`.
    *   Purpose: Simplify common operations like iteration, filtering, and manipulation of data.

**Special JS features or syntax**

There is no special JavaScript feature or syntax used in this benchmark. However:

*   **ES6+ syntax**: The code uses modern JavaScript features like arrow functions (`() => { }`) and template literals (`'\r\n'`).
    *   Purpose: Improve code readability, conciseness, and maintainability.

**Alternatives**

Other alternatives for sorting algorithms include:

*   **Merge Sort**: A divide-and-conquer algorithm that's similar to Quick Sort but has a guaranteed O(n log n) time complexity.
*   **Heap Sort**: Another divide-and-conquer algorithm that uses a binary heap data structure. It has an average time complexity of O(n log n).
*   **Radix Sort**: A non-comparative sorting algorithm that sorts integers or strings based on the digits or characters in their radix (base) representation.
    *   Purpose: Efficiently sort large datasets, especially those with numerical values.

In general, the choice of sorting algorithm depends on the specific requirements and constraints of your project, such as:

*   **Data size**: Larger datasets might benefit from more efficient algorithms like Quick Sort or Merge Sort.
*   **Data type**: Sorting numerical data requires different techniques than sorting strings or objects.
*   **Performance**: Faster algorithms are often preferred when speed is critical.

I hope this explanation has been helpful in understanding the benchmark and its test cases.

Related benchmarks:

Versions of Quick Sort vs. .sort (version: 0)

Comparing performance of: quickSort vs quickSort2 vs built in sort

Created: 4 years ago by: Guest

Jump to the latest result

quickSort

quickSort2

built in sort

Suite status: <idle, ready to run>

Experimental features:

Fastest: N/A

Slowest: N/A

Autogenerated LLM Summary (model llama3.2:3b, generated 6 months ago):