Searching in Arrays
Searching is one of the most common operations performed in an array. The search can be used to return the position of the element or check if it exists in the array.
There are several searching algorithms. The most commonly used among them are:
Linear Search
Binary Search
Ternary Search
Linear Search
The simplest search to be done on an array is the linear search.This search starts from first to end of the array and keeps iterating untill the element is found.
function linearSearch(array, target) {
for (let i = 0; i < array.length; i++) {
if (array[i] === target) {
return i; // Return the index of the target element
}
}
return -1; // Return -1 if the target element is not found
}
// Example usage
const numbers = [4, 2, 8, 5, 1, 9, 3];
const targetNumber = 5;
const index = linearSearch(numbers, targetNumber);
if (index !== -1) {
console.log(`Found ${targetNumber} at index ${index}`);
} else {
console.log(`${targetNumber} not found in the array`);
}
In this example, we have a function called linearSearch that takes two parameters: an array to search (array) and the target value to find (target). The function iterates over each element in the array using a for loop and checks if the current element matches the target value. If a match is found, the function returns the index of the element. If no match is found after traversing the entire array, the function returns -1.
Best use case
This search is best used when the list of elements is unsorted and the search is to be performed only once. It is also preferred for list to be small, as the time taken grows with the size of the data.
Binary Search
The linear search approach has one disadvantage. Finding elements in a large array will be time consuming. As the array grows, the time will increase linearly. A binary search can be used as a solution to this problem in some cases.
Binary search is an efficient searching algorithm that works on sorted arrays. It repeatedly divides the search space in half until the target value is found or determined to be absent.
function binarySearch(array, target) {
let left = 0;
let right = array.length - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (array[mid] === target) {
return mid; // Return the index of the target element
} else if (array[mid] < target) {
left = mid + 1; // Continue searching in the right half
} else {
right = mid - 1; // Continue searching in the left half
}
}
return -1; // Return -1 if the target element is not found
}
// Example usage
const numbers = [1, 2, 3, 4, 5, 8, 9];
const targetNumber = 5;
const index = binarySearch(numbers, targetNumber);
if (index !== -1) {
console.log(`Found ${targetNumber} at index ${index}`);
} else {
console.log(`${targetNumber} not found in the array`);
}
In this example, we have a function called binarySearch that takes two parameters: a sorted array to search (array) and the target value to find (target). The function initializes two pointers, left and right, which represent the left and right boundaries of the search space. Inside a while loop, the function calculates the middle index (mid) by taking the average of left and right. It then compares the element at the middle index with the target value.
If the middle element is equal to the target value, the function returns the middle index.
If the middle element is less than the target value, it means the target value is in the right half of the search space. The function updates
leftto bemid + 1to continue searching in the right half.If the middle element is greater than the target value, it means the target value is in the left half of the search space. The function updates
rightto bemid - 1to continue searching in the left half.
The process continues until either the target value is found, in which case the function returns its index, or the search space is exhausted, in which case the function returns -1 to indicate that the target value is not present in the array.
Best use case
This search is best used when the list of elements is already sorted (not always feasible, especially when new elements are frequently being inserted). The list to be searched can be very large without much decrease in searching time, due to the logarithmic time complexity of the algorithm.
Ternary Search
The basic idea behind ternary search is to divide the interval into three equal parts and determine which part the maximum or minimum value lies in. Here's the step-by-step process:
First, we compare the key with the element at mid1. If found equal, we return mid1.
If not, then we compare the key with the element at mid2. If found equal, we return mid2.
If not, then we check whether the key is less than the element at mid1. If yes, then recur to the first part.
If not, then we check whether the key is greater than the element at mid2. If yes, then recur to the third part.
If not, then we recur to the second (middle) part.
function ternarySearch(arr, target) {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
const partitionSize = Math.floor((right - left) / 3);
const mid1 = left + partitionSize;
const mid2 = right - partitionSize;
if (arr[mid1] === target) {
return mid1;
}
if (arr[mid2] === target) {
return mid2;
}
if (target < arr[mid1]) {
right = mid1 - 1;
} else if (target > arr[mid2]) {
left = mid2 + 1;
} else {
left = mid1 + 1;
right = mid2 - 1;
}
}
return -1; // Target value not found
}
// Example usage:
const array = [1, 3, 5, 7, 9, 11, 13, 15, 17];
const targetValue = 11;
const index = ternarySearch(array, targetValue);
if (index !== -1) {
console.log(`Target value found at index ${index}`);
} else {
console.log("Target value not found");
}
In this example, the ternarySearch function takes an array (arr) and a target value (target) as input and returns the index of the target value in the array. If the target value is not found, it returns -1.
The algorithm starts with two pointers, left and right, which represent the boundaries of the subarray being searched. The algorithm then calculates two midpoints (mid1 and mid2) that divide the subarray into three equal-sized parts.
The algorithm compares the target value with the values at mid1 and mid2. If the target value is found at either of these positions, the function returns the corresponding index.
If the target value is smaller than the value at mid1, the search is narrowed down to the left part of the array. If the target value is larger than the value at mid2, the search is narrowed down to the right part of the array. Otherwise, the target value must be within the middle part, so the search range is updated accordingly.
Sorting in Arrays
Sorting in arrays refers to the process of rearranging the elements in an array in a specific order, typically in ascending or descending order. Sorting is a fundamental operation in computer science and is used to organize data in a structured manner, making it easier to search, analyze, and perform various operations on the data.
Various algorithms have been designed that sort the array using different methods. Some of these sorts are more useful than the others in certain situations.
There are various sorting algorithms available.he most commonly used among them are:
Bubble Sort
Selection Sort
Insertion Sort
Merge Sort
Quick Sort
Bubble Sort:
Bubble sort is a simple sorting algorithm that repeatedly steps through the array, compares adjacent elements, and swaps them if they are in the wrong order. The process is repeated until the array is fully sorted.Like-
Here's an explanation of bubble sort in JavaScript:
function bubbleSort(array) {
const length = array.length;
for (let i = 0; i < length - 1; i++) {
for (let j = 0; j < length - 1 - i; j++) {
// Compare adjacent elements
if (array[j] > array[j + 1]) {
// Swap elements if they are in the wrong order
const temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
}
return array;
}
// Example usage
const numbers = [4, 2, 8, 5, 1, 9, 3];
const sortedNumbers = bubbleSort(numbers);
console.log(sortedNumbers); // Output: [1, 2, 3, 4, 5, 8, 9]
In this example, we have a function called bubbleSort that takes an array as a parameter. The function uses two nested for loops to iterate through the array. The outer loop runs length - 1 times, where length is the length of the array. This ensures that after each iteration, the largest element "bubbles" up to the end of the array.
The inner loop compares adjacent elements by using the index j and j + 1. If the current element is greater than the next element, a swap is performed using a temporary variable. This places the larger element towards the end of the array.
By the end of each iteration of the outer loop, the largest unsorted element is pushed to the end of the array. This process repeats until the array is fully sorted, with the largest elements gradually moving to the rightmost positions.
Best use case
This is a very elementary sort which is easy to understand and implement. It is not recommended in actual production environments. No external memory is required to sort as it is an in-place sort.
Insertion Sort
Insertion sort is a simple sorting algorithm that builds the final sorted array one element at a time. It iterates through the array, considering one element at a time and inserting it into its correct position within the already sorted portion of the array.
If we want to understand insertion sort, we must be need to see one example:
Let's say we have the following array of numbers: [4, 2, 8, 5, 1, 9, 3]. We want to sort this array in ascending order using the insertion sort algorithm.
Step 1: Start with the second number, which is 2.
Step 2: Compare 2 with the number to its left, which is 4. Since 4 is greater than 2, we shift 4 to the right and 2 to the left
Step 3: The array now becomes [2, 4, 8, 5, 1, 9, 3].
Step 4: Move on to the next unsorted number, which is 8.
Step 5: Compare 8 with the number to its left, which is 4. Since 4 is not greater than 8, we stop comparing and insert the picked number, 8, in its correct position.
Step 6: The array now becomes [2, 4, 8, 5, 1, 9, 3].
Steps 7:Move on to the next unsorted number, which is 5.then we do step 2 again.
exaplanation fo insertion sort in js
function insertionSort(array) {
const length = array.length;
for (let i = 1; i < length; i++) {
const key = array[i];
let j = i - 1;
// Move elements greater than the key to the right
while (j >= 0 && array[j] > key) {
array[j + 1] = array[j];
j--;
}
// Insert the key in its correct position
array[j + 1] = key;
}
return array;
}
// Example usage
const numbers = [4, 2, 8, 5, 1, 9, 3];
const sortedNumbers = insertionSort(numbers);
console.log(sortedNumbers); // Output: [1, 2, 3, 4, 5, 8, 9]
Best use case
Although this is a elementary sort with the worst case of O(n^2), it performs much better when the array is nearly sorted, as lesser elements would have to be moved. It is also preferred when the number of elements are less as it has significantly less overhead than the other sorts. It consumes less memory and is simpler to implement.
In some quick sort implementations, insertion sort is internally to sort the smaller lists faster.
Selection Sort
Selection sort is a simple sorting algorithm that repeatedly selects the smallest (or largest) element from an unsorted portion of the array and swaps it with the element at the beginning of the unsorted portion
Here's an example using numbers to illustrate the process:
Let's say we have the following array of numbers: [4, 2, 8, 5, 1, 9, 3]. We want to sort this array in ascending order using the selection sort algorithm.
First we need to divide tow part of array, one is sorted and another is unsorted.
Find the smallest element in the unsorted portion, which is 1.
Swap 1 with the first element in the unsorted portion (4).swap 1 to 4 and swap 4 to 1.he arrays becomes [1, 2, 8, 5, 4, 9, 3].
Move the boundary of the sorted portion one position to the right. Now, the sorted portion is [1].
Continue this process until the entire array is sorted.
function selectionSort(array) {
const length = array.length;
for (let i = 0; i < length - 1; i++) {
let minIndex = i;
// Find the index of the smallest element in the unsorted portion
for (let j = i + 1; j < length; j++) {
if (array[j] < array[minIndex]) {
minIndex = j;
}
}
// Swap the smallest element with the first element in the unsorted portion
if (minIndex !== i) {
const temp = array[i];
array[i] = array[minIndex];
array[minIndex] = temp;
}
}
return array;
}
// Example usage
const numbers = [4, 2, 8, 5, 1, 9, 3];
const sortedNumbers = selectionSort(numbers);
console.log(sortedNumbers); // Output: [1, 2, 3, 4, 5, 8, 9]
In this example, we define a function called selectionSort that takes an array as a parameter. The function iterates through the array using a for loop, selecting the smallest element in the unsorted portion and swapping it with the first element in that portion.
The outer loop runs from the first element to the second-to-last element because the last element will automatically be in its correct position once all other elements are sorted.
Inside the outer loop, we have an inner loop that starts from i + 1, where i is the current position of the outer loop. This loop finds the index of the smallest element in the unsorted portion by comparing each element with the current minimum element.
After finding the index of the smallest element, we perform a swap with the first element in the unsorted portion if the smallest element is not already at that position.
Best use case
This sort is not influenced by the initial ordering of elements in the array and can be sued to efficiently sort small lists. It performs the least amount of data movement amongst all sorts, therefore it could be used where data manipulation is costly.
Merge Sort
In simple terms, we can say that the process of merge sort is to divide the array into two halves, sort each half, and then merge the sorted halves back together. This process is repeated until the entire array is sorted.
Divide: The first step is to divide the array into smaller sub-arrays recursively.
Split the array
[5, 3, 1, 6, 2, 9]into two halves:Left sub-array:
[5, 3, 1]Right sub-array:
[6, 2, 9]
Continue dividing each sub-array into halves until each sub-array has only one element:
Divide the left sub-array further:
Left sub-array:
[5]Right sub-array:
[3, 1]Continue dividing the right sub-array:
Left sub-array:
[3]Right sub-array:
[1]
Divide the right sub-array further:
Left sub-array:
[6]Right sub-array:
[2, 9]Continue dividing the right sub-array:
Left sub-array:
[2]Right sub-array:
[9]
Merge: The next step is to merge the divided sub-arrays back together while maintaining the sorted order.
Merge the two single-element sub-arrays:
[5]and[3]:Compare the first elements of each sub-array.
Take the smaller element,
3, and move it to a new merged array.Move to the next element in the sub-array from which the element was selected (
[3]).Compare the next element,
5, with the element in the other sub-array ([1]).Take the smaller element,
5, and move it to the merged array.Continue this process until all elements are merged.
The merged sub-array becomes
[3, 5].
Merge the single-element sub-array
[1]with the merged sub-array[3, 5]:Compare the first elements of each sub-array.
Take the smaller element,
1, and move it to the merged array.Move to the next element in the sub-array from which the element was selected (
[1]).The merged sub-array becomes
[1, 3, 5].
Merge the two single-element sub-arrays:
[6]and[2]:Compare the first elements of each sub-array.
Take the smaller element,
2, and move it to a new merged array.Move to the next element in the sub-array from which the element was selected (
[2]).Compare the next element,
6, with the element in the other sub-array ([9]).Take the smaller element,
6, and move it to the merged array.Continue this process until all elements are merged.
The merged sub-array becomes
[2, 6].
Merge the single-element sub-array
[9]with the merged sub-array[2, 6]:Compare the first elements of each sub-array.
Take the smaller element,
9, and move it to the merged array.Move to the next element in the sub-array from which the elem
function mergeSort(arr) {
if (arr.length <= 1) {
return arr; // Base case: an array with 0 or 1 element is already sorted
}
const mid = Math.floor(arr.length / 2); // Find the middle index of the array
const left = arr.slice(0, mid); // Divide the array into two halves
const right = arr.slice(mid);
return merge(mergeSort(left), mergeSort(right)); // Recursively merge and sort the divided sub-arrays
}
function merge(left, right) {
let result = [];
let i = 0;
let j = 0;
while (i < left.length && j < right.length) {
if (left[i] <= right[j]) {
result.push(left[i]);
i++;
} else {
result.push(right[j]);
j++;
}
}
// Push the remaining elements of the left and right sub-arrays, if any
while (i < left.length) {
result.push(left[i]);
i++;
}
while (j < right.length) {
result.push(right[j]);
j++;
}
return result;
}
// Example usage:
const array = [5, 3, 1, 6, 2, 9];
const sortedArray = mergeSort(array);
console.log(sortedArray);
In this implementation, the mergeSort function takes an array arr as input and returns the sorted array. The base case checks if the array has 0 or 1 element, in which case it is already considered sorted and is returned.
If the array has more than one element, the function finds the middle index of the array and divides it into two halves using the slice method.
The function then recursively calls itself to apply the Merge Sort algorithm on the left and right sub-arrays. The results are passed to the merge function to merge and sort the divided sub-arrays.
The merge function takes two sorted arrays, left and right, and merges them into a single sorted array. It uses two pointers, i and j, to iterate over the elements of the left and right sub-arrays, comparing them and pushing the smaller element to the result array. Once one sub-array is fully iterated, the remaining elements from the other sub-array are appended to the result array.
Quick Sort
QuickSort is a popular sorting algorithm that follows 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 recursively sorted.
Choose a pivot element: In QuickSort, we typically choose the last element of the array as the pivot. In this case, the pivot is
9.Partition the array: Reorder the elements in the array so that all elements smaller than the pivot come before the pivot, and all elements greater than the pivot come after it. We start by initializing two empty arrays,
leftandright, to hold the smaller and greater elements, respectively.Compare each element (except the pivot) with the pivot:
5 < 9, so we push5to theleftarray.3 < 9, so we push3to theleftarray.1 < 9, so we push1to theleftarray.6 >= 9, so we push6to therightarray.2 < 9, so we push2to theleftarray.
The array becomes
[5, 3, 1, 6, 2](elements are not yet in their final sorted positions).
Recursively apply QuickSort: Now, we recursively apply the QuickSort algorithm to the
leftandrightsub-arrays.QuickSort on the
leftsub-array[5, 3, 1, 2]:Choose the last element,
2, as the pivot.Partition the array:
5 >= 2, so we push5to therightarray.3 >= 2, so we push3to therightarray.1 < 2, so we push1to theleftarray.
Recursively apply QuickSort:
QuickSort on the
leftsub-array[1]returns[1].QuickSort on the
rightsub-array[5, 3]:Choose the last element,
3, as the pivot.Partition the array:
5 >= 3, so we push5to therightarray.
Recursively apply QuickSort:
QuickSort on the
leftsub-array[]returns[].QuickSort on the
rightsub-array[5]returns[5].
The
leftsub-array becomes[1], the pivot is[2], and therightsub-array becomes[5].
The
leftsub-array becomes[1, 2, 3, 5], the pivot is[6], and therightsub-array becomes[].
Combine the results: Finally, combine the sorted
leftsub-array, the pivot, and the sortedrightsub-array to obtain the sorted array.The sorted
leftsub-array is[1, 2, 3, 5].The pivot is
[6].The sorted
rightsub-array is[].Concatenating them, we get the sorted array
[1, 2, 3, 5, 6, 9].
That's it! The array [5, 3, 1, 6, 2, 9] is sorted using the Quick
function quickSort(arr) {
if (arr.length <= 1) {
return arr; // Base case: an array with 0 or 1 element is already sorted
}
const pivot = arr[arr.length - 1]; // Choose the last element as the pivot
const left = [];
const right = [];
for (let i = 0; i < arr.length - 1; i++) {
if (arr[i] < pivot) {
left.push(arr[i]); // Elements smaller than the pivot go to the left array
} else {
right.push(arr[i]); // Elements greater than or equal to the pivot go to the right array
}
}
return [...quickSort(left), pivot, ...quickSort(right)]; // Recursively sort the left and right sub-arrays
}
// Example usage:
const array = [5, 3, 1, 6, 2, 9];
const sortedArray = quickSort(array);
console.log(sortedArray);
In this implementation, the quickSort function takes an array arr as input and returns the sorted array. The base case checks if the array has 0 or 1 element, in which case it is already considered sorted and is returned.
If the array has more than one element, the function selects the last element as the pivot and creates two empty arrays, left and right, to hold elements smaller and greater than the pivot, respectively.
The for loop iterates over all elements except the pivot, comparing them with the pivot. Elements smaller than the pivot are pushed into the left array, while elements greater than or equal to the pivot are pushed into the right array.
Finally, the function recursively calls itself to sort the left and right sub-arrays. The sorted left array, followed by the pivot, and then the sorted right array are concatenated using the spread operator (...) and returned as the sorted array.Se