javascript implements five sorting algorithms (bubble sorting, selection sorting, insertion sorting, Hill sorting and quick sorting) j

Bubble sorting algorithm O(N*N) of sorting algorithm:

Principle:
1. Compare the size relationship of two adjacent elements from beginning to end for each element that is not sorted
2. If the element on the left is large, the two elements exchange positions
3. Move one position to the right and compare the following two elements
4. Moving to the rightmost end is, and the largest element is at the rightmost end
5. Then start with a new idea, this time go to the penultimate position, and so on

Code implementation:

let array = [78,1,56,45,12,36,99,84,23,7]

for (let j = array.length - 1; j >= 0; j--) {
    for (let i = 0; i < j; i++) {
        if (array[i] > array[i+1]) {
            let temp = array[i]
            array[i] = array[i+1]
            array[i+1] = temp
        }
    }
}
console.log(array.join())

result

1 7 12 23 36 45 56 78 84 99

Selection of sorting algorithm O(N):

Principle:
1. First, find the smallest (large) element in the unordered sequence and store it at the beginning of the sorted sequence.
2. Then continue to find the smallest (large) element from the remaining unordered elements, and then put it at the end of the sorted sequence.
3. Repeat step 2 until all elements are sorted.

Code implementation:

let array = [78,1,56,45,12,36,99,84,23,7]
//Select sort
for (let j = 0; j < array.length - 1; j++) {
    let min = j
    for (let i = min + 1; i < array.length; i++) {
        if (array[min] > array[i]) {
            min = i
        }
     }
    let temp = array[j]
    array[j] = array[min]
    array[min] = temp
}

result:

1 7 12 23 36 45 56 78 84 99

Insertion sorting algorithm of sorting algorithm:

Principle:
1. Start the comparison from the second data of the array, that is, use the second number to compare with the previous one at the beginning. If the conditions are met (larger or smaller than the previous one, customized), let them exchange positions.
2. Then compare the third number with the second. If it meets the requirements, it will be exchanged. However, we have to continue to compare here. For example, there are five numbers, 8, 15, 20, 45, 17 and 17, which are smaller than 45. They need to be exchanged, but 17 is also smaller than 20. When they do not need to be exchanged with 15, they do not need to be compared with the data in front of 15. They certainly do not need to be exchanged, Because the previous data are orderly.
3. Repeat step 2 until all the data are arranged.

Code implementation:

let array = [78,1,56,45,12,36,99,84,23,7]
//Insert sort
for (let i = 1; i < array.length; i++) {
    let temp = array[i]
    let j = i
    while (array[j - 1] > temp && j > 0) {
        array[j] = array[j - 1]
        j--
    }
    array[j] = temp
}

result:

1 7 12 23 36 45 56 78 84 99

Hill sorting algorithm of sorting algorithm:

Hill sort is a sort algorithm proposed by Donald Shell in 1959. Hill sort is also an insertion sort. It is a more efficient version of simple insertion sort, also known as reduced incremental sort
Hill sort is to group records by certain increment of subscript, and sort each group by direct insertion sort algorithm; As the increment decreases, each group contains more and more keywords. When the increment decreases to 1, the whole file is just divided into one group, and the algorithm terminates.

Code implementation:

let array = [78,1,56,45,12,36,99,84,23,7]
//First increment
//Shell Sort 
//Initialization increment
let gap = Math.floor(array.length / 2)

while (gap >= 1) {
     for (let i = gap; i < array.length; i++) {
         let temp = array[i]
         let j = i

         while (array[j - gap] > temp && j > gap - 1) {
             array[j] = array[j - gap]
             j -= gap
         }
         array[j] = temp
     }

     gap = Math.floor(gap / 2)
}

result:

1 7 12 23 36 45 56 78 84 99

Quick sorting algorithm of sorting algorithm:

Steps:
1. Select a benchmark in the array;
2. Move the data less than the benchmark number in the array to the left of the benchmark number, and move the data greater than the benchmark number to the right;
3. For the arrays on the left and right sides of the benchmark number, repeat the above two processes until each subset has only one element, that is, it is all ordered.
Selection of reference number:
Usually select the first element of the array

let array = [78,1,56,45,12,36,99,84,23,7]
                       
function QuickSort(array,left,right) {
    if (left >= right) {
       return
    }

    let pivot = array[left] //Take the first number of the interval as the reference number
    let l = left //The "pointer" when searching from left to right indicates the current left position
    let r = right //The "pointer" when searching from right to left indicates the current right position

   while ( l < r) {
        while ( l < r && array[r] > pivot) {
            r--
        }
       while ( l < r && array[l] <= pivot) {
           l++
       }
       if (l < r) {
           let temp = array[l]
           array[l] = array[r]
           array[r] = temp
       }
   }
    array[left] = array[l]
    array[l] = pivot
    QuickSort(array,left,l-1)
    QuickSort(array,l+1,right)
}

QuickSort(array,0,array.length - 1)
console.log(array.join(' '))

result:

1 7 12 23 36 45 56 78 84 99

Keywords: Algorithm data structure quick sort

Added by magic2goodil on Thu, 23 Dec 2021 13:31:02 +0200