This directory contains implementations of various sorting algorithms in TypeScript. Each algorithm resides in its own subdirectory with a dedicated README file explaining its logic, complexity, and use cases.

Here's a list of the currently implemented sorting algorithms:

* Bubble Sort - A simple sorting technique good for educational purposes but inefficient for large datasets.

* Insertion Sort - Sorts by inserting elements into their correct positions within a sorted sub-array. Efficient for small to medium-sized datasets.

* (Add entries for other implemented algorithms here)

Each subdirectory contains the following:

* **index.ts:** The main implementation file for the specific sorting algorithm.

* **README.md:** A detailed explanation of the algorithm's logic, complexity, and use cases.

This project aims to provide a clear and comprehensive understanding of various sorting algorithms in TypeScript. Feel free to explore the code and implement additional sorting techniques to expand the collection!

Bubble Sort works by repeatedly stepping through the list to be sorted.

In each pass, it compares adjacent elements and swaps them if they are in the wrong order.

The larger element "bubbles" up towards the end of the list with each pass.

Here's a detailed breakdown:

1. **Initialization:**

- Set a variable `swapped` to `false` (indicates if a swap occurred during the pass).

- Iterate through the list using a loop for `n-1` times (since the last element is already in its final position after n-1 passes).

2. **Inner Loop:**

- In each iteration of the inner loop, compare the current element (at index `i`) with the next element (at index `i+1`).

- If the current element is greater than the next element, swap their positions and set `swapped` to `true`.

3. **Swapping:**

- To swap elements, use a temporary variable to hold the current element.

- Assign the next element's value to the current element's position.

- Assign the temporary variable (holding the original current element's value) to the next element's position.

4. **Continue Until No Swaps:**

- After the inner loop completes, check the value of `swapped`.

- If `swapped` is `false`, it means no swaps occurred during the pass, indicating the list is sorted. Terminate the outer loop.

- If `swapped` is `true`, repeat the outer loop for another pass, as elements might still be out of order.

Bubble Sort has a time complexity of O(n^2) in the worst and average cases. This means the number of comparisons (and potentially swaps) grows quadratically with the size of the input list (n). For larger datasets, this can be quite inefficient.

Bubble Sort has a space complexity of O(1). It only uses a constant amount of additional space (e.g., temporary variables for swapping) regardless of the input list size.

* **Simple to understand and implement:** Due to its straightforward logic, Bubble Sort is a great starting point for learning sorting algorithms.

* **Easy to visualize:** The concept of elements bubbling up is easy to grasp and can be visualized for better understanding.

* **Inefficient for large datasets:** The O(n^2) time complexity makes Bubble Sort impractical for sorting massive amounts of data.

* Bubble Sort is primarily used for educational purposes due to its simplicity.

* It might be suitable for sorting very small datasets where efficiency is not a critical concern.

Bubble Sort provides a valuable introduction to sorting algorithms. While not the most efficient option for real-world applications, understanding its logic is beneficial for grasping more complex sorting techniques.

export const bubbleSort = (arr: number[]): number[] => {

// Flag to track if any swaps occurred in the inner loop

let swapped = true;

// Loop through each element of the array (outer loop)

for (let outer = arr.length - 1; outer >= 0 && swapped; outer--) {

swapped = false; // Reset flag before inner loop

// Loop through the unsorted part of the array (inner loop)

for (let inner = 0; inner < outer; inner++) {

// Compare adjacent elements and swap if they are in the wrong order

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

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

swapped = true; // Set flag if a swap occurred

}

}

}

// Return the sorted array

return arr;

Insertion Sort works by dividing the input list into two parts: a sorted sub-array on the left and an unsorted sub-array on the right. In each pass, it takes an element from the unsorted sub-array and inserts it into its correct position within the sorted sub-array.

Here's a step-by-step explanation:

1. **Initialization:**

- Consider the first element of the list to be the sorted sub-array (size 1).

- Iterate through the list starting from the second element (index 1) onwards.

2. **Pick Unsorted Element:**

- In each iteration, select the current element from the unsorted sub-array.

3. **Shift Sorted Elements:**

- Iterate backwards through the sorted sub-array (starting from the element before the current position).

- If the current element is less than the element at the current position in the sorted sub-array, shift the larger element one position to the right.

4. **Insert Element:**

- Once a position in the sorted sub-array is greater than or equal to the current element, insert the current element at that position.

5. **Repeat Until Sorted:**

- Continue iterating through the unsorted sub-array, picking elements and inserting them into their correct positions within the sorted sub-array.

- By the end of the loop, the entire list becomes sorted.

The time complexity of Insertion Sort depends on the initial state of the data:

* **Best Case:** O(n) - If the data is already sorted, Insertion Sort only needs to iterate through the list once, resulting in linear time complexity.

* **Average Case:** O(n^2) - For random or partially sorted data, Insertion Sort performs multiple shifts and comparisons, leading to quadratic time complexity.

* **Worst Case:** O(n^2) - If the data is in reverse order, Insertion needs to make numerous shifts for each element, resulting in the same quadratic complexity as the average case.

Insertion Sort has a space complexity of O(1). It only uses a constant amount of additional space (e.g., temporary variables) regardless of the input list size.

* **Simple to understand and implement:** Similar to Bubble Sort, Insertion Sort's logic is easy to grasp, making it a good choice for beginners.

* **Efficient for small to medium datasets:** In such cases, Insertion Sort's performance is comparable to more complex algorithms.

* **Stable sorting:** Insertion Sort preserves the original order of elements with equal values.

* **Inefficient for large datasets:** The O(n^2) time complexity in the worst and average cases makes Insertion Sort less suitable for sorting massive amounts of data.

* Insertion Sort is a good choice for sorting small to medium-sized datasets where simplicity and stability are important.

* It can be useful in situations where frequent insertions into a partially sorted list occur.

Insertion Sort offers a good balance between simplicity and efficiency for specific use cases. While not ideal for very large datasets, it provides a solid foundation for understanding sorting algorithms.

export const insertionSort = (arr: number[]): number[] => {

// Loop through each element of the array (except the first element)

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

const current = arr[i];

let j = i - 1;

// Shift elements of the sorted sub-array to make space for the current element

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

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

j--;

}

// Insert the current element at its correct position

arr[j + 1] = current;

}

// Return the sorted array

return arr;

import { bench } from "vitest";

import { bubbleSort } from "../bubble";

import { insertionSort } from "../insertion";

import { TEST_DATA } from "./test-data";

describe("Sorting Algorithms", () => {

bench("Bubble Sort", () => {

for (const { input } of TEST_DATA) {

bubbleSort(input);

}

});

bench("Insertion Sort", () => {

for (const { input } of TEST_DATA) {

insertionSort(input);

}

});

import { bubbleSort } from "../bubble";

import { insertionSort } from "../insertion";

import { TEST_DATA } from "./test-data";

describe("Sorting Algorithms", () => {

describe("Bubble Sort", () => {

it.each(TEST_DATA)("should sort the array correctly", ({ input, expected }) => {

// Validate the test data

expect(input).toBeDefined();

expect(expected).toBeDefined();

// Run the function

const result = bubbleSort(input);

// Validate the result

expect(result).toBeDefined();

expect(result).toEqual(expected);

});

});

describe("Insertion Sort", () => {

it.each(TEST_DATA)("should sort the array correctly", ({ input, expected }) => {

// Validate the test data

expect(input).toBeDefined();

expect(expected).toBeDefined();

// Run the function

const result = insertionSort(input);

// Validate the result

expect(result).toBeDefined();

expect(result).toEqual(expected);

});

});

import type { InputTestData } from "@typings/input-data";

export const TEST_DATA: InputTestData<number[], number[]>[] = [

// Test cases with different array sizes

{ input: [1], expected: [1] },

{ input: [2, 1], expected: [1, 2] },

{ input: [4, 3, 2, 1, 0], expected: [0, 1, 2, 3, 4] },

{ input: [10, 5, 15, 2, 8], expected: [2, 5, 8, 10, 15] },

{ input: [100, 50, 200, 1, 75], expected: [1, 50, 75, 100, 200] },

// Test cases with duplicate elements

{ input: [3, 1, 2, 3, 1], expected: [1, 1, 2, 3, 3] },

{ input: [5, 5, 5], expected: [5, 5, 5] },

// Test cases with negative numbers

{ input: [-2, 5, 0, -1], expected: [-2, -1, 0, 5] },

{ input: [-5, -1, -3, -4], expected: [-5, -4, -3, -1] },

// Test cases with empty array

{ input: [], expected: [] },

import { bench } from "vitest";