Sorting algorithms
Tags: webdev, javascript, beginners, programming
Published: 2024-02-27 08:56:05

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.



  ```javascript

  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.



  ```javascript

  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.



  ```javascript

  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.



  ```javascript

  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.



  ```javascript

  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.