search
HomeWeb Front-endJS TutorialAn in-depth analysis of quick sort in JavaScript

An in-depth analysis of quick sort in JavaScript

Oct 28, 2020 pm 05:47 PM
javascriptfront endQuick sortalgorithm

An in-depth analysis of quick sort in JavaScript

Introduction

Sorting refers to arranging the elements of a linear list in a specific order (numeric or alphabetical). Sorting is often used in conjunction with search.

There are many sorting algorithms, and one of the fastest by far is Quicksort(Quicksort).

Quicksort sorts the given list elements using the divide-and-conquer strategy. This means that the algorithm breaks the problem into subproblems until the subproblems become simple enough to be solved directly.

Algorithmically, this can be achieved using recursion or looping. But for this problem, it is more natural to use recursion.

Understand the logic behind quick sort

First look at how quick sort works:

  1. Select an element in the array, this element is called Benchmark(Pivot). Usually the first or last element in the array is used as the basis.
  2. Then, rearrange the elements of the array so that all elements to the left of the pivot are smaller than the pivot, and all elements to the right are greater than the pivot. This step is called Partitioning. If an element is equal to the base, it doesn't matter which side it is on.
  3. Repeat this process for the left and right sides of the benchmark until the array is sorted.

Next, understand these steps through an example. Suppose there is an array containing unsorted elements [7, -2, 4, 1, 6, 5, 0, -4, 2]. Select the last element as the base. The decomposition steps of the array are shown in the figure below:

An in-depth analysis of quick sort in JavaScript

The elements selected as the basis in step 1 of the algorithm are colored. After partitioning, the base element is always at the correct position in the array.

The array with a bold black border represents what it will look like at the end of that particular recursive branch, with the resulting array containing only one element.

Finally you can see the sorting of the results of the algorithm.

Use JavaScript to implement quick sort

The backbone of this algorithm is the "partitioning" step. Whether using recursion or looping, this step is the same.

It is precisely because of this feature that the code for array partitioning is first written partition():

function partition(arr, start, end){
    // 以最后一个元素为基准
    const pivotValue = arr[end];
    let pivotIndex = start; 
    for (let i = start; i < end; i++) {
        if (arr[i] < pivotValue) {
        // 交换元素
        [arr[i], arr[pivotIndex]] = [arr[pivotIndex], arr[i]];
        // 移动到下一个元素
        pivotIndex++;
        }
    }
    
    // 把基准值放在中间
    [arr[pivotIndex], arr[end]] = [arr[end], arr[pivotIndex]] 
    return pivotIndex;
};

The code is based on the last element and uses the variable pivotIndex to track the "middle" position where all elements to the left are smaller than pivotValue and elements to the right are larger than pivotValue.

The final step swaps the pivot (last element) with pivotIndex.

Recursive implementation

After implementing the partition() function, we must solve the problem recursively and apply partitioning logic to complete the remaining steps:

function quickSortRecursive(arr, start, end) {
    // 终止条件
    if (start >= end) {
        return;
    }
    
    // 返回 pivotIndex
    let index = partition(arr, start, end);
    
    // 将相同的逻辑递归地用于左右子数组
    quickSort(arr, start, index - 1);
    quickSort(arr, index + 1, end);
}

In this function, the array is first partitioned, and then the left and right subarrays are partitioned. As long as this function receives an array that is not empty or has more than one element, the process will be repeated.

Empty arrays and arrays containing only one element are considered sorted.

Finally use the following example to test:

array = [7, -2, 4, 1, 6, 5, 0, -4, 2]
quickSortRecursive(array, 0, array.length - 1)

console.log(array)

Output:

-4,-2,0,1,2,4,5,6,7

Loop implementation

The recursive method of quick sort is more intuitive. But using loops to implement quick sort is a relatively common interview question.

Like most recursive to loop conversion solutions, the first thing that comes to mind is to use a stack to simulate recursive calls. Doing this allows you to reuse some familiar recursive logic and use it in loops.

We need a way to keep track of the remaining unsorted subarrays. One approach is to simply keep "pairs" of elements on the stack that represent the start and end of a given unsorted subarray.

JavaScript does not have an explicit stack data structure, but arrays support the push() and pop() functions. However, the peek() function is not supported, so you must use stack [stack.length-1] to manually check the top of the stack.

We will use the same "partitioning" function as the recursive method. Take a look at how to write the Quicksort part:

function quickSortIterative(arr) {
    // 用push()和pop()函数创建一个将作为栈使用的数组
    stack = [];
    
    // 将整个初始数组做为“未排序的子数组”
    stack.push(0);
    stack.push(arr.length - 1);
    
    // 没有显式的peek()函数
    // 只要存在未排序的子数组,就重复循环
    while(stack[stack.length - 1] >= 0){
        
        // 提取顶部未排序的子数组
        end = stack.pop();
        start = stack.pop();
        
        pivotIndex = partition(arr, start, end);
        
        // 如果基准的左侧有未排序的元素,
        // 则将该子数组添加到栈中,以便稍后对其进行排序
        if (pivotIndex - 1 > start){
            stack.push(start);
            stack.push(pivotIndex - 1);
        }
        
        // 如果基准的右侧有未排序的元素,
        // 则将该子数组添加到栈中,以便稍后对其进行排序
        if (pivotIndex + 1 < end){
            stack.push(pivotIndex + 1);
            stack.push(end);
        }
    }
}

Here is the test code:

ourArray = [7, -2, 4, 1, 6, 5, 0, -4, 2]
quickSortIterative(ourArray)

console.log(ourArray)

Output:

-4,-2,0,1,2,4,5,6,7

Visual demonstration

When it comes to sorting algorithms, Visualizing them can help us intuitively understand how they work. The following example is taken from Wikipedia:

An in-depth analysis of quick sort in JavaScript

The last element in the figure is also used as a benchmark. Given an array partitioned, recursively traverse the left side until it is completely sorted. Then sort the right side.

Efficiency of quick sort

Now discuss its time and space complexity. The worst-case time complexity of quick sort is $O(n^2)$. The average time complexity is $O(n\log n)$. Typically, worst-case scenarios can be avoided by using a randomized version of quicksort.

The weakness of the quicksort algorithm is the choice of benchmark. Each time you choose a wrong pivot (a pivot larger or smaller than most elements) you will get the worst possible time complexity. When repeatedly selecting a basis, if the element value is smaller or larger than the element's basis, the time complexity is $O(n\log n)$.

It can be observed from experience that no matter which data benchmark selection strategy is adopted, the time complexity of quick sort tends to have $O(n\log n)$.

Quicksort does not take up any additional space (excluding space reserved for recursive calls). This algorithm is called the in-place algorithm and requires no extra space.

For more programming-related knowledge, please visit: Introduction to Programming! !

The above is the detailed content of An in-depth analysis of quick sort in JavaScript. For more information, please follow other related articles on the PHP Chinese website!

Statement
This article is reproduced at:stackabuse. If there is any infringement, please contact admin@php.cn delete
From C/C   to JavaScript: How It All WorksFrom C/C to JavaScript: How It All WorksApr 14, 2025 am 12:05 AM

The shift from C/C to JavaScript requires adapting to dynamic typing, garbage collection and asynchronous programming. 1) C/C is a statically typed language that requires manual memory management, while JavaScript is dynamically typed and garbage collection is automatically processed. 2) C/C needs to be compiled into machine code, while JavaScript is an interpreted language. 3) JavaScript introduces concepts such as closures, prototype chains and Promise, which enhances flexibility and asynchronous programming capabilities.

JavaScript Engines: Comparing ImplementationsJavaScript Engines: Comparing ImplementationsApr 13, 2025 am 12:05 AM

Different JavaScript engines have different effects when parsing and executing JavaScript code, because the implementation principles and optimization strategies of each engine differ. 1. Lexical analysis: convert source code into lexical unit. 2. Grammar analysis: Generate an abstract syntax tree. 3. Optimization and compilation: Generate machine code through the JIT compiler. 4. Execute: Run the machine code. V8 engine optimizes through instant compilation and hidden class, SpiderMonkey uses a type inference system, resulting in different performance performance on the same code.

Beyond the Browser: JavaScript in the Real WorldBeyond the Browser: JavaScript in the Real WorldApr 12, 2025 am 12:06 AM

JavaScript's applications in the real world include server-side programming, mobile application development and Internet of Things control: 1. Server-side programming is realized through Node.js, suitable for high concurrent request processing. 2. Mobile application development is carried out through ReactNative and supports cross-platform deployment. 3. Used for IoT device control through Johnny-Five library, suitable for hardware interaction.

Building a Multi-Tenant SaaS Application with Next.js (Backend Integration)Building a Multi-Tenant SaaS Application with Next.js (Backend Integration)Apr 11, 2025 am 08:23 AM

I built a functional multi-tenant SaaS application (an EdTech app) with your everyday tech tool and you can do the same. First, what’s a multi-tenant SaaS application? Multi-tenant SaaS applications let you serve multiple customers from a sing

How to Build a Multi-Tenant SaaS Application with Next.js (Frontend Integration)How to Build a Multi-Tenant SaaS Application with Next.js (Frontend Integration)Apr 11, 2025 am 08:22 AM

This article demonstrates frontend integration with a backend secured by Permit, building a functional EdTech SaaS application using Next.js. The frontend fetches user permissions to control UI visibility and ensures API requests adhere to role-base

JavaScript: Exploring the Versatility of a Web LanguageJavaScript: Exploring the Versatility of a Web LanguageApr 11, 2025 am 12:01 AM

JavaScript is the core language of modern web development and is widely used for its diversity and flexibility. 1) Front-end development: build dynamic web pages and single-page applications through DOM operations and modern frameworks (such as React, Vue.js, Angular). 2) Server-side development: Node.js uses a non-blocking I/O model to handle high concurrency and real-time applications. 3) Mobile and desktop application development: cross-platform development is realized through ReactNative and Electron to improve development efficiency.

The Evolution of JavaScript: Current Trends and Future ProspectsThe Evolution of JavaScript: Current Trends and Future ProspectsApr 10, 2025 am 09:33 AM

The latest trends in JavaScript include the rise of TypeScript, the popularity of modern frameworks and libraries, and the application of WebAssembly. Future prospects cover more powerful type systems, the development of server-side JavaScript, the expansion of artificial intelligence and machine learning, and the potential of IoT and edge computing.

Demystifying JavaScript: What It Does and Why It MattersDemystifying JavaScript: What It Does and Why It MattersApr 09, 2025 am 12:07 AM

JavaScript is the cornerstone of modern web development, and its main functions include event-driven programming, dynamic content generation and asynchronous programming. 1) Event-driven programming allows web pages to change dynamically according to user operations. 2) Dynamic content generation allows page content to be adjusted according to conditions. 3) Asynchronous programming ensures that the user interface is not blocked. JavaScript is widely used in web interaction, single-page application and server-side development, greatly improving the flexibility of user experience and cross-platform development.

See all articles

Hot AI Tools

Undresser.AI Undress

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Undress AI Tool

Undress AI Tool

Undress images for free

Clothoff.io

Clothoff.io

AI clothes remover

AI Hentai Generator

AI Hentai Generator

Generate AI Hentai for free.

Hot Article

R.E.P.O. Energy Crystals Explained and What They Do (Yellow Crystal)
3 weeks agoBy尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. Best Graphic Settings
3 weeks agoBy尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. How to Fix Audio if You Can't Hear Anyone
4 weeks agoBy尊渡假赌尊渡假赌尊渡假赌
WWE 2K25: How To Unlock Everything In MyRise
1 months agoBy尊渡假赌尊渡假赌尊渡假赌

Hot Tools

ZendStudio 13.5.1 Mac

ZendStudio 13.5.1 Mac

Powerful PHP integrated development environment

SublimeText3 Linux new version

SublimeText3 Linux new version

SublimeText3 Linux latest version

VSCode Windows 64-bit Download

VSCode Windows 64-bit Download

A free and powerful IDE editor launched by Microsoft

SublimeText3 Mac version

SublimeText3 Mac version

God-level code editing software (SublimeText3)

Dreamweaver CS6

Dreamweaver CS6

Visual web development tools