Welcome to the practice-based lesson dedicated to Simple Sorting Algorithms. Sorting is one of the most investigated classes of algorithms in computer science. Understanding different methods of sorting becomes increasingly crucial as data size increases. In this lesson, we are going to revisit the basic sorting algorithms: Bubble, Selection, and Insertion sorts. These are not only excellent exercises for those new to coding, but they also lay the groundwork for more complex sorting algorithms like QuickSort.
Before we dive into the basics, let's peek into more complex territory by examining QuickSort, a popular divide-and-conquer sorting algorithm. The idea behind it is to pick a pivot element from the array and partition the other elements into two arrays according to whether they are less than or greater than the pivot. The pivot is then placed in its correct sorted position between the two subarrays. This process is recursively applied to each of the two arrays around the pivot, leading to a sorted array.
Here's how you can implement QuickSort in C#:
C#1using System; 2 3public class Solution 4{ 5 public static void QuickSort(int[] arr, int low, int high) 6 { 7 if (low < high) 8 { 9 int pi = Partition(arr, low, high); 10 11 // Recursively sort elements before partition and after partition 12 QuickSort(arr, low, pi - 1); 13 QuickSort(arr, pi + 1, high); 14 } 15 } 16 17 private static int Partition(int[] arr, int low, int high) 18 { 19 int pivot = arr[high]; 20 int i = (low - 1); // Index of smaller element 21 for (int j = low; j < high; j++) 22 { 23 // If current element is smaller than or equal to pivot 24 if (arr[j] <= pivot) 25 { 26 i++; 27 28 // Swap arr[i] and arr[j] 29 int temp = arr[i]; 30 arr[i] = arr[j]; 31 arr[j] = temp; 32 } 33 } 34 35 // Swap arr[i+1] and arr[high] (or pivot) 36 int temp1 = arr[i + 1]; 37 arr[i + 1] = arr[high]; 38 arr[high] = temp1; 39 40 return i + 1; 41 } 42 43 public static void Main(string[] args) 44 { 45 int[] arr = {10, 7, 8, 9, 1, 5}; 46 int n = arr.Length; 47 48 QuickSort(arr, 0, n - 1); 49 50 Console.WriteLine("Sorted array: "); 51 for (int i = 0; i < n; i++) 52 Console.Write(arr[i] + " "); 53 // Output: 1 5 7 8 9 10 54 } 55}
Alongside QuickSort, we will reverse gears and return to the simple sorting algorithms — Bubble Sort, Selection Sort, and Insertion Sort. These foundational algorithms will not only reinforce your understanding of the sorting principle but are often used as stepping stones to understanding more complex algorithms. Happy learning, and let's sort it out!