Benchmark: quicksort - MeasureThat.net

Script Preparation code:

var items = [5,3,7,6,2,9,63, 95, 63, 26, 76, 19, 65, 8, 63, 26];

Tests:

t1
function swap(items, leftIndex, rightIndex){ var temp = items[leftIndex]; items[leftIndex] = items[rightIndex]; items[rightIndex] = temp; } function partition(items, left, right) { var pivot = items[Math.floor((right + left) / 2)], //middle element i = left, //left pointer j = right; //right pointer while (i <= j) { while (items[i] < pivot) { i++; } while (items[j] > pivot) { j--; } if (i <= j) { swap(items, i, j); //sawpping two elements i++; j--; } } return i; } function quickSort(items, left, right) { var index; if (items.length > 1) { index = partition(items, left, right); //index returned from partition if (left < index - 1) { //more elements on the left side of the pivot quickSort(items, left, index - 1); } if (index < right) { //more elements on the right side of the pivot quickSort(items, index, right); } } return items; } console.log(quickSort(items, 0, items.length - 1));
t2
function quickSortBasic(array) { if(array.length < 2) { return array; } var pivot = array[0]; var lesserArray = []; var greaterArray = []; for (var i = 1; i < array.length; i++) { if ( array[i] > pivot ) { greaterArray.push(array[i]); } else { lesserArray.push(array[i]); } } return quickSortBasic(lesserArray).concat(pivot, quickSortBasic(greaterArray)); } console.log(quickSortBasic(items, 0, items.length - 1));

Rendered benchmark preparation results:

Suite status: <idle, ready to run>

Previous results

Test case name	Result
t1
t2

Fastest: N/A

Slowest: N/A

Latest run results:

Run details: (Test run date: 4 years ago)

User agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10_15_5) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/84.0.4147.135 Safari/537.36

Browser/OS: Chrome 84 on Mac OS X 10.15.5

View result in a separate tab

Test name	Executions per second
t1	39661.8 Ops/sec
t2	35711.2 Ops/sec

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

LLMs can make mistakes. Check important info.

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

**Benchmark Definition:**

The benchmark definition is for a JavaScript implementation of the Quicksort algorithm, which is a popular sorting algorithm that 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. The sub-arrays are then recursively sorted.

**Script Preparation Code:**

The script preparation code generates an array of 18 random integers:
```javascript
var items = [5,3,7,6,2,9,63, 95, 63, 26, 76, 19, 65, 8, 63, 26];
```
This code is executed only once before the benchmark runs.

**Html Preparation Code:**

There is no HTML preparation code specified.

**Individual Test Cases:**

The benchmark has two test cases:

1. **t1 (Original Quicksort Implementation):**
```javascript
function swap(items, leftIndex, rightIndex){...}
function partition(items, left, right) {...}
function quickSort(items, left, right) {...}

console.log(quickSort(items, 0, items.length - 1));
```
This implementation is the original Quicksort algorithm.

2. **t2 (Simplified Quicksort Implementation):**
```javascript
function quickSortBasic(array) {...}

console.log(quickSortBasic(items, 0, items.length - 1));
```
This implementation uses a simplified version of the Quicksort algorithm, which works by:

a. Selecting the first element as the pivot.
b. Creating two arrays: `lesserArray` for elements less than the pivot and `greaterArray` for elements greater than the pivot.
c. Recursively sorting `lesserArray` and `greaterArray`.
d. Concatenating the sorted sub-arrays, including the pivot.

**Options Compared:**

The benchmark compares the performance of two Quicksort implementations:

1. The original implementation (t1), which follows the standard Quicksort algorithm.
2. The simplified implementation (t2), which uses a simpler approach to partitioning and sorting.

**Pros and Cons:**

**Original Implementation (t1):**

Pros:

* Follows the standard Quicksort algorithm, which is well-established and efficient.
* Allows for easier understanding of the algorithm's logic.

Cons:

* May have higher overhead due to the recursive function calls.
* Can be slower for smaller arrays due to the overhead of the recursive calls.

**Simplified Implementation (t2):**

Pros:

* Simplifies the partitioning process, making it faster and more efficient.
* Reduces the number of recursive function calls, potentially improving performance.

Cons:

* Uses a simpler approach that may not be as intuitive or well-understood as the original implementation.
* May have higher overhead due to the creation of temporary arrays.

**Other Considerations:**

* The benchmark uses Chrome 84 on a Macintosh with Intel processor, which is an older version of Chrome. More recent versions of Chrome may have different performance characteristics.
* The test cases are designed to compare the performance of two Quicksort implementations, but it would be interesting to see how they perform against other sorting algorithms, such as Merge Sort or Heap Sort.

**Alternatives:**

Other sorting algorithms that could be compared in a benchmark include:

1. **Merge Sort:** A divide-and-conquer algorithm that splits the array into smaller sub-arrays and merges them back together.
2. **Heap Sort:** An in-place sorting algorithm that uses a heap data structure to sort the array.
3. **Radix Sort:** A non-comparative sorting algorithm that sorts integers by their individual digits.

These alternatives could provide interesting comparisons with the Quicksort implementations, especially for large arrays or specific use cases where certain characteristics are important (e.g., stability).

Related benchmarks:

quicksort (version: 0)

Comparing performance of: t1 vs t2

Created: 4 years ago by: Guest

Jump to the latest result

t1

t2

Suite status: <idle, ready to run>

Experimental features:

Fastest: N/A

Slowest: N/A

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