Moment For Technology

Sorting - Summary of the top 10 sorting algorithms

Posted on Dec. 2, 2022, 6:27 a.m. by Ryan Chaudhary
Category: The front end Tag: Sorting algorithm

The third tier

Bubble sort

The idea of bubble sort is to compare adjacent elements in pairs. When an element is larger than the adjacent element on the right, they are swapped. When an element is less than or equal to the adjacent element on the right, the position does not change

The implementation code

Function bubbleSort(list:Arraynumber) {for (let I = 0; i  list.length - 1; For (let j = 0; let j = 0; let j = 0; j  list.length - i -1; j++) { if( list[j]  list[j+1]) { let temp = list[j]; list[j] = list[j+1]; list[j+1] = temp } } } return list }Copy the code

Optimization 1: Whether tags are ordered

Function bubbleSortTwo(list:Arraynumber) {for (let I = 0; i  list.length - 1; For (let j = 0; let j = 0; let j = 0; j  list.length - i -1; j++) { if( list[j]  list[j+1]) { let temp = list[j]; list[j] = list[j+1]; List [j+1] = temp = false}} if(isSorted) {break}} return list}Copy the code

Optimization 3: ordered area optimization

Function bubbleSortThree(list:Arraynumber) {let sortBorder = list.length-1; // Let lastExcChangeIndex = 0; For (let I = 0; let I = 0; i  list.length - 1; i++) { let isSorted = true; For (let j = 0; let j = 0; j  sortBorder; j++) { if( list[j]  list[j+1]) { let temp = list[j]; list[j] = list[j+1]; list[j+1] = temp; // If an exchange occurs, then isSorted = false; LastExcChangeIndex = j}} sortBorder = lastExcChangeIndex if(isSorted) {break}} return list}Copy the code

Cocktail optimization

Each round of bubble sort compares elements from left to right, making a one-way comparison, whereas cocktail sort compares and swaps elements in both directions

Function bubbleSortFour(list:Arraynumber) {let outLength = math.floor (list.length/2) for (let i = 0; i  outLength; i++) { let sorted = true; For (let j = I; j  list.length - 1 - i; j++) { if(list[j]  list[j + 1]){ let temp = list[j]; list[j] = list[j + 1]; list[j + 1] = temp sorted = false } } if(sorted){ break } sorted = true; For (let j = list.length-1-i; j  i ; j--) { if(list[j]  list[j - 1]){ let temp = list[j]; list[j] = list[j - 1]; list[j - 1] = temp; sorted = false; } } if(sorted) { break } } return list }Copy the code

Cocktail + ordered area optimization

Function bubbleSortFive(list:Arraynumber) {let leftSortBorder = 0; let leftLastSortIndex= 0; let rightSortBorder = list.length - 1; let rightLastSortIndex = 0; Let outLength = math.floor (list.length/2) for (let I = 0; i  outLength; i++) { let sorted = true; For (let j = leftSortBorder; j  rightSortBorder; j++) { if(list[j]  list[j + 1]){ let temp = list[j]; list[j] = list[j + 1]; list[j + 1] = temp sorted = false; RightLastSortIndex = j; } // Assign the right boundary rightSortBorder = rightLastSortIndex if(sorted){break} sorted = true; For (let j = rightSortBorder; j  leftSortBorder ; j--) { if(list[j]  list[j - 1]){ let temp = list[j]; list[j] = list[j - 1]; list[j - 1] = temp; sorted = false; LeftLastSortIndex = j-1; If (sorted) {break}} return list}Copy the code

Best explanation: my personal blog, need TZ, here is the nugget version

Selection sort

The idea of selection sort: each round to select the smallest, directly switched to the left of the array

The implementation code

      function sort(arr:Arraynumber) {
          for (let index = 0; index  arr.length - 1; index++) {
              let minIndx = index;
              for (let j = index + 1; j  arr.length; j++) {
                  if(arr[j]  arr[minIndx]) {
                      minIndx = j
                  }            
              };
              let temp = arr[minIndx];
              arr[minIndx] = arr[index];
              arr[index] = temp
                      
          }
          return arr
      }
Copy the code

Selection sort solves the code efficiency problem caused by the frequent element exchange operation of bubble sort, but also becomes unstable sort

Best explanation: my personal blog, need TZ, here is the nugget version

Insertion sort

The idea of insertion sort is to maintain an ordered area and insert the elements one by one into the appropriate place in the ordered area until all the elements are ordered

The implementation code

function insertSort(arr:Arraynumber) { for (let index = 1; index  arr.length; index++) { let temp = arr[index]; let j = index - 1; // Compare elements from the right and shift for (; j = 0  arr[j]  temp; J --) {arr[j + 1] = arr[j]} insertValue arr[j + 1] = temp} return arr};Copy the code

Best explanation: my personal blog, need TZ, here is the nugget version

summary

The average time complexity of the sorting algorithms in the third tier is O(n2).

Differences and differences

1. Performance

The number of comparisons and exchanges of elements in bubble and insert sorts depends on how ordered the original array is

But overall, insertion sort performs slightly better than bubble sort

Because in bubble sort, each of the two elements are exchanged independently of each other

Insertion sort is continuous

Obviously insertion sort eliminates a lot of unnecessary swapping

In addition, selection sort is different from the previous two. It has a fixed number of commutations of elements, regardless of the order of the original array

Therefore, when the original array is nearly ordered, the performance of insertion sort is the best, and when most elements of the original array are unordered, the performance of selection sort is the best

2. Whether it is stable

Bubble sort and insertion sort are stable, and selection sort is unstable

The second tier

Heap sort

Heapsort idea: Heapsort is a sorting algorithm based on binary heap, which has the ability of self-adjustment. It can be summarized as: to build the unordered array into binary heap, if the order needs to be ascending, the maximum binary heap will be built; if the order needs to be descending, the minimum binary heap will be built

The implementation code

/** * @param {Arraynumber} arr Specifies the heap to be adjusted * @param {number} parentIndex Specifies the parent node to be dropped * @param {number} Length Specifies the valid heap size * @description */ function downAdjust(arr: Arraynumber, parentIndex: Number, length:number) {// temp Stores the value of the parent node and uses it as the final assignment. Let temp = arr[parentIndex]; // Let childrenIndex = parentIndex * 2 + 1; While (childrenIndex  length) {// if right node is present, If (childrenIndex + 1  length  ARR [childrenIndex + 1]  ARR [childrenIndex]) {childrenIndex = childrenIndex + 1; If (temp = arr[childrenIndex]) {break} arr[parentIndex] = arr[childrenIndex]; parentIndex = childrenIndex childrenIndex = childrenIndex * 2 + 1 } arr[parentIndex] = temp; } /** * @param {Arraynumber} * @description */ function heapSort(arr:Arraynumber) {// 1. For (let index = arr.length-2; index = 0; Index --) {downAdjust(arr, index, arr.length - 1)} console.log(' maximum heap: %j', arr) // 2. For (let index = arr.length-1; index = 0; Index --) {// swap the last element with the top of the heap let temp = arr[0]; arr[0] = arr[index]; arr[index] = temp; / / sink to adjust the maximum heap downAdjust (arr. Zero, index) / / the index value of effective length of pile Very clever here}} the function main () {let arr = [1, 3, 2, 6, 5, 7, 8, 9, 10, 0]; heapSort(arr); console.log(arr) }Copy the code

Best explanation: my personal blog, need TZ, here is the nugget version

Merge sort

Merge sort idea: split the array into two groups, ordered merge, and recursion, classic divide and conquer idea

The implementation code

Function merge(arr:Arraynumber, start:number, end:number, middle:number) { Let tempArray = new Array(end-start + 1); let p1 = start; let p2 = middle + 1; let p = 0; while(p1 = middle  p2 = end) { if(arr[p1] = arr[p2] ) { tempArray[p++] = arr[p1++] } else { tempArray[p++] = While (p1 = middle) {tempArray[p++] = arr[p1++]} while(p2 = end) { TempArray [p++] = arr[p2++]} for (let index = 0; index  tempArray.length; index++) { arr[start + index] = tempArray[index] } } function sort(arr:Arraynumber, start:number, End :number) {if(start  end) {/* start = 5; end = 10; The middle = 7; Note that we're rounding down: 5,6,7,8,9,10, so middle=7; 5,6,7 as a group; If 8, 9, 10 is a group of 6,7,8,9,10, middle=8; 6,7,8 as a group; 9 and 10 are a set of formulas: Math. Floor ((end-start)/2) + start Math.floor(A / Math.pow(2, B)) =  Math. Floor (A/(2 * * B)) =  (A   B) so: Math. The floor ((end - start) / 2) + start = = = ((end - start)   1) + start * / / / Let middle = ((end-start)1) + start; let middle = ((end-start)1) + start; sort(arr, start, middle); sort(arr, middle + 1, end); Function main() {const arr = [5, 8, 6, 3, 9, 2, 1, 7]; const arr = [5, 8, 6, 3, 9, 2, 1, 7]; console.log(sort(arr, 0, arr.length - 1)) }Copy the code

Best explanation: my personal blog, need TZ, here is the nugget version

Quick sort

The idea of quicksort: Quicksort is also a classic representation of the idea of divide and conquer, namely: select a reference element, larger than it on one side, smaller than it on the other side, and recurse

Implementation code:

Bilateral method:

/** * @param {Arraynumber} arr Array to be exchanged * @param {number} startIndex startIndex * @param {number} endIndex endIndex * @returns */ function partition(arR: Arraynumber, startIndex: number, endIndex: number) Const pivot = arr[startIndex]; const pivot = arr[startIndex]; // Left pointer let left = startIndex; // Let right = endIndex; while(left ! = right) {// While (left  right  arr[right]  pivot) {right--} // While (left  right  arr[right]  pivot) {left -- Arr [left] = pivot) {left++} if(left  right) {let p = arr[left]; arr[left] = arr[right]; arr[right] = p; } // Arr [startIndex] = arr[left]; arr[left] = pivot; /* How to ensure that the swapped left element is either less than or greater than the base element? If either left or right stops, If left = right, then right must be an element less than = pivot */ return left} function quickSort(arr: Arraynumber, startIndex: number, endIndex: Number) {if(startIndex = endIndex) {return} let pivotIndex = partition(arR, startIndex, endIndex); QuickSort (ARR, startIndex, pivotIndex - 1); quickSort(arr, pivotIndex + 1, endIndex); } function main() { let arr = [4, 2, 6, 2, 2, 2, 2, 8]; quickSort(arr, 0, arr.length - 1 ); console.log(arr) }Copy the code

Unilateral method:

/** * @param {Arraynumber} arr Array to be exchanged * @param {number} startIndex start position * @param {number} endIndex End position * @description Function partition(arR: Arraynumber, startIndex: number, endIndex: number); Let pivot = arr[startIndex]; let pivot = arr[startIndex]; // Let mark = startIndex; for (let index = startIndex; index = endIndex; index++) { if(arr[index]  pivot) { mark++; let p =arr[mark]; arr[mark] = arr[index]; arr[index] = p } } arr[startIndex] = arr[mark]; arr[mark] = pivot; return mark } function quickSort(arr: Arraynumber, startIndex: number, endIndex: number){ if(startIndex = endIndex) { return } const pivotIndex = partition(arr, startIndex, endIndex); quickSort(arr, startIndex, pivotIndex - 1); quickSort(arr, pivotIndex + 1, endIndex) } function main() { let arr = [4, 4, 6, 5, 3, 2, 8, 1]; quickSort(arr, 0, arr.length - 1); console.log(arr) }Copy the code

Non-recursive implementation:

/** * @param {Arraynumber} arr Array to be sorted * @param {number} startIndex Start position * @param {number} endIndex End position * @returns Function partition(arR: Arraynumber, startIndex: number, endIndex: number) Number) {// let pivot = arr[startIndex] // Let mark = startIndex for (let index = startIndex; index = endIndex; index++) { if(arr[index]  pivot) { mark++; let p = arr[mark]; arr[mark] = arr[index]; arr[index] = p } }; arr[startIndex] = arr[mark]; arr[mark] = pivot; return mark } interface StackItem { startIndex: number; endIndex: number; } function quickSort(arr: Arraynumber, startIndex: number, endIndex: Number) {// use a stack instead of a recursive call stack let quickSortStack:ArrayStackItem = []; Let obj:StackItem = {startIndex, endIndex}; quickSortStack.push(obj); While (quickSortStack.length) {let item = quickSortStack.pop() as StackItem; let { startIndex, endIndex } = item let pivotIndex = partition(arr, startIndex, endIndex); If (startIndex  pivotIndex - 1) {quickSortStack.push({startIndex, endIndex: pivotIndex - 1 }) } if(endIndex  pivotIndex + 1) { quickSortStack.push({ startIndex : pivotIndex + 1, endIndex: endIndex }) } } } function main() { let arr = [4, 4, 6, 5, 3, 2, 8, 1]; quickSort(arr, 0, arr.length - 1); console.log(arr) }Copy the code

Best explanation: my personal blog, need TZ, here is the nugget version

Hill sorting

Hill sort is an updated version of insertion sort, which does some "preprocessing" of the original array to make most of the elements of the original array ordered

The implementation code

    function sort(arr: Arraynumber) {
        let d = arr.length;
        while(d  1) {
            d = Math.floor(d / 2);
            for (let x = 0; x  d; x++) {
                for (let index = x + d; index  arr.length; index+=d) {
                    let temp = arr[index];
                    let j = index - d;
                    for (; j = 0  arr[j]  temp; j-= d) {
                        arr[index] = arr[j];
                    }
                    arr[j+ d] = temp;
                }
            }
        }
        return arr
    }
Copy the code

Best explanation: my personal blog, need TZ, here is the nugget version

summary

The second tier is an order of magnitude better than the third tier

The average time complexity of hill sort is the fastest to reach O(n1.3), and the average time complexity of quicksort, merge sort and heapsort is in O(nlogn).

Differences between the latter three:

1. Quicksort has an average time of O(nlogn), but in the extreme case it is O(n2), while heapsort and merge sort are stable at O(nlogn).

2. In terms of average complexity, heapsort performance is slightly lower than quicksort and merge sort, mainly because the parent and child nodes of binary heap are not contiguous in memory

When access to memory data, order to store data, reading and writing is often the highest efficiency, according to the principle of the space limitations of CPU, each time the CPU access memory, the memory in the adjacent data is also stored in cache, read the data, the adjacent next time need not read from the memory, but directly read from the CPU cache

3. Merge sort is stable, heap sort and quicksort are unstable

4. Quicksort and heapsort do not require additional storage space, while merge sort requires the creation of merge array

The first tier

Count sorting

The idea of counting sort is to determine the position of elements based on their subscripts, without comparing or swapping elements

The implementation code

Simple version of

function countSort(arr: Arraynumber):Arraynumber { // 1. Let Max = arr[0]; for (let index = 1; index  arr.length; index++) { if(arr[index]  max) { max = arr[index] } } // 2. Let countArray = (new Array(Max + 1)).fill(0); For (let index = 0; // 3. index  arr.length; Index ++) {countArray[arr[index]]++} let sortedArray = new Array(); for (let index = 0; index = countArray.length; index++) { for (let j = 0; j  countArray[index]; j++) { sortedArray.push(index) } } return sortedArray }Copy the code

Optimized version

function countSort(arr: Arraynumber) { // 1. Let Max = arr[0]; let min = arr[0]; for (let index = 1; index  arr.length; index++) { if(arr[index]  max) { max = arr[index] } if(arr[index]  min) { min = arr[index] } } // 2. Let length = max-min + 1; let countArray = (new Array(length)).fill(0) // 3. For (let index = 0; index  arr.length; index++) { countArray[arr[index] - min]++ } // 4. Let sortedArray = [] for (let index = 0; index  countArray.length; index++) { for (let j = 0; j  countArray[index]; j++) { sortedArray.push(index + min) } } return sortedArray }Copy the code

Stable version

function countSort(arr: Arraynumber) { // 1. Let Max = arr[0]; let min = arr[0]; for (let index = 1; index  arr.length; index++) { if(arr[index]  max) { max = arr[index] } if(arr[index]  min) { min = arr[index] } } // 2. Let length = max-min + 1; let countArray = (new Array(length)).fill(0) // 3. For (let index = 0; index  arr.length; index++) { countArray[arr[index] - min]++ } // 4. For (let index = 1; let index = 1; index  countArray.length; index++) { countArray[index] += countArray[index - 1] } // 5. SortedArray = new Array(arr.length); sortedArray = new Array(arr.length); for (let index = arr.length - 1; index = 0; SortedArray [countArray[arr[index] -min] -1] = arr[index] countArray[arr[index] -min] -1] = arr[index] countArray[arr] index  - min]-- } return sortedArray }Copy the code

Best explanation: my personal blog, need TZ, here is the nugget version

Bucket sort

Bucket sort is an updated version of counting sort, making up for the limitations of counting sort (counting sort is not applicable to non-integer sort).

The implementation code

function bucketSort(arr:Arraynumber) { // 1. D let Max = arr[0]; let min = arr[0]; for (let index = 0; index  arr.length; index++) { if(arr[index]  max) { max = arr[index] } if(arr[index]  min) { min = arr[index] } } const d = max - min; // 2. Const bucketNum = arr.length; / * small pit: Let bucketList = new Array(bucketNum).fill([]) */ let bucketList = new Array(bucketNum) for (let index = 0; index  bucketList.length; index++) { bucketList[index] = [] } // 3. Let area = d/(bucketnum-1); let area = d/(bucketnum-1); for (let index = 0; index  arr.length; index++) { let num = Math.floor((arr[index] - min)/area); BucketList [num].push(arr[index])} /* bucketList[num].push(arr[index])} (element -min)/area = the number of buckets in the array, which in theory should be round up, but the array index is from 0, so it is math.floor 2. Because (Max. -min)/area must be the last bucket and an integer, that is:  d = max - min area = d/num result = (max - min)/area = (max - min)/d * num = (max - min)/(max - min) * num result === */ // 4. */ // 4. */ // 4. For (let index = 0; index  bucketList.length; index++) { bucketList[index] = bucketList[index].sort((a:number, B :number) = (a-b))} return bucketList.flat()}Copy the code

Best explanation: my personal blog, need TZ, here is the nugget version

Radix sort

Radix sort is also to solve the limitations of counting sort, such as sorting English words, the idea is: to split the work into multiple rounds, each round of a single character using counting sort

The implementation code

// Value range of ASCII code let ASCII = 128; function getCharIndex(str:string,index:number):number { if(str.length = index) { return 0 } return str.charCodeAt(index) } function radixSort(arr:Arraystring, maxLength:number) { let sortedArray = new Array(arr.length); for (let k = maxLength - 1; k = 0; K --) {// let countArray = new Array(ASCII).fill(0); for (let index = 0; index  arr.length; index++) { let i = getCharIndex(arr[index], k) countArray[i]++ } // 2. For (let index = 1; let index = 1; index  countArray.length; index++) { countArray[index] += countArray[index-1] } // 3. For (let index = arr.length-1; let index = arr. index = 0; index--) { let i = getCharIndex(arr[index], k); let sortedIndex = countArray[i] - 1; sortedArray[sortedIndex] = arr[index]; countArray[i]-- } arr=[...sortedArray] } return arr } function main() { const arr = ['qd', 'abc', 'qwe', 'hhh', 'a', 'cws', 'ope']; console.log(radixSort(arr, 3)) }Copy the code

summary

The first echelon of sorting algorithms are linear complexity sorting algorithms

The counting sort algorithm has a time complexity of O(n + m) where m is the range of the original array

The bucket sort algorithm has a time complexity of O(n) where n is the number of buckets

The time complexity of radix sorting algorithm is O(k(n + m)), where K is the maximum number of bits of an element, and m is the value range of each bit

In addition, these three sorting algorithms are stable sorting

Great summary

Summary from: comic algorithm little grey algorithm journey + programmer little grey princess article

Search
About
mo4tech.com (Moment For Technology) is a global community with thousands techies from across the global hang out!Passionate technologists, be it gadget freaks, tech enthusiasts, coders, technopreneurs, or CIOs, you would find them all here.