# Sorting Algorithms

## Overview Table​

AlgorithmEfficiencyImportanceCategoryStrategy
Quick Sort★★★★☆★★★★★Comparison SortDivide and Conquer
Merge Sort★★★★☆★★★★★Comparison SortDivide and Conquer
Heap Sort★★★★☆★★★★☆Comparison SortHeap Data Structure
Bubble Sort★☆☆☆☆★☆☆☆☆Comparison SortExchanging
Insertion Sort★★☆☆☆★★★☆☆Comparison SortInsertion
Selection Sort★☆☆☆☆★★☆☆☆Comparison SortSelection
Bucket Sort★★★☆☆★★★☆☆Non-Comparison SortDistribution
Counting Sort★★★☆☆★★★☆☆Non-Comparison SortCounting

## Quick Sort​

Explanation: Quick Sort is a highly efficient sorting algorithm and is based on the divide-and-conquer approach. It 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 sorted recursively.

Time Complexity:

• Average case: O(n log n)
• Worst case: O(n^2) (rare)

Visualizations:

History: Quick Sort was developed by British computer scientist Tony Hoare in 1959 and has since become one of the most widely used sorting algorithms due to its efficiency and simplicity.

Code Sample:

``function quickSort(arr) {  if (arr.length <= 1) {    return arr;  }  const pivot = arr[Math.floor(arr.length / 2)];  const left = arr.filter((x) => x < pivot);  const middle = arr.filter((x) => x === pivot);  const right = arr.filter((x) => x > pivot);  return [...quickSort(left), ...middle, ...quickSort(right)];}// Example usageconst arr = [3, 6, 8, 10, 1, 2, 1];console.log(quickSort(arr));``

## Merge Sort​

Explanation: Merge Sort is a stable, comparison-based sorting algorithm that divides the unsorted list into n sublists, each containing one element, and then repeatedly merges sublists to produce new sorted sublists until there is only one sublist remaining.

Time Complexity:

• Best case: O(n log n)
• Worst case: O(n log n)

Visualizations:

History: Merge Sort was invented by John von Neumann in 1945. It is known for its efficiency and is often used in situations where stability is important.

Code Sample:

``function mergeSort(arr) {  if (arr.length <= 1) {    return arr;  }  const mid = Math.floor(arr.length / 2);  const left = mergeSort(arr.slice(0, mid));  const right = mergeSort(arr.slice(mid));  return merge(left, right);}function merge(left, right) {  const result = [];  let i = 0,    j = 0;  while (i < left.length && j < right.length) {    if (left[i] < right[j]) {      result.push(left[i]);      i++;    } else {      result.push(right[j]);      j++;    }  }  return result.concat(left.slice(i)).concat(right.slice(j));}// Example usageconst arr = [3, 6, 8, 10, 1, 2, 1];console.log(mergeSort(arr));``

## Heap Sort​

Explanation: Heap Sort is a comparison-based sorting algorithm that uses a binary heap data structure. It first builds a max-heap from the input data and then repeatedly extracts the maximum element from the heap and rebuilds the heap until all elements are sorted.

Relies on the Heap Data Structure for sorting.

Time Complexity:

• Best case: O(n log n)
• Worst case: O(n log n)

Visualizations:

History: Heap Sort was introduced by J.W.J. Williams in 1964 as a method for sorting using the heap data structure. It is known for its good performance in the worst-case scenario.

Code Sample:

``function heapify(arr, n, i) {  let largest = i;  const left = 2 * i + 1;  const right = 2 * i + 2;  if (left < n && arr[left] > arr[largest]) {    largest = left;  }  if (right < n && arr[right] > arr[largest]) {    largest = right;  }  if (largest !== i) {    [arr[i], arr[largest]] = [arr[largest], arr[i]];    heapify(arr, n, largest);  }}function heapSort(arr) {  const n = arr.length;  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {    heapify(arr, n, i);  }  for (let i = n - 1; i > 0; i--) {    [arr[0], arr[i]] = [arr[i], arr[0]];    heapify(arr, i, 0);  }}// Example usageconst arr = [3, 6, 8, 10, 1, 2, 1];heapSort(arr);``

## Bubble Sort​

Explanation: Bubble Sort is a simple comparison-based algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted.

Time Complexity:

• Best case: O(n)
• Worst case: O(n^2)

Visualizations:

History: Bubble Sort is one of the simplest sorting algorithms and has been used since the early days of computer science. However, due to its inefficiency, it is rarely used in practice.

Code Sample:

``function bubbleSort(arr) {  const n = arr.length;  for (let i = 0; i < n; 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]];      }    }  }}// Example usageconst arr = [3, 6, 8, 10, 1, 2, 1];bubbleSort(arr);``

## Insertion Sort​

Explanation: Insertion Sort is a simple sorting algorithm that builds the final sorted array one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort.

Time Complexity:

• Best case: O(n)
• Worst case: O(n^2)

History: Insertion Sort has been known since at least the mid-20th century. It is useful for small data sets or as part of more complex algorithms.

Code Sample:

``function insertionSort(arr) {  for (let i = 1; i < arr.length; i++) {    const key = arr[i];    let j = i - 1;    while (j >= 0 && arr[j] > key) {      arr[j + 1] = arr[j];      j--;    }    arr[j + 1] = key;  }}// Example usageconst arr = [3, 6, 8, 10, 1, 2, 1];insertionSort(arr);``

## Selection Sort​

Explanation: Selection Sort is an in-place comparison-based algorithm. It has O(n^2) time complexity, making it inefficient on large lists, and generally performs worse than the similar insertion sort.

Time Complexity:

• Best case: O(n^2)
• Worst case: O(n^2)

History: Selection Sort is one of the oldest sorting algorithms and has been used since the early days of computing. It is mainly of academic interest today.

Code Sample:

``function selectionSort(arr) {  for (let i = 0; i < arr.length; i++) {    let minIdx = i;    for (let j = i + 1; j < arr.length; j++) {      if (arr[j] < arr[minIdx]) {        minIdx = j;      }    }    [arr[i], arr[minIdx]] = [arr[minIdx], arr[i]];  }}// Example usageconst arr = [3, 6, 8, 10, 1, 2, 1];selectionSort(arr);console.log(arr);``

Explanation: Radix Sort is a non-comparative sorting algorithm. It sorts numbers by processing individual digits. It is efficient for sorting large lists of integers or strings.

Time Complexity:

• Best case: O(nk)
• Worst case: O(nk), where k is the number of digits

Visualizations:

History: Radix Sort was introduced by Herman Hollerith in 1887. It is particularly useful for sorting data with a large range of values.

Code Sample:

``function countingSort(arr, exp) {  const n = arr.length;  const output = new Array(n).fill(0);  const count = new Array(10).fill(0);  for (let i = 0; i < n; i++) {    const index = Math.floor(arr[i] / exp) % 10;    count[index]++;  }  for (let i = 1; i < 10; i++) {    count[i] += count[i - 1];  }  for (let i = n - 1; i >= 0; i--) {    const index = Math.floor(arr[i] / exp) % 10;    output[count[index] - 1] = arr[i];    count[index]--;  }  for (let i = 0; i < n; i++) {    arr[i] = output[i];  }}function radixSort(arr) {  const max = Math.max(...arr);  for (let exp = 1; Math.floor(max / exp) > 0; exp *= 10) {    countingSort(arr, exp);  }}``

## Bucket Sort (Bin Sort)​

Explanation: Bucket Sort works by distributing elements into several buckets, then sorting each bucket individually using another sorting algorithm or recursively applying the bucket sort. It is a cousin of radix sort.

Time Complexity:

• Best case: O(n + k)
• Worst case: O(n^2) (depends on the sorting algorithm used inside the buckets and the distribution of the input)

History: Bucket Sort is often attributed to Harold H. Seward in 1954 and is used for sorting numbers uniformly distributed over a range.

Code Sample:

``function bucketSort(arr, bucketSize = 5) {  if (arr.length === 0) {    return arr;  }  let i,    minValue = arr[0],    maxValue = arr[0];  // Determine minimum and maximum values  arr.forEach((currentVal) => {    if (currentVal < minValue) {      minValue = currentVal;    } else if (currentVal > maxValue) {      maxValue = currentVal;    }  });  // Initialize buckets  const bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;  const buckets = new Array(bucketCount);  for (i = 0; i < buckets.length; i++) {    buckets[i] = [];  }  // Distribute input array values into buckets  arr.forEach((currentVal) => {    buckets[Math.floor((currentVal - minValue) / bucketSize)].push(currentVal);  });  // Sort each bucket and concatenate the results  arr.length = 0;  buckets.forEach((bucket) => {    insertionSort(bucket);    bucket.forEach((element) => {      arr.push(element);    });  });  return arr;}// Helper function: Insertion Sortfunction insertionSort(arr) {  for (let i = 1; i < arr.length; i++) {    const key = arr[i];    let j = i - 1;    while (j >= 0 && arr[j] > key) {      arr[j + 1] = arr[j];      j--;    }    arr[j + 1] = key;  }}// Example usageconst arr = [3.2, 0.4, 2.7, 1.6, 0.9, 2.3, 3.0];console.log(bucketSort(arr));``

## Counting Sort​

Explanation: Counting Sort is a non-comparative sorting algorithm that sorts elements by counting the number of occurrences of each unique element in the input array. The count is stored in an auxiliary array and then used to place the elements in the correct position in the output array. It is efficient for sorting integers with a known, limited range.

Time Complexity:

• Best case: O(n + k)
• Worst case: O(n + k) (where n is the number of elements and k is the range of the input)

History: Counting Sort was introduced by Harold H. Seward in 1954. It is mainly used for sorting integers and is particularly effective for small ranges.

Code Sample:

``function countingSort(arr) {  const max = Math.max(...arr);  const min = Math.min(...arr);  const range = max - min + 1;  const count = new Array(range).fill(0);  const output = new Array(arr.length);  // Count occurrences of each element  arr.forEach((num) => {    count[num - min]++;  });  // Compute cumulative count  for (let i = 1; i < count.length; i++) {    count[i] += count[i - 1];  }  // Place the elements in sorted order  for (let i = arr.length - 1; i >= 0; i--) {    output[count[arr[i] - min] - 1] = arr[i];    count[arr[i] - min]--;  }  // Copy the sorted elements back to the original array  for (let i = 0; i < arr.length; i++) {    arr[i] = output[i];  }  return arr;}// Example usageconst arr = [4, 2, 2, 8, 3, 3, 1];console.log(countingSort(arr));``

# Automated Amazon Reports

Automatically download Amazon Seller and Advertising reports to a private database. View beautiful, on demand, exportable performance reports.