This is the 22nd day of my participation in Gwen Challenge.

What is sort

Sorting is the sorting of the input numbers in order from smallest to largest.

All sorts of sorting algorithms

As sorting is a relatively basic problem, so the sorting algorithm is more kinds.

Bubble sort

Bubble sort is an algorithm that repeats the operation of comparing the size of two adjacent numbers starting from the right side of the sequence and then switching the positions of the two numbers based on the result. In this process, the numbers slowly “bubble” from right to left to the top of the sequence, hence the name “bubbling sort”.

Time consuming

In bubble sort, round 1 needs to compare N -1 times, round 2 needs to compare N -2 times… Round N -1 requires one comparison. Therefore, the total number of comparisons is (n-1) + (n-2) +… Material n2/2 + 1. The number of comparisons is constant and has nothing to do with the order of input data.

The time complexity of bubble sort is O (n2).

implementation

function bubbleSort(list) {
  for (let i = 0; i < list.length - 1; i++) {
    // Array length n, loop n-1 times
    for (let j = list.length - 1; j - 1 - i > 0; j--) {
      // Compare and switch pairs from right to left
      if (list[j - 1] > list[j]) {
        [list[j - 1], list[j]] = [list[j], list[j - 1]]. }}}}console.log(bubbleSort([1.2.5.9.3.4.6.8.7])) // [1, 2, 3, 4, 5, 6, 7, 8, 9]
Copy the code

The trick is to swap values using array deconstruction, which is faster than using temporary variables.

Selection sort

Selection sort is an algorithm that repeats the operation of “finding the minimum value from the data to be sorted and exchanging it with the leftmost number in the sequence”. Linear lookup is used to find the minimum value in the sequence.

Time consuming

Selection sort uses linear lookup to find the minimum, so n-1 numbers need to be compared in round 1, and n-2 numbers need to be compared in round 2… By round N-1 you only have to compare one number. Therefore, the total number of comparisons is the same as bubble sort, both are (n-1) + (n-2) +… + 1 material n2/2 times.

The time complexity of selection sort is O (n2), which is the same as that of bubble sort.

implementation

// Select sort
function selectSort(list) {
  // The array length is n, and only n-1 nodes need to be processed
  for (let i = 0; i < list.length - 1; i++) {
    let minIndex = getMinIndex(list.slice(i), i);
    [list[i], list[minIndex]] = [list[minIndex], list[i]];
  }
  console.log(list);
}

// Get the index of the smallest value in the unprocessed data on the right
function getMinIndex(list, skip) {
  let min = list[0],
    minIndex = 0;
  for (let i = 1, len = list.length; i < len; i++) {
    if(list[i] < min) { min = list[i]; minIndex = i; }}return minIndex + skip;
}
selectSort([1.2.5.9.3.4.6.8.7]);

Copy the code

Insertion sort

Insertion sort is an algorithm that sorts data sequentially from the left end of a sequence. In the sorting process, the data on the left side is continuously resorted, while the data on the right side is left unsorted. The idea of insert sort is to take a piece of data from the unsorted region on the right and insert it into the appropriate position in the sorted region.

Time consuming

O of n2.

implementation

// Insert sort
function insertSort(list) {
  if (list.length < 2) return list;
  for (let i = 1; i < list.length; i++) {
    for (let j = i - 1; j > 0; j--) {
      if (list[j+1] < list[j]) {
        [list[j+1], list[j]] = [list[j], list[j+1]]}}}console.log(list);
}

insertSort([1.2.5.9.3.4.6.8.7]);
Copy the code

Heap sort

Heap sort is characterized by the use of heaps in data structures.

Time consuming

Heap sort starts by putting n items into the heap in order nlogn time. During sorting, the heap starts as an empty heap and gradually fills up with data. Since the heap height is less than log2n, the time required to insert 1 data is O (logn).

The overall heap sort time is O (nlogn).

Merge sort

Merge sort splits the sequence into two subsequences of the same length, and merges the subsequences when no further down (that is, when there is only one data in each subsequence) is possible. Merging refers to merging two ordered subsequences into one ordered sequence. This operation is repeated until all subsequences are merged into one whole.

Time consuming

Order nlogn.

Quick sort

The quicksort algorithm first randomly selects a reference value (pivot) in the sequence, then divides the numbers other than the reference value into “less than the reference value” and “more than the reference value” categories, and arranges them in the following form.

knowledge

Quicksort is divide-and-conquer. It divides the original problem into two subproblems (numbers smaller than the base value and numbers larger than the base value) and then solves the two problems separately. Subproblems, that is, when the subsequences are sorted, and then, as I said at the beginning, they are combined into one sequence, then the sorting of the original sequence is done. However, quicksort is used again to solve subproblems, and even within this quicksort. Sorting is only done if there is only one number left in the subproblem. Like this, the continued use of the algorithm within the algorithm is called “recursion.”

Time consuming

Order nlogn.