Select the pivot element which is the first element of the array
Mark first element as 'i' and the last element as 'j'
Increment i if arr[i] <= pivot
Decrement j if arr[j] > pivot
After incrementing i and decrementing j as per the last two steps, swap arr[i] and arr[j]
Once i crosses j, in other words, if j>i then swap arr[j] with pivot and return j
Now, after the partition procedure, we'll get two parts, the left partitioned and the right partitioned part. Perform quick sort recursively on both these parts.
const arr = [50, 70, 60, 90, 40, 80, 10, 20, 30];
const swap = (indexOne, indexTwo) => {
// ES6 way -> array destructuring
[arr[indexOne], arr[indexTwo]] = [arr[indexTwo], arr[indexOne]]
/*
The above line is same as doing
const temp = arr[indexTwo]
arr[indexTwo] = arr[indexOne]
arr[indexOne] = temp
*/
}
function partition(arr, low, high) {
const pp = arr[low]
let i = low, j = high
while (j > i) {
do {
i++
} while (arr[i] <= pp)
while (arr[j] > pp) {
j--
}
if (j > i) {
swap(i, j)
}
}
swap(low, j)
return j
}
function quickSort(arr, low, high) {
if (low < high) {
const pp = partition(arr, low, high)
quickSort(arr, 0, pp)
quickSort(arr, pp + 1, high)
}
}
const qs = quickSort(arr, 0, arr.length - 1)
console.log(arr) //[ 10, 20, 30, 40, 50, 60, 70, 80, 90 ]
Time-complexity of quicksort
If the list is sorted in ascending or descending order then the list is traversed 1+2+3+4...+n so it'n^2
The worst case is therefore n^2
The best case happens when j appears at the center of the list. In this case, it will be nlogn
2. Bubble Sort
3. Selection Sort
4. Merge Sort
5. Count Sort
6. Radix Sort
7. Bin / Bucket Sort
8. Shell Sort
Linked List
Operations
Display linked list
Insert an element at first place (head)
Insert an element at last place
Insert an element at any place (index)
Get the element at an index
Delete an element
Delete all elements
Reverse linked list (2 ways -> copy to array and back, reverse links)
Concatenate two linked lists
Merge two linked lists
// Create Node
class Node {
constructor(element, nextNode) {
this.element = element;
this.nextNode = nextNode
}
}
// Create LinkedList
class LinkedList {
constructor() {
this.head = null;
this.size = 0
}
// insertAtHead
insertAtHead(element) {
// create a node
// point this to head node -> next node of new node should be current head node
const newHeadNode = new Node(element, this.head)
this.head = newHeadNode
this.size++
}
// printList -> prints all elements
printList() {
let currentNode = this.head
while (currentNode) {
console.log(currentNode.element)
currentNode = currentNode.nextNode
}
}
// get At
getAt(index) {
// check of index is proper
if (index > this.size && index < 0) {
return null
}
let currentIndex = 0
let currentNode = this.head
while (currentIndex <= index) {
if (currentIndex === index) {
return currentNode?.element || null
}
currentNode = currentNode.nextNode
currentIndex++
}
}
// get All in an array
getAll() {
const linkedListArray = []
let currentNode = this.head
while (currentNode) {
linkedListArray.push(currentNode.element)
currentNode = currentNode.nextNode
}
return linkedListArray
}
// insertAtTail
insertAtTail(element) {
const tailNode = new Node(element, null);
let currentNode = this.head
if (!currentNode) {
this.head = tailNode
return
}
while (currentNode) {
console.log(currentNode)
if (!currentNode.nextNode) {
currentNode.nextNode = tailNode
return
}
currentNode = currentNode.nextNode
}
}
// insertAtIndex
insertAtIndex(index, element) {
if (index >= this.size || index < 0) return
let currentIndex = 0
let previousNode = this.head
let currentNode = this.head
while (currentIndex <= index) {
if (currentIndex === index) {
if (index === 0) {
// this.head = new Node(element, this.head)
this.insertAtHead(element)
return
}
previousNode.nextNode = new Node(element, currentNode)
return
}
previousNode = currentNode
currentNode = currentNode.nextNode
currentIndex++
}
}
// removeFirst
removeFirst() {
this.head = this.head.nextNode
}
// removeLast
removeLast() {
let currentNode = this.head
let previousNode = this.head
while (currentNode) {
if (!currentNode.nextNode) {
previousNode.nextNode = null
return
}
previousNode = currentNode
currentNode = currentNode.nextNode
}
}
// removeAtIndex
removeAt(index) {
if (index > this.size) {
return
}
let currentIndex = 0
let currentNode = this.head
let previousNode = this.head
while (currentNode) {
if (index === currentIndex) {
//remove element
if (index === 0) {
this.head = currentNode.nextNode
return
}
previousNode.nextNode = currentNode.nextNode
return
}
previousNode = currentNode
currentNode = currentNode.nextNode
currentIndex++
}
}
// removeAll
removeAll() {
this.head = null
}
// concatenate / join two lists
static concatLists(l1, l2) {
let newLL = new LinkedList()
let currentL1Node = l1.head
let currentL2Node = l2.head
while (currentL1Node) {
newLL.insertAtHead(currentL1Node.element)
if (!currentL1Node.nextNode) break
currentL1Node = currentL1Node.nextNode
}
while (currentL2Node) {
newLL.insertAtHead(currentL2Node.element)
if (!currentL2Node.nextNode) break
currentL2Node = currentL2Node.nextNode
}
return newLL.getAll()
}
// merge two lists
static mergeSortedLists(l1, l2) {
let firstNode = l1.head
let secondNode = l2.head
let thirdNode = null
let lastNode = null
// initially check which head is small and get the third and fourth on that head
if (firstNode.element < secondNode.element) {
thirdNode = lastNode = firstNode
firstNode = firstNode.nextNode
lastNode.nextNode = null
} else {
thirdNode = lastNode = secondNode
secondNode = secondNode.nextNode
lastNode.nextNode = null
}
while (firstNode && secondNode) {
if (firstNode.element < secondNode.element) {
lastNode.nextNode = firstNode
lastNode = firstNode
firstNode = firstNode.nextNode
lastNode.nextNode = null
} else {
lastNode.nextNode = secondNode
lastNode = secondNode
secondNode = secondNode.nextNode
lastNode.nextNode = null
}
}
if (firstNode) {
lastNode.nextNode = firstNode
} else if (secondNode) {
lastNode.nextNode = secondNode
}
while (thirdNode) {
console.log(thirdNode.element)
thirdNode = thirdNode?.nextNode
}
console.log(l1)
console.log(l2)
}
}
let ll = new LinkedList()
ll.insertAtHead(70)
ll.insertAtHead(30)
ll.insertAtHead(10)
// ll.removeAt(3)
// ll.removeFirst()
// ll.removeLast()
// ll.removeAll()
// console.log(ll.getAt(1))
// console.log(ll.getAll())
let l2 = new LinkedList()
l2.insertAtHead(3000)
l2.insertAtHead(2000)
l2.insertAtHead(1000)
// const arr = LinkedList.concatLists(ll, l2)
// console.log(arr)
LinkedList.mergeSortedLists(ll, l2)
