The most basic front-end algorithm

Bubble Sort

Instructions for bubble sorting:
As one of the simplest sorting algorithms, bubble sorting gives me the same feeling as that of Abandon in the word book. It comes first on the first page every time, so I am most familiar with... Another optimization algorithm for bubble sorting is to set up a flag. When there is no exchange of elements in a sequence traversal, it proves that the sequence has been ordered. But this improvement doesn't do much to improve performance...

Best Cases:
When the input data is already in positive order (they are already in positive order, I want you to bubble sort. What's the use...)

When is the slowest case:
When the input data is in reverse order (just write a for loop to output data in reverse order. Why use you to bubble sort? Am I free...)

Bubble sorting JavaScript code implementation:

 1 function bubbleSort(arr) {
 2     var len = arr.length;
 3     for (var i = 0; i < len; i++) {
 4         for (var j = 0; j < len - 1 - i; j++) {
 5             if (arr[j] > arr[j+1]) {        //Pairwise comparison of adjacent elements
 6                 var temp = arr[j+1];        //Element exchange
 7                 arr[j+1] = arr[j];
 8                 arr[j] = temp;
 9             }
10         }
11     }
12     return arr;
13 }

Selection Sort

Instructions for selecting sorting:
One of the most stable sorting algorithms in terms of time complexity, because no matter what data goes in, it is O(n) ²) Time complexity... So when using it, the smaller the data scale, the better. The only advantage may be that it doesn't take up extra memory space.

Select Sorting JavaScript code implementation:

 1 function selectionSort(arr) {
 2     var len = arr.length;
 3     var minIndex, temp;
 4     for (var i = 0; i < len - 1; i++) {
 5         minIndex = i;
 6         for (var j = i + 1; j < len; j++) {
 7             if (arr[j] < arr[minIndex]) {     //Find the smallest number
 8                 minIndex = j;                 //Save the index of the smallest number
 9             }
10         }
11         temp = arr[i];
12         arr[i] = arr[minIndex];
13         arr[minIndex] = temp;
14     }
15     return arr;
16 }

Insertion Sort

Insert sorting instructions:
Although the code implementation of insertion sorting is not as simple and rough as bubble sorting and selection sorting, its principle should be the easiest to understand, because anyone who has played poker should be able to understand it. Of course, if you say that you never sort your cards according to the size of the cards when you play cards and touch them, it's estimated that you won't be interested in the insertion sorting algorithm in your life...
Like bubble sort, insertion sort also has an optimization algorithm called split half insertion. For this algorithm, if I get lazy cancer, I will apply a classic sentence in the textbook: interested students can study it by themselves after class...

Insert sorting JavaScript code implementation:

 1 function insertionSort(arr) {
 2     var len = arr.length;
 3     var preIndex, current;
 4     for (var i = 1; i < len; i++) {
 5         preIndex = i - 1;
 6         current = arr[i];
 7         while(preIndex >= 0 && arr[preIndex] > current) {
 8             arr[preIndex+1] = arr[preIndex];
 9             preIndex--;
10         }
11         arr[preIndex+1] = current;
12     }
13     return arr;
14 }

Shell Sort

Instructions for Hill sorting:
Hill sort is a more efficient implementation of insert sort. It differs from insert sorting in that it preferentially compares elements that are far away. The core of Hill sort is the setting of interval sequence. The interval sequence can be set in advance or defined dynamically. The algorithm for dynamically defining interval sequence was proposed by Robert Sedgewick, co-author of algorithm (4th Edition). Here, I use this method.

Hill sorting JavaScript code implementation:

 1 function shellSort(arr) {
 2     var len = arr.length,
 3         temp,
 4         gap = 1;
 5     while(gap < len/3) {          //Dynamically define interval sequence
 6         gap =gap*3+1;
 7     }
 8     for (gap; gap> 0; gap = Math.floor(gap/3)) {
 9         for (var i = gap; i < len; i++) {
10             temp = arr[i];
11             for (var j = i-gap; j > 0 && arr[j]> temp; j-=gap) {
12                 arr[j+gap] = arr[j];
13             }
14             arr[j+gap] = temp;
15         }
16     }
17     return arr;
18 }

Merge Sort

Instructions for merging and sorting:
As a typical algorithmic application of the idea of divide and conquer, the implementation of merge sorting consists of two methods:

Top down recursion (all recursive methods can be rewritten iteratively, so there is the second method)
Bottom up iteration
The author describes the structure of the algorithm in the bottom-up JavaScript. However, for the recursive method, the author believes that:

However, it is not possible to do so in JavaScript, as the recursion goes too deep
for the language to handle.
However, this approach is not feasible in JavaScript because the recursion depth of the algorithm is too deep for it.

Merge and sort JavaScript code implementation:

 1 function mergeSort(arr) {  //The top-down recursive method is adopted
 2     var len = arr.length;
 3     if(len < 2) {
 4         return arr;
 5     }
 6     var middle = Math.floor(len / 2),
 7         left = arr.slice(0, middle),
 8         right = arr.slice(middle);
 9     return merge(mergeSort(left), mergeSort(right));
10 }
11 
12 function merge(left, right)
13 {
14     var result = [];
15 
16     while (left.length>0 && right.length>0) {
17         if (left[0] <= right[0]) {
18             result.push(left.shift());
19         } else {
20             result.push(right.shift());
21         }
22     }
23 
24     while (left.length)
25         result.push(left.shift());
26 
27     while (right.length)
28         result.push(right.shift());
29 
30     return result;
31 }

Quick Sort

Quick sort instructions:
It is also a typical application of the idea of divide and conquer in sorting algorithm. In essence, quick sort should be a recursive divide and conquer method based on bubble sort.
Quick sorting is fast and efficient! It is one of the fastest sorting algorithms to process big data. Although the time complexity of Worst Case reaches O(n ²), But others are excellent. In most cases, they perform better than the sorting algorithm with an average time complexity of O(n log n). But why? I don't know... Fortunately, my obsessive-compulsive disorder was committed again. After checking more than N materials, I finally found a satisfactory answer in the algorithm art and informatics competition:

The worst case scenario for quicksort is O(n) ²), For example, the fast arrangement of sequential sequence. However, its expected spreading time is O(n log n), and the constant factor implicit in the O(n log n) sign is very small, which is much smaller than the merging sorting with stable complexity equal to O(n log n). Therefore, for the vast majority of random sequences with weak order, quick sorting is always better than merge sorting.

to update:
The advantages and disadvantages of quick sorting are more clearly explained in the fourth edition of the algorithm:

The inner loop of quick sort is shorter than most sorting algorithms, which means that it is faster both in theory and in practice. Its main disadvantage is that it is very fragile, and we should be very careful in implementation to avoid poor performance.

Quick sort JavaScript code implementation:

 1 function quickSort(arr, left, right) {
 2     var len = arr.length,
 3         partitionIndex,
 4         left = typeof left != 'number' ? 0 : left,
 5         right = typeof right != 'number' ? len - 1 : right;
 6 
 7     if (left < right) {
 8         partitionIndex = partition(arr, left, right);
 9         quickSort(arr, left, partitionIndex-1);
10         quickSort(arr, partitionIndex+1, right);
11     }
12     return arr;
13 }
14 
15 function partition(arr, left ,right) {     //Partition operation
16     var pivot = left,                      //Set reference value (pivot)
17         index = pivot + 1;
18     for (var i = index; i <= right; i++) {
19         if (arr[i] < arr[pivot]) {
20             swap(arr, i, index);
21             index++;
22         }        
23     }
24     swap(arr, pivot, index - 1);
25     return index-1;
26 }
27 
28 function swap(arr, i, j) {
29     var temp = arr[i];
30     arr[i] = arr[j];
31     arr[j] = temp;
32 }

Heap Sort

Instructions for heap sorting:
Heap sort can be said to be a selective sort that uses the concept of heap to sort. There are two methods:

Large top heap: the value of each node is greater than or equal to the value of its child nodes. It is used for ascending arrangement in heap sorting algorithm

Small top heap: the value of each node is less than or equal to the value of its child nodes, which is used for descending arrangement in heap sorting algorithm

Heap sorting JavaScript code implementation:

1 var len;    //Because multiple functions declared need data length, set len as a global variable
 2 
 3 function buildMaxHeap(arr) {   //Build large top reactor
 4     len = arr.length;
 5     for (var i = Math.floor(len/2); i &gt;= 0; i--) {
 6         heapify(arr, i);
 7     }
 8 }
 9 
10 function heapify(arr, i) {     //Heap adjustment
11     var left = 2 * i + 1,
12         right = 2 * i + 2,
13         largest = i;
14 
15     if (left < len && arr[left] > arr[largest]) {
16         largest = left;
17     }
18 
19     if (right < len && arr[right] > arr[largest]) {
20         largest = right;
21     }
22 
23     if (largest != i) {
24         swap(arr, i, largest);
25         heapify(arr, largest);
26     }
27 }
28 
29 function swap(arr, i, j) {
30     var temp = arr[i];
31     arr[i] = arr[j];
32     arr[j] = temp;
33 }
34 
35 function heapSort(arr) {
36     buildMaxHeap(arr);
37 
38     for (var i = arr.length-1; i > 0; i--) {
39         swap(arr, 0, i);
40         len--;
41         heapify(arr, 0);
42     }
43     return arr;
44 }

Counting Sort

Instructions for counting and sorting:
The core of counting and sorting is to convert the input data values into keys and store them in the additional array space.
As a sort with linear time complexity, count sort requires that the input data must be integers with a certain range.

JavaScript code implementation of counting and sorting:

 1 function countingSort(arr, maxValue) {
 2     var bucket = new Array(maxValue+1),
 3         sortedIndex = 0;
 4         arrLen = arr.length,
 5         bucketLen = maxValue + 1;
 6 
 7     for (var i = 0; i < arrLen; i++) {
 8         if (!bucket[arr[i]]) {
 9             bucket[arr[i]] = 0;
10         }
11         bucket[arr[i]]++;
12     }
13 
14     for (var j = 0; j < bucketLen; j++) {
15         while(bucket[j] > 0) {
16             arr[sortedIndex++] = j;
17             bucket[j]--;
18         }
19     }
20 
21     return arr;
22 }

Bucket Sort

Bucket sorting instructions:
Bucket sorting is an upgraded version of counting sorting. It makes use of the mapping relationship of the function. The key to efficiency lies in the determination of the mapping function.
In order to make bucket sorting more efficient, we need to do these two things:

When there is enough extra space, try to increase the number of barrels
The mapping function used can evenly distribute the input N data into K buckets
At the same time, for the sorting of elements in the bucket, it is very important to choose a comparative sorting algorithm for the performance.

Best Cases:
When the input data can be evenly distributed to each bucket

When is the slowest case:
When the input data is allocated to the same bucket

Bucket sorting JavaScript code implementation:

 1 function bucketSort(arr, bucketSize) {
 2     if (arr.length === 0) {
 3       return arr;
 4     }
 5 
 6     var i;
 7     var minValue = arr[0];
 8     var maxValue = arr[0];
 9     for (i = 1; i < arr.length; i++) {
10       if (arr[i] < minValue) {
11           minValue = arr[i];                //Minimum value of input data
12       } else if (arr[i] > maxValue) {
13           maxValue = arr[i];                //Maximum value of input data
14       }
15     }
16 
17     //Initialization of bucket
18     var DEFAULT_BUCKET_SIZE = 5;            //Set the default number of buckets to 5
19     bucketSize = bucketSize || DEFAULT_BUCKET_SIZE;
20     var bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;   
21     var buckets = new Array(bucketCount);
22     for (i = 0; i < buckets.length; i++) {
23         buckets[i] = [];
24     }
25 
26     //The mapping function is used to allocate the data to each bucket
27     for (i = 0; i < arr.length; i++) {
28         buckets[Math.floor((arr[i] - minValue) / bucketSize)].push(arr[i]);
29     }
30 
31     arr.length = 0;
32     for (i = 0; i < buckets.length; i++) {
33         insertionSort(buckets[i]);                      //Sort each bucket. Insert sort is used here
34         for (var j = 0; j < buckets[i].length; j++) {
35             arr.push(buckets[i][j]);                      
36         }
37     }
38 
39     return arr;
40 }

Radix Sort

Instructions for cardinality sorting:
There are two methods of cardinality sorting:

MSD sorts from high order
LSD sorts from the low order
Cardinality sort vs count sort vs bucket sort
These three sorting algorithms all use the concept of bucket, but there are obvious differences in the use of bucket:
Cardinality sorting: allocate buckets according to each number of key value
Counting and sorting: only one key value is stored in each bucket
Bucket sorting: each bucket stores a certain range of values

Cardinality sorting JavaScript code implementation:

 1 //LSD Radix Sort
 2 var counter = [];
 3 function radixSort(arr, maxDigit) {
 4     var mod = 10;
 5     var dev = 1;
 6     for (var i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
 7         for(var j = 0; j < arr.length; j++) {
 8             var bucket = parseInt((arr[j] % mod) / dev);
 9             if(counter[bucket]==null) {
10                 counter[bucket] = [];
11             }
12             counter[bucket].push(arr[j]);
13         }
14         var pos = 0;
15         for(var j = 0; j < counter.length; j++) {
16             var value = null;
17             if(counter[j]!=null) {
18                 while ((value = counter[j].shift()) != null) {
19                       arr[pos++] = value;
20                 }
21           }
22         }
23     }
24     return arr;
25 }

Tags: Java Algorithm quick sort

Posted by naitsir on Sat, 07 May 2022 11:08:44 +0300