Benchmark: Versions of Quick 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);

Rendered benchmark preparation results:

Suite status: <idle, ready to run>

Previous results

Test case name	Result
quickSort
quickSort2

Fastest: N/A

Slowest: N/A

Latest run results:

Run details: (Test run date: one year ago)

User agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/128.0.0.0 Safari/537.36

Browser/OS: Chrome 128 on Windows

View result in a separate tab

Test name	Executions per second
quickSort	73333.4 Ops/sec
quickSort2	1485813.6 Ops/sec

Autogenerated LLM Summary (model llama3.2:3b, generated one year ago):

LLMs can make mistakes. Check important info.

I'll provide an in-depth explanation of the provided benchmark, its test cases, and alternatives.

**Overview of Quick Sort**

Quick sort is a popular sorting algorithm that uses the divide-and-conquer technique to sort arrays of elements. It works by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot.

**Benchmark Definition JSON**

The benchmark definition json contains information about the script preparation code for two different versions of Quick Sort: `quickSort` and `quickSort2`. The script prepares an example array `[0, 213, 2, 55312, 322, 1312, 12311123, 54642]`.

**Test Cases**

There are two test cases:

1. **`quickSort`**: This test case runs the original `quickSort` function.
2. **`quickSort2`**: This test case runs the modified `quickSort2` function.

**Comparison of Options**

The two Quick Sort implementations differ in their pivot selection and array manipulation strategies.

*   In `quickSort`, the pivot is selected from the last element of the array (`arr[arr.length - 1]`) and elements are partitioned using a traditional for loop.
*   In `quickSort2`, the pivot is removed from the end of the array (`arr.pop()`) and elements are partitioned using a while loop that shifts elements to the left until it finds an element greater than or equal to the pivot.

**Pros and Cons**

Here's a brief summary of the pros and cons for each implementation:

*   `quickSort`:
    *   Pros: Simple to implement, easy to understand.
    *   Cons: Not efficient in terms of performance (O(n^2) on average), vulnerable to worst-case scenarios (e.g., already sorted or reverse-sorted arrays).
*   `quickSort2`:
    *   Pros: More efficient than traditional quick sort (O(n log n) on average), less prone to worst-case scenarios.
    *   Cons: More complex implementation, potentially harder to understand and debug.

**Library Usage**

There is no library usage in this benchmark. However, the standard JavaScript library provides various utility functions like `Array.prototype.sort()` that could be used as alternatives for sorting arrays.

**Special JS Features or Syntax**

This benchmark does not use any special JavaScript features or syntax. It only demonstrates basic programming concepts like function definitions, loops, and conditional statements.

**Alternatives**

Some alternative sorting algorithms you may consider:

*   **Merge Sort**: A divide-and-conquer algorithm that splits the array into smaller sub-arrays, sorts them individually, and merges them back together.
*   **Heap Sort**: A comparison-based sorting algorithm that uses a binary heap data structure to sort elements efficiently.
*   **Radix Sort**: A non-comparison sorting algorithm that sorts integers by their digits using radix sorting.

You can explore these algorithms and compare their performance with Quick Sort on MeasureThat.net or other benchmarking platforms.

Related benchmarks:

Versions of Quick Sort (version: 0)

Comparing performance of: quickSort vs quickSort2

Created: 8 years ago by: Guest

Jump to the latest result

quickSort

quickSort2

Suite status: <idle, ready to run>

Fastest: N/A

Slowest: N/A

Autogenerated LLM Summary (model llama3.2:3b, generated one year ago):