An introduction to sorting and searching
What is sorting and searching?
- Sort: To change an out-of-order array into an ascending or descending array
- Search: Find the index of an element in an array
JS for sorting and searching
- Sort in JS: the array sort method
- JS search: array indexOf method
Sorting algorithm
- Bubble sort (inefficient)
- Selection sort (inefficient)
- Insertion sort (inefficient)
- Merge sort (efficient for work)
- Quicksort (efficient enough to work with)
- .
Search algorithm
- Sequential search (performance O(n))
- Binary search (performance O(logN))
- .
Bubble sort
Bubble sort idea
- Compare all adjacent elements and swap them if the first is larger than the second
- I’m going to make sure that the last number is going to be the largest
- After n-1 rounds, the sort is complete
Can be viewed through animation: visualgo.net/zh/sorting
Code implementation
Array.prototype.bubbleSort = function(){
for(let i = 0; i <this.length - 1; i++){for(let j = 0; j <this.length - 1 - i; j++){
let tmp;
if(this[j] > this[j+1]){
tmp = this[j];
this[j] = this[j+1];
this[j+1] = tmp; }}}};const arr = [2.3.45.23.3.4.2];
arr.bubbleSort();
Copy the codeTwo nested loops, time complexity: O(n*n)
Selection sort
- Find the smallest value in the array, select it and place it first
- Then find the second smallest value, select it and place it in second place
- And so on, for n-1 rounds
Can be viewed through animation: visualgo.net/zh/sorting
Code implementation
Array.prototype.selectionSort = function(){
for(let i = 0; i < this.length -1; i++){
let indexMin = i;
for(let j = i+1; j < this.length; j++){
if(this[j] < this[indexMin]){ indexMin = j; }}let tmp = this[i];
this[i] = this[indexMin];
this[indexMin] = tmp; }};const arr = [1.7.7.7.7.7.3.3.3.212.2.3.45.23.3.4.2];
arr.selectionSort();
console.log(arr)
Copy the codeTwo nested loops, time complexity: O(n*n)
Insertion sort
- Start with the second number and go forward
- If you’re bigger than that, go to the back
- And so on to the last number
This can be achieved by animation viewing:visualgo.net/zh/sorting
Code implementation
Array.prototype.insertionSort = function(){
for(let i = 1; i <this.length; i++){
for(let j = i; j > 0; j--){
if(this[j]<this[j-1]) {let temp = this[j];
this[j] = this[j-1];
this[j-1] = temp; }}}};const arr = [1.7.7.7.5.3.3.212.2.3.45.23.3.4.2];
arr.insertionSort();
console.log(arr)
Copy the codeTwo nested loops, time complexity: O(n*n)
Time complexity of merge sort
- Splitting: Splitting an array in half and recursively “splitting” the subarrays until they are separated into separate numbers
- Merge: Merge two numbers into an ordered array, and then merge the ordered array until all subarrays are merged into a complete array
- Create an empty array res to hold the final sorted array
- Compare the headers of two ordered arrays, with the smaller one off the queue and pushed into the RES
- If both arrays still have values, repeat step 2
This can be achieved by animation viewing:visualgo.net/zh/sorting
Array.prototype.mergeSort = function(){
const rec = (arr) = >{
if(arr.length <= 1) {returnarr ; }const mid = Math.floor(arr.length/2);
const left = arr.slice(0,mid);
const right = arr.slice(mid,arr.length);
const orderLeft = rec(left);
const orderRight = rec(right);
const res = [];
while(orderLeft.length || orderRight.length){
if(orderLeft.length && orderRight.length){
res.push(orderLeft[0] < orderRight[0]? orderLeft.shift():orderRight.shift()) }else if(orderLeft.length){
res.push(orderLeft.shift());
}else if(orderRight.length){
res.push(orderRight.shift())
}
}
return res;
}
const res = rec(this);
res.forEach((n,i) = > {this[i] = n; }); };const arr = [2.5.4.3.1];
arr.mergeSort();
console.log(arr)
Copy the code- Order logN in minutes.
- The time of the combination is O(n).
- Total time complexity: O(n*logN)
21 LeetCode subject
The answer can refer to the official problem
Answer key:
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode prehead = new ListNode(-1);
ListNode prev = prehead;
while(l1 ! =null&& l2 ! =null) {
if (l1.val <= l2.val) {
prev.next = l1;
l1 = l1.next;
} else {
prev.next = l2;
l2 = l2.next;
}
prev = prev.next;
}
// At most, only one of the two lists has not been merged
prev.next = l1 == null ? l2 : l1;
returnprehead.next; }}Copy the codeQuick sort idea
- Partition: Select an arbitrary “baseline” from the array. All elements smaller than the baseline are placed before the baseline and all elements larger than the baseline are placed after the baseline
- Recursion: Recursively partition subarrays before and after the base
This can be achieved by animation viewing:visualgo.net/zh/sorting
Array.prototype.quickSort = function(){
const rec = (arr) = >{
if(arr.length <= 1) {returnarr; }const left = [];
const right = [];
const mid = arr[0];
for(let i = 1; i < arr.length; i++){
if(arr[i] < mid){
left.push(arr[i]);
}else{ right.push(arr[i]); }}return [...rec(left),mid,...rec(right)];
}
const res = rec(this);
res.forEach((n,i) = > {
this[i] = n; })};const arr = [1.7.7.7.5.3.3.212.2.3.45.23.3.4.2];
arr.quickSort();
console.log(arr)
Copy the code- The recursion is order logN.
- The time complexity of the partition operation is O(n)
- Total time complexity: O(n*logN)
Sequential search
- Through the array
- If we find an element equal to the target, we return its index
- At the end of the walk, if no target value has been found, -1 is returned
Array.prototype.sequentialSearch = function(item){
for(let i = 0; i < this.length; i++){
if(this[i] === item){
returni; }}return -1;
};
const arr = [2.5.4.3.1];
arr.sequentialSearch(3);
console.log(arr.sequentialSearch(1))
Copy the code- Traversing the array is a loop operation
- Time complexity: O(n)
Binary search
- Start with the middle element of the array, and if that middle element happens to be the target value, the search ends
- If the target value is greater or less than the middle element, the half of the array that is greater or less than the middle element is searched
- This is a sorted array
Array.prototype.binarySearch = function(item){
let low = 0;
let high = this.length - 1;
while(low <= high){
const mid = Math.floor((low + high) / 2);
const element = this[mid];
if(element < item){
low = mid + 1;
}else if(element > item){
high = mid - 1;
}else{
returnmid; }}return -1;
};
const arr = [1.2.3.4.5];
arr.binarySearch(3);
console.log(arr.binarySearch(4))
Copy the code- Each comparison makes half the search area searched
- Time complexity: O(logN)
LeetCode question 374
/**
* Forward declaration of guess API.
* @param {number} num your guess
* @return -1 if num is lower than the guess number
* 1 if num is higher than the guess number
* otherwise return 0
* var guess = function(num) {}
*/
/ * * *@param {number} n
* @return {number}* /
var guessNumber = function(n) {
let left = 1, right = n;
while (left < right) { // Loop until the left and right ends of the interval are the same
const mid = Math.floor((left + right ) / 2);
if (guess(mid) <= 0) {
right = mid; // The answer is in the interval [left, mid]
} else {
left = mid + 1; // The answer is in the interval [mid+1, right]}}Left == right
return left;
};
Copy the code