Skip to main content

Quick Sort in JavaScript

Quick Sort, devised by Tony Hoare in 1959, leverages the divide-and-conquer strategy. It selects a pivot element and then arranges all smaller elements to one side and larger ones to the other.

Quick Sort Under the Hook

Quick Sort operates in three steps:

  1. Selecting a pivot.

  2. Shifting elements smaller than the pivot to one side, and moving elements larger than the pivot to the other side.

  3. Repeating these steps for both sides separately.

Consider, for instance, sorting [3, 9, 4, 7, 5, 1, 6, 2, 8] with 7 as the pivot. After one round, it becomes [3, 4, 5, 1, 6, 2, 7, 9, 8]. The pivot 7 is correctly placed, and we can then divide the array into two parts: [3, 4, 5, 1, 6] and [9, 8], which can be sorted separately.

Quick Sort Implementation in JavaScript : Partition

Let's implement Quick Sort in JavaScript. First, we partition the array around the pivot in our partition function:

In this portion of the code, we selected the last element as the pivot and placed smaller elements on the left. The function starts by initialising i to one index before the start. This basically keeps track of the latest position where an element has been swapped because it was less than or equal to the pivot. If arr[j] is less than or equal to the pivot, i is incremented, and then arr[j] is swapped with arr[i]. Essentially, smaller elements get pushed towards the front of the array (or the given part of the array).

The start and end parameters control which part of the given array is under the partition operation. Using these parameters, we can apply partition to some part of the array, which will be helpful later.


Quick Sort Implementation in JavaScript : Sorting

Then, we apply Quick Sort with a function that invokes partition and recursively sorts the two halves:

Spot on! We've just created a fully functioning Quick Sort algorithm in JavaScript.

Honing In On Quick Sort Efficiency

The time complexity of Quick Sort can vary. Generally speaking, the more unique items there are, the quicker Quick Sort works. In the best and average cases, it shines with a time complexity of O(n∗log(n)). However, the time complexity can degrade to O(n2) in the worst case.

Comments

Post a Comment

Popular posts from this blog

JavaScript Maps

Dive Into JavaScript Maps A Map stores data as key-value pairs. We'll recall how to create Maps, implement them, and delve into the details of their memory management. Understanding JavaScript Maps Maps are versatile data structures in JavaScript. They store key-value pairs and accept any data type as a key — even objects and functions! Here is how we create an empty Map: let myMap = new Map(); // creates an empty Map Here, myMap is a new JavaScript Map, eagerly awaiting to store your keys and values. Meander Through Map Methods Maps provide some essential built-in methods: set(key, value): Stores a key-value pair. get(key): Retrieves the value of a key. has(key): Checks if a key exists and returns true or false. delete(key): Erases a key-value pair. size: Returns the count of key-value pairs. To gain a better understanding, let's apply these methods: let myMap = new Map(); // Add pairs with set myMap.set('apples', 10); // Adds a new pair myMap.set('bananas', 6...
Post a Comment
Read more

How to work with Set in JavaScript

Understanding JavaScript Sets Set in JavaScript is an unordered collection of unique values. We can examine the size of the set using .size method. Notice that the set is unordered, and we can't guarantee that elements will be shown in the order we added them. Sets work similarly to JavaScript objects but are designed for uniqueness. They use hashing, a way to convert a given pearl into a unique code, which facilitates rapid storage and retrieval. When checking if an item is in a Set, JavaScript computes its hash code to locate it, much like a map leading to a treasure. Sets have numerous practical uses in database management, data analysis , and more . Problem 1: Check if Two Sets are Disjoint Let's begin by considering the function, areDisjoint which takes two arrays and determines if they are disjoint, meaning they have no elements in common. This is crucial when analysing datasets for overlapping values, similar to ensuring that two puzzle pieces from different puzzles d...
Post a Comment
Read more

The Synergy Between DevOps and Agile Methodologies

When it comes to modern software development practices, two methodologies have gained significant traction in recent years: DevOps and Agile. While they are distinct in their approaches, DevOps and Agile share common goals of improving collaboration, efficiency, and quality in software development processes. Understanding DevOps DevOps  is a set of practices that combines software development (Dev) and IT operations (Ops) to shorten the systems development life cycle and provide continuous delivery of high-quality software. It emphasizes collaboration, automation, and monitoring throughout the software delivery process. Key principles of DevOps include: Automation of processes Continuous integration and delivery Monitoring and feedback loops Collaboration between teams Exploring Agile Methodologies Agile  is an iterative approach to software development that focuses on delivering value to customers through incremental and iterative development. Agile methodologies promote adap...
Post a Comment
Read more