JavaScript Predefine Function for Array and String:
JavaScript has several predefined functions for arrays that can be quite handy. Here are a few of them:
1. `push()`: Adds one or more elements to the end of an array.
let fruits = ['apple', 'banana'];
fruits.push('orange');
// ['apple', 'banana', 'orange']
2. `pop()`: Removes the last element from an array.
let fruits = ['apple', 'banana', 'orange'];
fruits.pop();
// ['apple', 'banana']
3. `shift()`: Removes the first element from an array.
let fruits = ['apple', 'banana', 'orange'];
fruits.shift();
// ['banana', 'orange']
4. `unshift()`: Adds one or more elements to the beginning of an array.
`
let fruits = ['banana', 'orange'];
fruits.unshift('apple');
// ['apple', 'banana', 'orange']
5. `splice()`: Adds or removes elements from an array.
let fruits = ['apple', 'banana', 'orange'];
// Removing elements
fruits.splice(1, 1); // ['apple', 'orange']
// Adding elements
fruits.splice(1, 0, 'mango'); // ['apple', 'mango', 'orange']
6. `slice()`: Returns a shallow copy of a portion of an array.
let fruits = ['apple', 'banana', 'orange'];
let newFruits = fruits.slice(1, 3); // ['banana', 'orange']
7. `concat()`: Merges two or more arrays.
let fruits = ['apple', 'banana'];
let moreFruits = ['orange', 'mango'];
let allFruits = fruits.concat(moreFruits);
// ['apple', 'banana', 'orange', 'mango']
8. `forEach()`: Executes a provided function once for each array element.
let fruits = ['apple', 'banana', 'orange'];
fruits.forEach(function(fruit) {
console.log(fruit);
});
// 'apple', 'banana', 'orange'
9. `map()`: Creates a new array with the results of calling a provided function on every element in the array.
let numbers = [1, 2, 3];
let doubled = numbers.map(function(number) {
return number * 2;
});
// [2, 4, 6]
10. `filter()`: Creates a new array with all elements that pass the test implemented by the provided function.
let numbers = [1, 2, 3, 4];
let evens = numbers.filter(function(number) {
return number % 2 === 0;
});
// [2, 4]
11) Sort():
The sort() method in JavaScript is used to sort the elements of an array in place and returns the sorted array. By default, it sorts the elements as strings in alphabetical and ascending order. Here's a basic example:
let fruits = ['banana', 'apple', 'orange'];
fruits.sort();
console.log(fruits);
// Output: ['apple', 'banana', 'orange']
To sort numbers correctly, you need to provide a compare function:
let numbers = [10, 2, 3, 4, 5];
numbers.sort(function(a, b) {
return a - b;
});
console.log(numbers);
// Output: [2, 3, 4, 5, 10]
Explanation of the compare function:
a - b sorts the array in ascending order.
b - a sorts the array in descending order.
12) `map()`
The `map()` method creates a new array populated with the results of calling a provided function on every element in the calling array. It's commonly used to transform or modify the elements of an array.
- The `map()` method is ideal for transforming all elements of an array.
array.map(function(currentValue, index, array) {
// Return element for new array
});
```
**Example**:
```javascript
let numbers = [1, 2, 3, 4];
let doubled = numbers.map(function(number) {
return number * 2;
});
console.log(doubled);
// Output: [2, 4, 6, 8]
```
13) `reduce()`
The `reduce()` method executes a reducer function (that you provide) on each element of the array, resulting in a single output value. It's often used for summing values, flattening arrays, or performing other cumulative operations.
The `reduce()` method is perfect for accumulating or aggregating array values into a single result
array.reduce(function(accumulator, currentValue, index, array) {
// Return the updated accumulator
}, initialValue);
```
let numbers = [1, 2, 3, 4];
let sum = numbers.reduce(function(accumulator, number) {
return accumulator + number;
}, 0);
console.log(sum);
// Output: 10
```
String Predefine method:
1. `charAt()`: Returns the character at a specified index.
let str = "Hello, world!";
console.log(str.charAt(1)); // Output: 'e'
```
2. `concat()`: Joins two or more strings.
let str1 = "Hello";
let str2 = "World";
console.log(str1.concat(", ", str2)); // Output: 'Hello, World'
```
3. `includes()`: Checks if a string contains a specified value, returning `true` or `false`.
let str = "Hello, world!";
console.log(str.includes("world")); // Output: true
4. `indexOf()`: Returns the index of the first occurrence of a specified value in a string.
let str = "Hello, world!";
console.log(str.indexOf("world")); // Output: 7
```
5. `replace()`: Replaces a specified value with another value in a string.
let str = "Hello, world!";
let newStr = str.replace("world", "JavaScript");
console.log(newStr); // Output: 'Hello, JavaScript!'
```
6. `slice()`: Extracts a part of a string and returns it as a new string.
let str = "Hello, world!";
let newStr = str.slice(7, 12);
console.log(newStr); // Output: 'world'
```
7. `split()`: Splits a string into an array of substrings based on a specified separator.
let str = "Hello, world!";
let arr = str.split(", ");
console.log(arr); // Output: ['Hello', 'world!']
```
8. `toLowerCase()`: Converts a string to lowercase letters.
let str = "Hello, World!";
console.log(str.toLowerCase()); // Output: 'hello, world!'
```
9. `toUpperCase()`: Converts a string to uppercase letters.
let str = "Hello, World!";
console.log(str.toUpperCase()); // Output: 'HELLO, WORLD!'
```
10. `trim()`: Removes whitespace from both ends of a string.
let str = " Hello, world! ";
console.log(str.trim()); // Output: 'Hello, world!'
What is Quick Sort?
Quick Sort is a highly efficient sorting algorithm and is based on the divide-and-conquer approach. It works by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then sorted recursively.
Steps of Quick Sort
1. Choose a pivot: Pick an element as a pivot from the array. Various strategies can be used for choosing the pivot (e.g., the first element, the last element, the middle element, or a random element).
2. Partitioning: Rearrange the elements in the array such that all elements less than the pivot are moved to its left, and all elements greater than the pivot are moved to its right.
3. Recursively apply the same logic: Apply the above steps recursively to the sub-arrays formed by dividing the pivot element until the base case is reached (array of size 0 or 1).
Implementation in JavaScript
Below is a complete implementation of the Quick Sort algorithm in JavaScript with detailed comments:
function quickSort(arr) {
// Base case: arrays with 0 or 1 element are already sorted
if (arr.length <= 1) {
return arr;
}
// Choose a pivot element (here, we choose the last element)
let pivot = arr[arr.length - 1];
// Arrays to hold elements less than and greater than the pivot
let left = [];
let right = [];
// Partition the array into left and right arrays
for (let i = 0; i < arr.length - 1; i++) {
if (arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
// Recursively apply Quick Sort to left and right sub-arrays, then combine
return [...quickSort(left), pivot, ...quickSort(right)];
}
// Example usage:
let arr = [3, 6, 8, 10, 1, 2, 1];
let sortedArr = quickSort(arr);
console.log(sortedArr);
// Output: [1, 1, 2, 3, 6, 8, 10]
```
Detailed Explanation
1. Base Case: If the array has 0 or 1 elements, it's already sorted, so we return the array as is.
2. Pivot Selection: In this implementation, the pivot is chosen as the last element of the array.
3. Partitioning
- We create two empty arrays: `left` and `right`.
- We iterate over the array (except the pivot) and compare each element to the pivot.
- If the element is less than the pivot, it goes into the `left` array; otherwise, it goes into the `right` array.
4.Recursive Sorting
- We recursively apply the `quickSort` function to the `left` and `right` arrays.
- We concatenate the sorted `left` array, the pivot, and the sorted `right` array to form the final sorted array.
This implementation of Quick Sort has an average time complexity of O(n log n) and a worst-case time complexity of O(n^2) (when the pivot selection is poor, such as always choosing the smallest or largest element in a sorted array).
Bubble sort and Selection Sort:
Certainly! Let's dive into the Bubble Sort and Selection Sort algorithms. Both are simple and intuitive sorting algorithms, but they differ in their approach and efficiency.
Bubble Sort
Bubble Sort is a straightforward comparison-based sorting algorithm. It repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted.
Steps of Bubble Sort
1. Compare each pair of adjacent elements.
2. If the elements are in the wrong order, swap them.
3. Repeat the process for the next pair of elements.
4. Continue this until the list is sorted.
Example in JavaScript
function bubbleSort(arr) {
let n = arr.length;
for (let i = 0; i < n - 1; i++) {
for (let j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// Swap arr[j] and arr[j + 1]
let temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
return arr;
}
// Example usage:
let arr = [64, 34, 25, 12, 22, 11, 90];
console.log(bubbleSort(arr));
// Output: [11, 12, 22, 25, 34, 64, 90]
```
Selection Sort
Selection Sort is another simple comparison-based sorting algorithm. It divides the input list into two parts: the sorted part at the left end and the unsorted part at the right end. It repeatedly selects the smallest (or largest, depending on the order) element from the unsorted part and swaps it with the first element of the unsorted part.
Steps of Selection Sort
1. Find the smallest element in the unsorted part.
2. Swap it with the first element of the unsorted part.
3. Move the boundary between the sorted and unsorted parts one element to the right.
4. Repeat the process until the entire list is sorted.
Example in JavaScript
function selectionSort(arr) {
let n = arr.length;
for (let i = 0; i < n - 1; i++) {
// Find the minimum element in the unsorted part
let minIndex = i;
for (let j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// Swap the found minimum element with the first element of the unsorted part
let temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
return arr;
}
// Example usage:
let arr = [64, 34, 25, 12, 22, 11, 90];
console.log(selectionSort(arr));
// Output: [11, 12, 22, 25, 34, 64, 90]
Bubble Sort
- Simple to implement.
- Works well with small lists.
- Time Complexity: O(n^2) in worst and average cases.
- Space Complexity: O(1)
Selection Sort
- Also simple to implement.
- Always performs the same number of comparisons.
- Time Complexity: O(n^2) in worst and average cases.
- Space Complexity: O(1).
POST Answer of Questions and ASK to Doubt