Please enable JavaScript.
Coggle requires JavaScript to display documents.
Sorting and order statistics. - Coggle Diagram
Sorting and order statistics.
Sorting algorithms
Sorting algorithms arrange a collection of elements in a specific order, such as ascending or descending.
Some commonly used sorting algorithms include:
Bubble Sort: Repeatedly swap adjacent elements if they are in the wrong order.
Insertion Sort: Build the final sorted array one element at a time by inserting each element into its correct position.
Selection Sort: Find the minimum element and swap it with the first unsorted element.
Merge Sort: Divide the array into halves, recursively sort them, and then merge the sorted halves.
Quick Sort: Select a pivot element, partition the array around the pivot, and recursively sort the subarrays.
Comparison-based sorting algorithms
Many sorting algorithms, such as Bubble Sort, Insertion Sort, Selection Sort, Merge Sort, and Quick Sort, are comparison-based.
Comparison-based sorting algorithms compare elements using key comparisons to determine their relative order.
The best-known lower bound for comparison-based sorting algorithms is O(n log n) in the average and worst case.
Linear-time sorting algorithms
Linear-time sorting algorithms can achieve better time complexity than comparison-based sorting algorithms.
Counting Sort: Suitable for sorting elements with a small range of non-negative integers.
Radix Sort: Sorts elements digit by digit, starting from the least significant digit to the most significant.
Order statistics
Order statistics algorithms deal with finding the kth smallest or largest element in a collection.
Selection algorithms, such as Quick Select, can find the kth smallest element in linear time on average.
Median of Medians is another algorithm that finds an approximate median element in linear time.
Analysis of sorting algorithms
Time complexity: Analysis of sorting algorithms focuses on the number of comparisons and swaps performed.
Space complexity: Analysis considers the additional memory required by sorting algorithms.