There are many common sorting algorithms, such as bubble sort, insertion sort, selection sort, merge sort, quick sort, count sort, radix sort, bucket sort and so on. This series of articles are divided into several parts to summarize the common sorting algorithms.

This paper is a series of algorithms: bubble sort, insertion sort, selection sort

Relevant concepts

  • Sorted in place

In situ sorting algorithm, is specifically refers to the space complexity is O(1) sorting algorithm. The three sorting algorithms that we’re going to talk about today, they’re all in place sorting algorithms.

  • The stability of

If there are elements with equal values in the sorted sequence, the original order of the elements remains unchanged after sorting.

Bubble sort

One bubble moves at least one element to its proper position, n times, and n numbers are sorted.

Optimization: When no data is exchanged during a bubbling operation, it indicates that the bubbling operation is in complete order and no further bubbling operation is required


Code implementation

  /** * Bubble sort * key words: compare, swap, each round of bubble produces a maximum * optimization: complete order has been achieved when there is no swap *@param arr 
   */
  bubbleSort = (arr) = > {
    if (arr.length <= 1) return arr;
    
    for (let i = 0; i < arr.length; i++) {
      let hasChange = false // Indicates a bit that is fully ordered when no swap is made
      for (let j = 0; j < arr.length - i - 1; j++) {
        if (arr[j] > arr[j + 1]) {
          const temp = arr[j]
          arr[j] = arr[j + 1]
          arr[j + 1] = temp
          hasChange = true}}if(! hasChange)break
    }
    
    return arr
  }js
Copy the code

instructions

  • Bubble sort is an in-place sort algorithm

The bubbling process only involves the exchange operation of adjacent data and only requires constant level temporary space, so its spatial complexity is O(1) and it is an in-place sorting algorithm.

  • Bubble sort is a stable sorting algorithm

When there are two adjacent elements of the same size, we do not swap, the same size of the data before and after sorting will not change the order, so bubble sort is a stable sorting algorithm.

  • Time complexity of bubble sort O(n^2)

In the best case, the time complexity is O(n), and only one bubbling operation is required to know that it is already ordered;

The worst-case time is O(n^2), the data to be sorted is exactly in reverse order, and we need to do n bubbling operations.

Insertion sort

When we insert an element into an array, we do it in the following way, that is, we walk through the array and find the appropriate position to insert the element.

Insertion sort is also based on this idea of insertion.

First, the data in the array is divided into two intervals, sorted interval and unsorted interval. The initial sorted interval has only one element, the first element of the array. The core idea of insertion algorithm is to take the elements in the unsorted interval, find the appropriate insertion position in the sorted interval, and ensure that the sorted interval data is always in order. This process is repeated until the unsorted interval is empty and the algorithm ends.

Code implementation

  /** * Insert sort * keywords: sorted and unsorted, compare, move * step: 1. Sorting [0] and unsorted [1,length-1] 2. Inserts the current unsorted value into the position of the record. * Traverses the sorted part *@param arr 
   */
  const insertionSort = (arr) = > {
    if (arr.length <= 1) return arr;
    
    for (let i = 1; i < arr.length; i++) {
      let pointer = arr[i] // I =1 is not sorted, I =0 is sorted
      let j; // Define j separately, because the loop ends with j subscript
      for (j = i - 1; j >= 0; j--) {
        // If arr[j] > arr[I], shift arr[j] backward until it finds the appropriate position j to break out of the loop and insert arr[I] at position j.
        if (arr[j] > pointer) {
          arr[j + 1] = arr[j] // Move data
        } else {
          break
        }
      }
      arr[j + 1] = pointer // Insert data. J plus 1 is because when j is equal to 0, j-- is equal to negative 1
    }
    
    return arr
  }
Copy the code

instructions

  • Insertion sort is an in-place sort algorithm
  • Insertion sort is a stable sorting algorithm
  • Insert sort is order n^2 in time.
  • Extension: The time of inserting an element into an array is O(n).

Selection sort

The implementation of selection sort algorithm is similar to insertion sort, which is divided into sorted and unsorted intervals. But select sort will find the smallest element in the unsorted range each time and place it at the end of the sorted range.

Code implementation

/** * Select sort * Keywords: sorted and unsorted, compare, move, smallest element * Step: 1. Distinguish sorted [0] from unsorted [1,length-1] 2. Traverse the unsorted part to find the minimum value 3. Swap the minimum and the last sorted bit * traverses the unsorted bit *@param arr 
   */
  const selectionSort = (arr) = > {
    if (arr.length <= 1) return arr;

    for (let i = 0; i < arr.length - 1; i++) {
      let min = i; // Assume the minimum value is arr[0]
      // Start with I +1 and select "minimum"
      for (let j = i + 1; j < arr.length; j++) {
        if (arr[j] < arr[min]) {
          min = j // Find the minimum value of the entire array. Don't swap.}}// When the minimum value is found, the swap is performed
      let temp = arr[i];
      arr[i] = arr[min];
      arr[min] = temp;
    }
    return arr
  }
Copy the code

instructions

  • Selection sort is an in-place sort algorithm
  • Select sort time O(n^2)
  • But selection sort is an unstable sorting algorithm.

For example, for a set of data such as 5, 8, 5, 2, 9, sorted by the selective sorting algorithm, the first time we find the smallest element 2, we switch places with the first 5, the order of the first 5 and the middle 5 will change, so it will be unstable.

The performance comparison

Analysis and evaluation of a sorting algorithm, generally from the execution efficiency, memory consumption and stability of three aspects.

Compared with bubble sort and insert sort, selection sort itself is unstable sorting algorithm, so it is relatively inferior.

So for bubble sort and insert sort, although bubble sort and insert sort have the same time complexity, but from the point of view of code implementation, the data exchange of bubble sort is more complex than the data movement of insert sort, because bubble sort requires three assignment operations, while insert sort only needs one. Therefore, insertion sort is often used in actual development.

These three sorting algorithms are all based on the array, but the time complexity of these three sorting methods is O(n^2), which is relatively high. In actual use, the sorting algorithm with the time complexity of O(nlogn) is still preferred. Stay tuned for future articles

reference

Geek article Sorting (I) : Why is Insertion sorting more popular than bubble Sorting?

Code reference github.com/wangzheng08…