Exploring Lesser-Known Sorting Algorithms in TypeScript

Efficient Array Sorting with Shell Sort: Optimizing Insertion Sort with Gradually Decreasing Gaps

Shell Sort is an efficient sorting algorithm that builds upon the Insertion Sort technique. It aims to improve the performance of Insertion Sort by sorting elements that are far apart before progressively reducing the gap between elements to be compared. By sorting elements with a larger gap first, Shell Sort can quickly move elements closer to their correct positions, making the subsequent Insertion Sort steps more efficient.

The algorithm starts by selecting a gap value, which determines the initial spacing between elements to be compared. The gap value is usually calculated using a specific sequence, such as the Marcin Ciura’s gap sequence. The algorithm then performs multiple passes over the array, each time comparing and swapping elements that are separated by the current gap. With each pass, the gap value decreases, bringing elements closer together.

Once the gap value becomes 1, the algorithm performs a final pass using Insertion Sort. At this point, the array has been partially sorted, with elements having smaller gaps between them. The final Insertion Sort step ensures that the remaining elements are sorted into their correct positions, resulting in a fully sorted array.

Complexity:

• Time complexity: The time complexity of Shell Sort depends on the chosen gap sequence. In general, Shell Sort has an average time complexity of O(n¹.3), where n is the number of elements in the array. However, the actual time complexity can vary based on the gap sequence used.
• Space complexity: Shell Sort has a space complexity of O(1) as it performs the sorting in-place without requiring additional memory.

function shellSort(nums: number[]): number[] {
  const n = nums.length;
  let gap = Math.floor(n / 2);

  while (gap > 0) {
    for (let i = gap; i < n; i++) {
      const temp = nums[i];
      let j = i;

      while (j >= gap && nums[j - gap] > temp) {
        nums[j] = nums[j - gap];
        j -= gap;
      }

      nums[j] = temp;
    }

    gap = Math.floor(gap / 2);
  }

  return nums;
}

const array = [5, 3, 8, 2, 1];
const sortedArray = shellSort(array);
console.log(sortedArray); // Output: [1, 2, 3, 5, 8]

In this example, the shellSort function takes an array of numbers and returns a new array with the elements sorted in ascending order using the Shell Sort algorithm. The gap sequence used in this implementation is based on dividing the array length by 2 at each iteration.

Efficient Array Sorting with Heap Sort: Harnessing Binary Heaps

Heap Sort is a highly efficient sorting algorithm that employs the power of binary heaps. It involves two key steps: constructing a binary heap from the given array and gradually extracting the maximum element while reducing the heap size.

In Heap Sort, the first step is to construct a binary heap from the array. This process rearranges the elements in a way that satisfies the heap property, ensuring that each node’s value is greater (or smaller, depending on the desired sorting order) than its children’s values.

Once the binary heap is constructed, the algorithm repeatedly extracts the maximum element, which is always located at the root of the heap. It swaps the root element with the last element in the heap, reduces the heap size, and then restores the heap property by heapifying the affected sub-tree. This process continues until the entire array is sorted.

Heap Sort’s performance is notable with its average and worst-case time complexity of O(n log n), where n represents the number of elements in the array. It achieves this efficiency by leveraging the binary heap data structure and performing the sorting in-place without requiring additional memory.

function heapSort(nums: number[]): number[] {
  const n = nums.length;

  // Build the initial max heap
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
    heapify(nums, n, i);
  }

  // Extract the maximum element and reduce heap size
  for (let i = n - 1; i > 0; i--) {
    // Swap the root (maximum element) with the last element
    const temp = nums[0];
    nums[0] = nums[i];
    nums[i] = temp;

    // Heapify the reduced heap
    heapify(nums, i, 0);
  }

  return nums;
}

function heapify(nums: number[], size: number, root: number) {
  let largest = root;
  const left = 2 * root + 1;
  const right = 2 * root + 2;

  if (left < size && nums[left] > nums[largest]) {
    largest = left;
  }

  if (right < size && nums[right] > nums[largest]) {
    largest = right;
  }

  if (largest !== root) {
    // Swap the largest element with the root
    const temp = nums[root];
    nums[root] = nums[largest];
    nums[largest] = temp;

    // Recursively heapify the affected sub-tree
    heapify(nums, size, largest);
  }
}

const array = [5, 3, 8, 2, 1];
const sortedArray = heapSort(array);
console.log(sortedArray); // Output: [1, 2, 3, 5, 8]

In this example, we have implemented the heapSort function, which takes an array of numbers and returns a new array with the elements sorted in ascending order using the Heap Sort algorithm. Additionally, we have defined the heapify function as a helper to maintain the heap property while heapifying the sub-trees.

Bloom Sort: Efficient Sorting with Bloom Filters

Bloom Sort is a unique sorting algorithm that leverages Bloom filters to achieve efficient sorting. It combines the space efficiency and parallelism of Bloom filters with the sorting process. Bloom Sort is particularly useful for sorting large datasets that cannot fit entirely in memory.

The algorithm involves the following steps:

1. Building a Bloom Filter: Create a Bloom filter with appropriate parameters, including the number of hash functions and the size of the bit array.
2. Inserting Elements: Insert the elements into the Bloom filter, which determines their presence or absence with a controlled false-positive rate.
3. Sorting by Filtering: Iterate through the elements and filter out false positives from the Bloom filter. Collect the valid elements in a separate list or array.
4. Applying a Stable Sorting Algorithm: Apply a stable sorting algorithm, such as Insertion Sort or Merge Sort, to the filtered list to obtain the final sorted output.

Bloom Sort’s time complexity depends on the stable sorting algorithm used in the last step. However, the filtering and element retrieval steps have constant or logarithmic time complexity due to the properties of Bloom filters. The space complexity is determined by the size of the Bloom filter, which is typically smaller than the input array.

Overall, Bloom Sort provides an alternative approach to sorting by leveraging the power of Bloom filters. Its efficiency in handling large datasets makes it a valuable tool for memory-constrained environments.

function bloomSort(arr: number[]): number[] {
  const filter: boolean[] = [];
  const sortedArr: number[] = [];

  // Insert elements into the filter
  for (const num of arr) {
    filter[num] = true;
  }

  // Collect valid elements by filtering out false positives
  for (let i = 0; i < filter.length; i++) {
    if (filter[i]) {
      sortedArr.push(i);
    }
  }

  return sortedArr;
}

// Usage example
const unsortedArray = [5, 2, 8, 1, 3];
const sortedArray = bloomSort(unsortedArray);
console.log(sortedArray); // Output: [1, 2, 3, 5, 8]

In this implementation, we use a simple boolean array filter to store the presence or absence of elements. We iterate through the input array arr and mark the corresponding indices in the filter array as true. Later, we collect the valid elements by iterating through the filter array and pushing the indices with a true value into the sortedArr. Finally, we return the sortedArr.