A brief intro about sorting algorithms
"Sorting is like tidying up your room, but for data! In this article, we'll explore different ways to neatly organize information. From basic methods like putting numbers in order to more clever ways that work faster with big lists. We'll learn how each method works, see when they're great, and how they're used in real life. By the end, you'll know all about these sorting tricks and how they can help tidy up information for all kinds of tasks!"
Bubble Sort Algorithm 🛁
Introduction
The bubble sort algorithm is a foundational sorting technique for arranging elements in ascending or descending order within an array. While less efficient for larger datasets, it provides a clear understanding of basic sorting mechanisms.
Algorithm Overview
- Compare adjacent elements in the array.
- Swap them if they are in the wrong order.
- Repeat this process for the entire array until no more swaps are needed.
TypeScript Implementation
Brute Force Solution
export default function bubbleSortBruteForce(nums: number[]): number[] {
const length: number = nums.length;
for (let row: number = 0; row < length - 1; row++) {
for (let col: number = 0; col < length - row - 1; col++) {
if (nums[col] > nums[col + 1]) {
[nums[col], nums[col + 1]] = [nums[col + 1], nums[col]];
}
}
}
return nums;
}
const nums: number[] = [2, 41, 4, 1, 7];
bubbleSortBruteForce(nums.slice()); // 🔄 Using slice to avoid modifying the original array
Complexity Analysis
- Best Case: O(n) - When the array is already sorted.
- Average Case: O(n^2) - For random arrays.
- Worst Case: O(n^2) - When the array is sorted in reverse order.
Optimal Solution
export default function bubbleSortOptimal(nums: number[]): number[] {
const length: number = nums.length;
let swapped: boolean;
for (let row: number = 0; row < length - 1; row++) {
swapped = false;
for (let col: number = 0; col < length - row - 1; col++) {
if (nums[col] > nums[col + 1]) {
[nums[col], nums[col + 1]] = [nums[col + 1], nums[col]];
swapped = true;
}
}
if (!swapped) break;
}
return nums;
}
const nums: number[] = [2, 41, 4, 1, 7];
bubbleSortOptimal(nums.slice()); // 🔄 Using slice to avoid modifying the original array
Important Note:
Here, I'm using the slice method on the nums array. This lets me work with a copy of the data instead of the original data.
In this code snippet, I'm emphasizing the use of strict types, even though some types are inferred from their initial values. Explicitly defining types, even when inferred, enhances readability, consistency, and documentation within the code.
- Clarity: Assigning explicit types makes code easier to understand.
- Consistency: It ensures uniformity and simplifies future modifications.
- Documentation: Helps clarify variable usage and intentions for better comprehension.
When dealing with real-world data in data structures, algorithms, or any data-related tasks, it's better not to change the original data directly. Instead, it's best practice to create a duplicate or copy of the data and perform modifications on the copied version while keeping the original dataset unchanged.
Selection Sort Algorithm 🎯
Introduction
The selection sort algorithm is a comparison-based sorting technique used to arrange elements within an array. While straightforward, it's less efficient for larger datasets but offers a fundamental understanding of sorting.
Algorithm Overview
- Start by dividing the array into sorted and unsorted portions.
- Find the smallest element from the unsorted portion and place it at the end of the sorted portion.
- Repeat this process until the entire array is sorted.
TypeScript Implementation
export function selectionSort(nums: number[]): number[] {
const length: number = nums.length;
for (let row: number = 0; row < length - 1; row++) {
let minIdx: number = row;
for (let col: number = row + 1; col < length; col++) {
if (nums[col] < nums[minIdx]) {
minIdx = col;
}
}
if (minIdx !== row) {
[nums[row], nums[minIdx]] = [nums[minIdx], nums[row]];
}
}
return nums;
}
const nums: number[] = [2, 41, 4, 1, 7];
console.log(selectionSort(nums.slice())); // Using slice to avoid modifying the original array
Complexity Analysis
- Best Case: O(n^2) - When the array is already sorted.
- Average Case: O(n^2) - For random arrays.
- Worst Case: O(n^2) - When the array is sorted in reverse order.
Insertion Sort Algorithm 📥
Introduction
The insertion sort algorithm is another comparison-based sorting technique used to arrange elements within an array. It's particularly efficient for small datasets and nearly sorted arrays due to its simplicity.
Algorithm Overview
- Start with the second element and consider it as a sorted sequence.
- Iterate through the unsorted elements, one at a time.
- For each element, compare it with the elements in the sorted sequence and insert it into the correct position.
TypeScript Implementation
export function insertionSort(nums: number[]): number[] {
const length: number = nums.length;
for (let row: number = 1; row < length; row++) {
const currentElement: number = nums[row];
let col: number = row - 1;
while (col >= 0 && nums[col] > currentElement) {
nums[col + 1] = nums[col];
col--;
}
nums[col + 1] = currentElement;
}
return nums;
}
const nums: number[] = [2, 41, 4, 1, 7];
console.log(insertionSort(nums.slice())); // 🔄 Using slice to avoid modifying the original array
Complexity Analysis
- Best Case: O(n) - When the array is nearly sorted.
- Average Case: O(n^2) - For random arrays.
- Worst Case: O(n^2) - When the array is sorted in reverse order.
The Insertion Sort algorithm's efficiency lies in its ability to efficiently sort small datasets or partially sorted arrays. It's an in-place sorting algorithm that operates directly on the array by shifting elements and inserting them into their correct positions.
Merge Sort Algorithm 🔄
Introduction
The merge sort algorithm is an efficient, comparison-based sorting technique that follows the divide-and-conquer strategy to sort elements within an array. It offers better performance compared to other sorting algorithms for larger datasets.
Algorithm Overview
- Divide the array into smaller subarrays until each subarray contains only one element.
- Merge adjacent subarrays while sorting elements to create larger sorted subarrays.
- Continue merging and sorting until a single sorted array remains.
TypeScript Implementation
Recursive Approach
export default function mergeSort(nums: number[]): number[] {
if (nums.length <= 1) {
return nums;
}
const mid: number = Math.floor(nums.length / 2);
const left: number[] = nums.slice(0, mid);
const right: number[] = nums.slice(mid);
const sortedLeft: number[] = mergeSort(left);
const sortedRight: number[] = mergeSort(right);
return merge(sortedLeft, sortedRight);
}
function merge(nums1: number[], nums2: number[]): number[] {
let [leftIdx, rightIdx]: [number, number] = [0, 0];
const result: number[] = [];
while (leftIdx < nums1.length && rightIdx < nums2.length) {
if (nums1[leftIdx] < nums2[rightIdx]) {
result.push(nums1[leftIdx]);
leftIdx++;
} else {
result.push(nums2[rightIdx]);
rightIdx++;
}
}
/*
* After the loop, one of the arrays might still have elements remaining.
* You can append the remaining elements directly without additional checks.
*/
return result.concat(nums1.slice(leftIdx), nums2.slice(rightIdx));
}
const nums: number[] = [2, 41, 4, 1, 7];
console.log(mergeSort(nums.slice())); // 🔄 Using slice to avoid modifying the original array
Complexity Analysis
- Best Case: O(n log n) - Achieved when the array is nearly sorted.
- Average Case: O(n log n) - For random arrays.
- Worst Case: O(n log n) - Regardless of the input data.
Quick Sort Algorithm ⚡
Introduction
The Quick Sort algorithm is a highly efficient comparison-based sorting technique used to rearrange elements within an array. Leveraging the concept of partitioning, Quick Sort offers better performance compared to other sorting algorithms.
Algorithm Overview
- Choose an element as the pivot from the array.
- Rearrange the elements in such a way that elements less than the pivot are moved to the left, and elements greater than the pivot are moved to the right.
- Recursively apply the above steps to the sub-arrays created by partitioning until the entire array is sorted.
TypeScript Implementation
export default function quickSort(nums: number[]): number[] {
if (nums.length <= 1) {
return nums;
}
const pivot: number = nums[0];
const left: number[] = [];
const right: number[] = [];
for (const num of nums.slice(1)) {
if (num < pivot) {
left.push(num);
} else {
right.push(num);
}
}
return [...quickSort(left), pivot, ...quickSort(right)];
}
const nums: number[] = [2, 41, 4, 1, 7];
console.log(quickSort(nums.slice())); // 🔄 Using slice to avoid modifying the original array
Complexity Analysis
- Best Case: O(n log n) - When the pivot chosen splits the array into nearly equal halves.
- Average Case: O(n log n) - For random arrays.
- Worst Case: O(n^2) - When the pivot is the smallest or largest element in every partition.
You can find all the code samples here
Conclusion
Understanding these sorting algorithms is crucial for developers when selecting the appropriate method for various scenarios. The bubble sort, while straightforward, works well for smaller datasets, providing a fundamental sorting mechanism. In contrast, quick sort excels in efficiently handling larger arrays, offering a faster sorting approach. Depending on your specific use case, you can leverage these algorithms to organize and optimize your code.
Thank you for reading this far; your support means a lot! If you have any questions, please don't hesitate to ask in the comments. Don't forget to like and share the article – your appreciation is highly valued. Your feedback and suggestions are also more than welcome. 🙏👍😊
To see visualizations of how these algorithms operate, you can explore the website at https://visualgo.net/en/sorting.
Top comments (0)