Interviewer asks: Can you get in a triple row?

I:

.

About time complexity:

  1. Square order (O(n**2)) sort all kinds of simple sort: direct insertion, direct selection and bubble sort.
  2. Linear logarithmic order (O(nlog2n)) sort: quicksort, heap sort and merge sort;
  3. O(n1+§)), § is a constant between 0 and 1. Hill sorting
  4. Linear order (O(n)) sort radix sort, in addition to bucket, box sort.

In situ sorting: refers to the sorting algorithm whose space complexity is O(1).

Stability: If there are elements of the same value in the sorted sequence, the order of the elements will not change after sorting.

Bubble sort

Bubble Sort (English: Bubble Sort), also known as Bubble Sort, is a simple sorting algorithm. It repeatedly walks through the sequence to be sorted, comparing two elements at a time and swapping them if they are in the wrong order. The task of visiting an array is repeated until no more exchanges are needed, that is, the array has been sorted. The algorithm gets its name because smaller elements slowly “float” to the top of the list through swapping.

Bubble sort requires O(n**2) comparisons for n items and can be sorted in place. Although this algorithm is one of the easiest to understand and implement for sorting, it is very inefficient for sorting a sequence containing a large number of elements.

Bubble sort has the same running time as insert sort, but the two algorithms are very different in the number of swaps required. In the worst case, bubble sort requires O(n**2) swaps, whereas insertion sort requires at most O(n) swaps. Implementations of bubble sort (like the one below) typically run poorly (O(n ** 2) on already sorted columns, whereas insertion sort in this case requires only O(n) operations. So many modern algorithm textbooks avoid bubble sort and use insertion sort instead. Bubble sort can also reduce the complexity to O(n) in the optimal case if a flag is used to indicate the possibility of swapping when the inner loop is first run. In this case, there is no need to swap the sorted sequence. If you reverse the order of visits each time you visit the array, you can also improve efficiency slightly. Sometimes it’s called cocktail sort because the algorithm goes back and forth from one end of the array to the other.

The bubbling sort algorithm works as follows:

  1. Compare adjacent elements. If the first one is bigger than the second, swap them both.
  2. Do the same for each pair of adjacent elements, starting from the first pair to the last pair at the end. When we do that, the last element is going to be the largest number.
  3. Repeat this step for all elements except the last one.
  4. Keep repeating the above steps for fewer and fewer elements at a time until there are no more pairs to compare.
  • Bubble sort
  • Bubble sort TS implementation
  • Cocktail ordering
  • Cocktail sort TS implementation
export function bubbleSort(arr: number[]) {
  const length = arr.length
  if (length <= 1) return arr
  for (let i = 0; i < length; i++) {
    let changed: boolean = false // There is no data exchange
    for (let j = 0; j < length - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        swap(arr, j, j + 1)
        changed = true}}if(! changed)break
  }
  return arr
}
Copy the code

Cocktail ordering

export function cocktailSort(arr: number[]) {
  const len = arr.length
  for (let i = 0; i < len / 2; i++) {
    let start: number = 0
    let end: number = len - 1
    for (let j = start; j < end; j++) {
      if (arr[j] > arr[j + 1]) swap(arr, j, j + 1)
    }
    end--
    for (let j = end; j > start; j--) {
      if (arr[j] < arr[j - 1]) swap(arr, j - 1, j)
    }
    start++
  }
  return arr
}
Copy the code

Bubble sort

Cocktail ordering

Selection sort

Selection sort is a simple and intuitive sorting algorithm. Here’s how it works. First, find the smallest (large) element in the unsorted sequence and store it at the beginning of the sorted sequence. Then, continue to find the smallest (large) element from the remaining unsorted elements and place it at the end of the sorted sequence. And so on until all the elements are sorted.

The main advantage of selection sort has to do with data movement. If an element is in the correct final position, it will not be moved. Each time a pair of elements is swapped, at least one of them will be moved to its final position, so sorting a list of N elements does at most n-1 swaps. Of all the sorting methods that rely entirely on swapping to move elements, selective sorting is the best one.

  • Selection sort
  • Select sort TS implementation
export function selectionSort(arr: number[]) {
  const length = arr.length
  if (length <= 1) return arr
  for (let i = 0; i < length; i++) {
    let min = i
    for (let j = i + 1; j < length; j++) {
      if (arr[j] < arr[min]) {
        min = j
      }
    }
    swap(arr, i, min)
  }
  return arr
}
Copy the code

Insertion sort

Insertion Sort is a simple and intuitive sorting algorithm. It works by building an ordered sequence, scanning back to front in the sorted sequence for unsorted data, finding the appropriate location and inserting it. In the implementation of insertion sort, in-place sort is usually adopted (that is, the sort only needs to use O(1) extra space). Therefore, in the process of scanning from back to front, the sorted elements need to be moved backward step by step repeatedly to provide insertion space for the latest elements.

The Insertion Sort is the same as picking up cards one by one from a poker table and sorting them in hand.

In general, insert sorts are implemented on arrays using in-place. The specific algorithm is described as follows:

  1. Start with the first element, which can be considered sorted
  2. Takes the next element and scans back to front in the sorted element sequence
  3. If the element (sorted) is larger than the new element, move the element to the next position
  4. Repeat step 3 until you find a place where the sorted element is less than or equal to the new element
  5. After inserting the new element into the location
  6. Repeat steps 2 to 5
export function insertionSort(arr: number[]) {
  const length = arr.length
  if (length <= 1) return arr
  for (let i = 1; i < length; i++) {
    const cur = arr[i]
    let j = i - 1
    for (; j >= 0; j--) {
      if (arr[j] > cur) {
        arr[j + 1] = arr[j]
      } else {
        break
      }
    }
    arr[j + 1] = cur
  }

  return arr
}
Copy the code

or

export function insertionSort2(arr: number[]) {
  const len = arr.length
  for (let i = 1; i < len; i++) {
    for (let j = i - 1; j >= 0; j--) {
      if (arr[j] > arr[j + 1]) {
        // It is less efficient to change two elements
        swap(arr, j + 1, j)
      } else {
        break}}}return arr
}
Copy the code
  • Insertion sort
  • Insert sort TS implementation

Quick sort

Quicksort, also known as partition-exchange sort, is a sort algorithm first proposed by Tony Hall. On average, sorting n items takes O(nlogn) (big O symbol) comparisons. In the worst case, O(n**2) comparisons are required, but this is uncommon. In fact, quicksort O(NlogN) is usually significantly faster than other algorithms because its inner loop can be achieved efficiently on most architectures.

Quicksort uses a Divide and conquer strategy to Divide a list into two subsequences, smaller and larger, and then sort the two recursively.

Steps as follows:

  1. Pick a base: Pick an element from a sequence, called pivot,
  2. Split: Reorder the sequence so that all elements smaller than the base value are placed in front of the base value and all elements larger than the base value are placed behind the base value (numbers equal to the base value can go to either side). At the end of the split, the sorting of the base values is done,
  3. Recursive sort subsequence: Recursively sorts subsequences of elements less than a reference value and subsequences of elements greater than a reference value.

Recursion to the bottom of the judgment condition is the size of the sequence is zero or one, at which point the sequence is clearly ordered.

There are several specific methods to select the reference value, which has a decisive influence on the time performance of sorting.

  • Quick sort
  • Quick sort TS implementation

1 Common quick platoon

function partition(arr: number[], left: number, right: number) :number {
  let pivot: number = left // Start from the left by default, there is room for optimization
  let index = pivot + 1
  for (let i = index; i <= right; i++) {
    if (arr[i] < arr[pivot]) {
      swap(arr, i, index)
      index++
    }
  }
  swap(arr, pivot, index - 1)
  return index - 1
}

export function quickSort(arr: number[], l? :number, r? :number) {
  const len = arr.length
  const left: number = typeof l === 'number' ? l : 0
  const right: number = typeof r === 'number' ? r : len - 1
  let partitionIndex = 0
  if (left < right) {
    partitionIndex = partition(arr, left, right)
    quickSort(arr, left, partitionIndex - 1)
    quickSort(arr, partitionIndex + 1, right)
  }
  return arr
}
Copy the code

2 Fast row left and right Pointers

function partition(arr: number[], left: number, right: number) :number {
  let l: number = left // Start from the left by default, there is room for optimization
  let r: number = right
  const target: number = arr[left]

  while (l < r) {
    while (arr[r] >= target && r > l) {
      r--
    }
    while (arr[l] <= target && l < r) {
      l++
    }
    swap(arr, l, r)
  }

  if(l ! == left) { swap(arr, l, left) }return l
}

export function quickSort2(arr: at, l? :number, r? :number) {
  const len = arr.length
  const left: number = typeof l === 'number' ? l : 0
  const right: number = typeof r === 'number' ? r : len - 1
  let partitionIndex = 0
  if (left < right) {
    partitionIndex = partition(arr, left, right)
    quickSort2(arr, left, partitionIndex - 1)
    quickSort2(arr, partitionIndex + 1, right)
  }
  return arr
}
Copy the code

3 Three way fast platoon

function partion(arr: at, l: number, r: number) {
  // Select the first value of the interval
  let v = arr[l]
  let lt = l
  let gt = r + 1

  // The following loop is hard to understand
  // I and gt are both changing, gt moving to the left will not affect I, lt growth will shift the term equal to v to I, so I ++ is needed
  for (let i = l + 1; i < gt; ) {
    if (arr[i] === v) {
      // Lt and I are separated here
      i++
    } else if (arr[i] > v) {
      swap(arr, gt - 1, i)
      gt--
    } else {
      swap(arr, lt + 1, i)
      lt++
      i++
    }
  }

  swap(arr, l, lt) // arr[lt] === v
  lt--
  return { lt, gt }
}

export function quickSort3(arr: at, l? :number, r? :number) {
  const len = arr.length
  const left: number = typeof l === 'number' ? l : 0
  const right: number = typeof r === 'number' ? r : len - 1
  if (left >= right) return
  let { lt, gt } = partion(arr, left, right)
  quickSort3(arr, l, lt)
  quickSort3(arr, gt, r)
  return arr
}
Copy the code

Shell sort

Hill sort, also known as the descending incremental sort algorithm, is a more efficient and improved version of insertion sort. Hill sort is an unstable sort algorithm.

Hill sort is an improved method based on the following two properties of insertion sort:

  1. Insertion sort has high efficiency when it operates on almost ordered data, that is, it can achieve the efficiency of linear sort
  2. But insert sort is generally inefficient because it can only move data one bit at a time

Hill sort improves the performance of insert sort by dividing all the compared elements into several regions. This allows an element to make one big step towards its final position at a time. The algorithm then takes smaller and smaller steps for sorting. The last step of the algorithm is ordinary insert sort, but by this step, the data to be sorted is almost already sorted (insert sort is faster).

  • Hill sorting
  • Hill sort TS implementation
export function shellSort(arr: number[]) {
  const length: number = arr.length
  let i, j
  / / adjust the gap
  for (let gap = length >> 1; gap > 0; gap >>= 1) {
    // Insert rows according to the interval
    for (i = gap; i < length; i++) {
      let temp: number = arr[i]
      // Scan the range from the current position to the left
      for (j = i - gap; j >= 0 && arr[j] > temp; j -= gap) {
        arr[j + gap] = arr[j]
      }
      arr[j + gap] = temp
    }
  }
  return arr
}
Copy the code

or

export function shellSort2(arr: number[]) {
  const length: number = arr.length
  let i, j
  / / adjust the gap
  for (let gap = length >> 1; gap > 0; gap >>= 1) {
    // Insert rows according to the interval
    for (i = gap; i < length; i++) {
      // Scan the range from the current position to the left
      for (j = i - gap; j >= 0 && arr[j] > arr[j + gap]; j -= gap) {
        // It is less efficient to change two elements
        swap(arr, j, j + gap)
      }
    }
  }
  return arr
}
Copy the code

Merge sort

Merge sort (English: Merge sort, or mergesort) is an efficient sorting algorithm created on Merge operations with an efficiency of O(nlogn). It was first proposed in 1945 by John von Neumann. This algorithm is a very typical application of Divide and Conquer, and each level of divide-and-conquer recursion can be performed simultaneously.

Divide and conquer:

  1. Split: To recursively divide the current sequence into equal halves.
  2. Integration: The integration of subsequences from the previous step while preserving the order of the elements (merge).

Merge, also known as merge algorithm, refers to the operation of merging two already sorted sequences into a single sequence. Merge sort algorithms rely on merge operations.

Merge sort has two ways of thinking about it:

Recursion (top-down)

  1. Apply for a space that is the sum of two sorted sequences and is used to store the combined sequence
  2. Sets two Pointers, starting at the start of two sorted sequences
  3. Compare the elements to which the two Pointers point, place the smaller element into the merge space, and move the pointer to the next position
  4. Repeat step 3 until a pointer reaches the end of the sequence
  5. Copies all remaining elements of the other sequence directly to the end of the merged sequence
function merge(lArr: number[], rArr: number[]) {
  const result: number[] = []
  while (lArr.length && rArr.length) {
    if (lArr[0] < rArr[0]) {
      result.push(<number>lArr.shift())
    } else {
      result.push(<number>rArr.shift())
    }
  }
  while (lArr.length) {
    result.push(<number>lArr.shift())
  }
  while (rArr.length) {
    result.push(<number>rArr.shift())
  }
  return result
}

function merge2(lArr: number[], rArr: number[]) {
  const result: number[] = []
  let lLen = lArr.length
  let rLen = rArr.length
  let i = 0
  let j = 0
  while (i < lLen && j < rLen) {
    if (lArr[i] < rArr[j]) result.push(lArr[i++])
    else result.push(rArr[j++])
  }

  while (i < lLen) result.push(lArr[i++])
  while (j < rLen) result.push(rArr[j++])

  return result
}
Copy the code

Bottom-up iterative method

The principle is as follows (assuming a sequence of n elements) :

  1. Merge each two adjacent digits of the sequence to form CEIL (N /2) sequences, and each sequence contains two/one element after sorting
  2. If the number of sequences at this time is not one, the above sequences are merged again to form CEIL (N /4) sequences, and each sequence contains four/three elements
  3. Repeat step 2 until all elements are sorted, that is, the sequence number is 1
export function mergeSort2(arr: number[]) :number[] {
  const len = arr.length
  for (let sz = 1; sz < len; sz *= 2) {
    for (let i = 0; i < len - sz; i += 2 * sz) {
      const start = i
      const mid = i + sz - 1
      const end = Math.min(i + 2 * sz - 1, len - 1)
      merge(arr, start, mid, end)
    }
  }
  return arr
}

function merge(arr: number[], start: number, mid: number, end: number) {
  let i = start
  let j = mid + 1
  const tmp = []
  let k = start
  for (let w = start; w <= end; w++) {
    tmp[w] = arr[w]
  }
  while (i < mid + 1 && j < end + 1) {
    if (tmp[i] < tmp[j]) arr[k++] = tmp[i++]
    else arr[k++] = tmp[j++]
  }
  while (i < mid + 1) arr[k++] = tmp[i++]
  while (j < end + 1) arr[k++] = tmp[j++]
}
Copy the code
  • Merge sort
  • Merge sort (top down, recursive) TS implementation
  • Merge sort (bottom up, iterative method) TS implementation

Heap sort

Usually the heap is implemented with a one-dimensional array. In the case where the array starts at 0:

  1. The left child of parent I is in position 2 times I plus 1
  2. The right child of parent I is in position 2 times I plus 2
  3. The parent of child node I is in position floor((i-1) / 2)

The operation of the heap

In the data structure of the heap, the maximum value in the heap is always at the root node (the minimum value in the heap is at the root node when the heap is used in priority queues). The following operations are defined in the heap:

  1. Max Heapify: Adjusts the end child of the heap so that the child is always smaller than the parent
  2. Create Build Max Heap: Reorder all the data in the Heap
  3. HeapSort: a recursive operation that removes the root of the first data and makes the maximum heap adjustment
  • Heap sort
  • Heap sort TS implementation
function heapifyMax(arr: at, i: number, len: number) {
  const left = 2 * i + 1
  const right = 2 * i + 2
  let max = i

  if (left < len && arr[left] > arr[max]) {
    max = left
  }

  if (right < len && arr[right] > arr[max]) {
    max = right
  }

  if(max ! == i) { swap(arr, max, i) heapifyMax(arr, max, len) } }function heapifyMin(arr: at, i: number, len: number) {
  const left = 2 * i + 1
  const right = 2 * i + 2
  let min = i

  if (left < len && arr[left] < arr[min]) {
    min = left
  }

  if (right < len && arr[right] < arr[min]) {
    min = right
  }

  if(min ! == i) { swap(arr, min, i) heapifyMin(arr, min, len) } }// Build the big top heap
function buildMaxHeap(arr: at) {
  const len = arr.length
  for (let i = Math.floor(len / 2); i >= 0; i--) {
    heapifyMax(arr, i, len)
  }
}

// Build a small top heap
function buildMinHeap(arr: at) {
  const len = arr.length
  for (let i = Math.floor(len / 2); i >= 0; i--) {
    heapifyMin(arr, i, len)
  }
}

// asc is true from small to large, false from large to small
export function heapSort(arr: at, asc: boolean = true) {
  if (asc) {
    buildMaxHeap(arr)
    const len = arr.length
    for (let i = len - 1; i > 0; i--) {
      swap(arr, 0, i)
      heapifyMax(arr, 0, i)
    }
  } else {
    buildMinHeap(arr)
    const len = arr.length
    for (let i = len - 1; i > 0; i--) {
      swap(arr, 0, i)
      heapifyMin(arr, 0, i)
    }
  }
  return arr
}
Copy the code

Count sorting

It’s bound to be non-negative

Counting sort is a stable linear time sort algorithm. The algorithm was proposed by Harold H. Seward in 1954. Counting sort uses an extra array C, where the ith element is the number of elements in array A whose value is equal to I. We then arrange the elements in A into the correct position according to array C.

Its running time is t(n+k) when the input element is n integers between 0 and k. Counting sort is not comparison sort, which is faster than any comparison sort algorithm.

Since the length of the array C used to count depends on the range of data in the array to be sorted (equal to the difference between the maximum and minimum value of the array to be sorted plus 1), counting sort takes a lot of time and memory for arrays with a large range of data. For example, counting sort is the best algorithm for sorting numbers between 0 and 100, but it is not suitable for sorting names alphabetically. However, counting sort can be used in radix sort algorithms to more efficiently sort large arrays of data.

The steps of the algorithm are as follows:

  1. Find the largest and smallest elements in the array to be sorted
  2. Count the number of occurrences of each element of value I in the array, stored in the i-th entry of array C
  3. All counts add up (starting with the first element in C, adding each term to the previous one)
  4. Reverse populating the target array: place each element I in the C[I] entry of the new array, subtracting C[I] by one for each element
  • Count sorting
  • Counting sort TS implementation
export function countingSort(arr: at) {
  const bucket: at = []
  const len = arr.length
  // Array index cursor
  let sortIndex: number = 0

  for (let i = 0; i < len; i++) {
    if (bucket[arr[i]]) {
      bucket[arr[i]]++
    } else {
      // Array subscripts cannot be negative, so counting sort is limited to sorting natural numbers
      bucket[arr[i]] = 1}}for (let j = 0; j < bucket.length; j++) {
    while (bucket[j]) {
      arr[sortIndex++] = j
      bucket[j]--
    }
  }
  return arr
}
Copy the code

Radix sort

Radix sort (English: Radix sort) is a non-comparative integer sort algorithm, its principle is to cut the integers into different numbers according to the number of digits, and then compare them according to each number. Since integers can also represent strings (such as names or dates) and floating-point numbers in a particular format, radix sort is not restricted to integers. The invention of radix sorting can be traced back to Herman Holery’s contribution to the Tabulation Machine in 1887.

It is implemented by unifying all the values to be compared (positive integers) into the same numeric length, with the shorter ones preceded by zeros. Then, sort the order one by one, starting with the lowest order. So from the lowest order to the highest order, the sequence becomes an ordered sequence.

The radix sort can be LSD (Least Significant Digital) or MSD (Most Significant Digital). LSD sorts from the right of the key, while MSD sorts from the left of the key.

The time complexity of radix sort is O(k*n), where n is the number of sorted elements and k is the number of digits. This is not to say that the time complexity is necessarily better than O(nlogn). The size of k depends on the choice of numeric bits (such as bits) and the size of the whole set of data types to which the data to be sorted belongs. K determines how many rounds are processed, and n is the number of operations per round.

  • Radix sort
  • Radix sort TS implementation
export function radixSort(arr: at) :at {
  const len = arr.length
  const max = Math.max(... arr)let buckets: at[] = []
  let digit = `${max}`.length
  let start = 1
  let res: at = arr.slice()
  while (digit > 0) {
    start *= 10
    for (let i = 0; i < len; i++) {
      const j = res[i] % start
      if (buckets[j] === void 0) {
        buckets[j] = []
      }
      buckets[j].push(res[i])
    }
    res = []
    for (let j = 0; j < buckets.length; j++) {
      buckets[j] && (res = res.concat(buckets[j]))
    }
    buckets = []
    digit--
  }
  return res
}
Copy the code

Bucket sort, box sort

Bucket sort, or box sort, is a sorting algorithm that works by sorting an array into a finite number of buckets. Each bucket is sorted individually (it is possible to use another sorting algorithm or continue to use bucket sort recursively). Bucket sort is a kind of induction result of pigeon nest sort. Bucket sorting uses linear time (O(n)) when the values in the array to be sorted are evenly distributed. Bucket sort, however, is not comparison sort, and it is not affected by the lower bound O(nlogn).

Bucket sorting is done with the following procedure:

  1. Set a quantitative array as an empty bucket.
  2. Search the sequence and put the items one by one into the corresponding bucket.
  3. Sort each bucket that is not empty.
  4. Put items back into their original sequence in a bucket that is never empty.
  • Bucket sort
  • Bucket sorting TS implementation
export function bucketSort(arr: at, size: number = 5) {
  const len = arr.length
  const max = Math.max(... arr)const min = Math.min(... arr)const bucketSize = Math.floor((max - min) / size) + 1
  const bucket: at[] = []
  const res: at = []

  for (let i = 0; i < len; i++) {
    const j = Math.floor((arr[i] - min) / bucketSize) ! bucket[j] && (bucket[j] = []) bucket[j].push(arr[i])let l = bucket[j].length
    while (l > 0) {
      // The inside of each bucket is sorted
      // There is only one element that needs to be positioned
      bucket[j][l] < bucket[j][l - 1] && swap(bucket[j], l, l - 1)
      [j] bucket[j] bucket[j] bucket[j] bucket[j] bucket
      // bucket[j].sort((a, b) => a - b)
      l--
    }
  }

  // The data inside each bucket is already in order
  // Join the array in the bucket
  for (let i = 0; i < bucket.length; i++) {
    const l = bucket[i] ? bucket[i].length : 0
    for (let j = 0; j < l; j++) {
      res.push(bucket[i][j])
    }
  }
  return res
}
Copy the code

A quick performance test

Performance test code

The test conditions are

for (let i = 0; i < 100000; i++) {
  arr.push(Math.floor(Math.random() * 10000))}Copy the code

The test results

I measured many times, found that the speed of counting sort is the absolute first, of course, the space lags behind, if it is a large number of high repetition, not large spacing values can be considered. Ordinary fast sorting speed is also very fast, cardinality, bucket (may be related to the speed of bucket sorting algorithm) although non-comparison sort, but the speed is not dominant, hill, heap sort speed is very fast, and selection, bubble sort is very slow.

reference

  • hustcc/JS-Sorting-Algorithm

Welcome to my nuggets and public accounts, algorithms, TypeScript, React and their source ecology.

Recommend a very good multi-platform editor, support direct copy to wechat, Zhihu, nuggets, headlines and other platforms, the style can be customized, predefined is also very good-looking.

  • mdnice
  • GitHub