Avinash Maurya

Posted on

# Sorting algorithms

Common sorting algorithms implemented in JavaScript, along with simple definitions, examples, and indications of whether they are stable or not:

### 1. Bubble Sort:

• Stability: Stable

• Description: Repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order.

function bubbleSort(arr) {

const n = arr.length;

for (let i = 0; i < n - 1; i++) {

for (let j = 0; j < n - i - 1; j++) {

if (arr[j] > arr[j + 1]) {

[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];

}

}

}

return arr;

}

### 2. Selection Sort:

• Stability: Not stable

• Description: Divides the array into a sorted and an unsorted region, repeatedly selects the smallest element from the unsorted region, and moves it to the sorted region.

function selectionSort(arr) {

const n = arr.length;

for (let i = 0; i < n - 1; i++) {

let minIndex = i;

for (let j = i + 1; j < n; j++) {

if (arr[j] < arr[minIndex]) {

minIndex = j;

}

}

[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];

}

return arr;

}

### 3. Insertion Sort:

• Stability: Stable

• Description: Builds the sorted array one item at a time by repeatedly taking the next element and inserting it into the already sorted part.

function insertionSort(arr) {

const n = arr.length;

for (let i = 1; i < n; i++) {

let key = arr[i];

let j = i - 1;

while (j >= 0 && arr[j] > key) {

arr[j + 1] = arr[j];

j--;

}

arr[j + 1] = key;

}

return arr;

}

### 4. Merge Sort:

• Stability: Stable

• Description: Divides the array into two halves, recursively sorts each half, and then merges them together.

function mergeSort(arr) {

if (arr.length <= 1) {

return arr;

}

const middle = Math.floor(arr.length / 2);

const left = arr.slice(0, middle);

const right = arr.slice(middle);

return merge(mergeSort(left), mergeSort(right));

}

function merge(left, right) {

let result = [];

let leftIndex = 0;

let rightIndex = 0;

while (leftIndex < left.length && rightIndex < right.length) {

if (left[leftIndex] <= right[rightIndex]) {

result.push(left[leftIndex]);

leftIndex++;

} else {

result.push(right[rightIndex]);

rightIndex++;

}

}

return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));

}

### 5. Quick Sort:

• Stability: Not stable

• Description: Selects a pivot, partitions the array into elements smaller and larger than the pivot, and recursively sorts the partitions.

function quickSort(arr) {

if (arr.length <= 1) {

return arr;

}

const pivot = arr[0];

const left = [];

const right = [];

for (let i = 1; i < arr.length; i++) {

arr[i] < pivot ? left.push(arr[i]) : right.push(arr[i]);

}

return quickSort(left).concat(pivot, quickSort(right));

}

Remember, these examples provide a basic understanding, and there are often more optimized or efficient implementations available. Choose the sorting algorithm based on the specific requirements of your task.