Sorting Algorithms Overview

Study Notes

Sorting algorithms arrange elements in a specific order, such as numerical or alphabetical.
Algorithms can be classified as comparison-based or non-comparison-based.
Comparison-based algorithms rely on comparing elements using operators like "less than or equal to."
Examples of comparison-based sorting algorithms include Bubble Sort, Insertion Sort, Merge Sort, Heap Sort, Selection Sort, and Quick Sort.
Non-comparison-based sorting algorithms, like Counting Sort and Radix Sort, do not employ direct comparisons between elements.

Selection Sort organizes an array by continuously locating the minimum element in the unsorted portion and appending it to the sorted section.
The algorithm maintains two subarrays: a sorted subarray and an unsorted subarray.
In each iteration, the smallest element from the unsorted subarray is selected and shifted to the sorted subarray to build a fully sorted array.
Example: Starting with arr[] = {2, 7, 4, 1, 5, 3}, the process identifies and moves elements in each step leading to the sorted array {1, 2, 3, 4, 5, 7}.

Quick Sort is characterized by its divide-and-conquer strategy and incremental approach.
The general time complexity for Quick Sort is T(n) = T(k) + T(n-k-1) + O(n), resulting in an average time complexity of O(n²).
It employs O(1) auxiliary space, making it efficient in terms of memory usage.
The partitioning process involves selecting a pivot element, and rearranging the array so that elements less than the pivot are on its left, while those greater are on its right.
The algorithm recursively sorts subarrays around the pivot, enhancing its efficiency in organizing data.

The Quick Sort process involves a function that uses parameters for low and high indices to execute sorting.
The partition function identifies the pivot and facilitates the rearrangement of elements, followed by recursive calls to sort either side of the pivot.