Sorting and search algorithm learning selection sort and insertion sort

Come to Guangdong is pretty boy!! But — what’s the difference between not studying and salted fish?

This article is about selection sort and insertion sort in sorting algorithm

Selection sort

• Selection sort is an address comparison sort algorithm. The general idea of selection sort is to find the smallest value in the data structure and place it first, then find the second-smallest value and place it second, and so on.
• Here we use the auxiliary function from bubble sort in the previous article. 👉 Sort and search algorithm learning bubble

// We use the bubbling helper function in the previous sectionfunction ArrayList() {
        var array = [];
        this.insert  = function(element) {
            array.push(element);
        } 
        this.toString = function() {
            returnarray.join(); } // Swap function var swap =function(array, index1, index2) { var aux = array[index1]; array[index1] = array[index2]; array[index2] = aux; [array[index1], array[index2]] = [array[index2], Array [index1]]}} // write the selectionSort this.selectionsort = in ArrayListfunction() {
        var length = array.length, indexMin;
        for (var i = 0; i < length-1; i++) {
            indexMin = i;
            for (var y = 0; j < length; j++) {
                if (array[indexMin] > array[y]) {
                    indexMin = y
                }
            }
            if(i ! == indexMin) {
                swap(array, i, indexMin)}}}Copy the code

Select tests for sorting

    console.time('array 3') var array3 = createNotSortedArray(10); console.log(array3.toString()); / / 10,9,8,7,6,5,4,3,2,1 array3. SelectionSort (); console.log('sorted', array3.toString()); / / sorted 1,2,3,4,5,6,7,8,9,10 console. TimeEnd ('array 3') // array 3: 0.25ms
Copy the code

The 👉 selection algorithm is also an O(n²) algorithm, which, like bubbling, nested two cycles, resulting in quadratic complexity.

Insertion sort

• Concept: Build the final array by sorting one item at a time, assuming the first item is sorted, then comparing it to the second item to determine whether the second item should be placed to the left or right of the first item, and so on.
• Here we use the auxiliary function from bubble sort in the previous article. 👉 Sort and search algorithm learning bubble

// Insert sort this.insertionSort =function() {
        var length = array.length, j, temp;
        for (var i = 1; i < length; i++) {
            j = i;
            temp = array[i];
            while(j>0 && array[j-1] > temp) { array[j] = array[j-1]; j--; } array[j] = temp; }}Copy the code

Test 👌

    console.time('array 4') var array4 = createNotSortedArray(10); console.log(array4.toString()); / / 10,9,8,7,6,5,4,3,2,1 array4. InsertionSort (); console.log('sorted', array4.toString()); / / sorted 1,2,3,4,5,6,7,8,9,10 console. TimeEnd ('array 4') // array 4: 0.222021484375ms
Copy the code

As you can see from time, this algorithm performs better than selection sort and bubble sort (sorting small arrays)

Sweat is the lubricant of success. Sweat is the lubricant of success.