Introduction To
A sorting algorithm is an algorithm that puts elements of a list in a certain order. The most frequently used orders are numerical order and lexicographical order. Efficient sorting is important for optimizing the efficiency of other algorithms (such as search and merge algorithms) which require input data to be in sorted lists. Sorting is also often useful for canonicalizing data and for producing human-readable output. More formally, the output of any sorting algorithm must satisfy two conditions:
1. The output is in nondecreasing order (each element is no smaller than the previous element according to the desired total order);
2. The output is a permutation (a reordering, yet retaining all of the original elements) of the input.
Sorting algorithms are prevalent in introductory computer science classes, where the abundance of algorithms for the problem provides a gentle introduction to a variety of core algorithm concepts, such as big O notation, divide and conquer algorithms, data structures such as heaps and binary trees, randomized algorithms, best, worst and average case analysis, time–space tradeoffs, and upper and lower bounds.
Course Structure
Basic
Library Implementations of Sorting Algorithms
- Know Your Sorting Algorithm | Set 1 (Sorting Weapons used by Programming Languages)
- Know Your Sorting Algorithm | Set 2 (Introsort- C++’s Sorting Weapon)
- Comparator function of qsort() in C
- std::sort() in C++ STL
- C qsort() vs C++ sort()
- Arrays.sort() in Java with examples
- Collections.sort() in Java with Examples
Misc
- Asymptotic Analysis and comparison of sorting algorithms
- Hoare’s vs Lomuto partition scheme in QuickSort
- Serial Sort v/s Parallel Sort in Java
- An Insertion Sort time complexity question
- Time complexity of insertion sort when there are O(n) inversions?
- Lower bound for comparison based sorting algorithms
- Which sorting algorithm makes minimum number of memory writes?
- When does the worst case of Quicksort occur?
- Can QuickSort be implemented in O(nLogn) worst case time complexity?
- QuickSort Tail Call Optimization (Reducing worst case space to Log n )
- Why Quick Sort preferred for Arrays and Merge Sort for Linked Lists?
- Where is Heap Sort used practically?
- Find memory conflicts among multiple threads
Coding Problems
- Sort elements by frequency | Set 1
- Sort elements by frequency | Set 2
- Count Inversions in an array | Set 1 (Using Merge Sort)
- Sort an array of 0s, 1s and 2s
- Find the Minimum length Unsorted Subarray, sorting which makes the complete array sorted
- Find whether an array is subset of another array | Added Method 3
- Sort a nearly sorted (or K sorted) array
- Sort numbers stored on different machines
- Sort a linked list of 0s, 1s and 2s
- A Pancake Sorting Problem
- Find number of pairs (x, y) in an array such that x^y > y^x
- Count all distinct pairs with difference equal to k
- C Program for Bubble Sort on Linked List
- Sort n numbers in range from 0 to n^2 – 1 in linear time
- C Program to Sort an array of names or strings
- Sort an array according to the order defined by another array
- Sort an array in wave form
- Check if any two intervals overlap among a given set of intervals
- How to efficiently sort a big list dates in 20’s
- Sort an almost sorted array where only two elements are swapped
- Find the point where maximum intervals overlap
- Sort a linked list that is sorted alternating ascending and descending orders?
- C++ program for Sorting Dates using Selection Sort
- How to sort an array of dates in C/C++?
- Sorting Strings using Bubble Sort
- Maximum product of a triplet (subsequnece of size 3) in array
- Find missing elements of a range
- Find a permutation that causes worst case of Merge Sort
- Minimum sum of two numbers formed from digits of an array
- Find minimum difference between any two elements
- Convert an array to reduced form | Set 1 (Simple and Hashing)
- Sorting Vector of Pairs in C++ | Set 1 (Sort by first and second)
- Sorting Vector of Pairs in C++ | Set 2 (Sort in descending order by first and second)
- Sorting 2D Vector in C++ | Set 1 (By row and column)
- Sorting 2D Vector in C++ | Set 2 (In descending order by row and column)
- Sorting 2D Vector in C++ | Set 3 (By number of columns)
- Find Surpasser Count of each element in array
- Rearrange positive and negative numbers with constant extra space
- Sort an array according to count of set bits
- Count distinct occurrences as a subsequence
- Minimum number of swaps required to sort an array
- Number of swaps to sort when only adjacent swapping allowed
- Minimum swaps to make two arrays identical
- Find elements larger than half of the elements in an array
- Count minimum number of subsets (or subsequences) with consecutive numbers
- Sum of all elements between k1’th and k2’th smallest elements
- Number of sextuplets (or six values) that satisfy an equation
- Sort an array according to absolute difference with given value
- Minimize the sum of product of two arrays with permutations allowed
- Position of an element after stable sort
- Chocolate Distribution Problem
- Sort even-placed elements in increasing and odd-placed in decreasing order
- Permute two arrays such that sum of every pair is greater or equal to K
- Choose k array elements such that difference of maximum and minimum is minimized
- Sort an array when two halves are sorted
- Find pair with greatest product in array
- Minimum swap required to convert binary tree to binary search tree
- K-th smallest element after removing some integers from natural numbers
- Check whether Arithmetic Progression can be formed from the given array
- Bucket Sort To Sort an Array with Negative Numbers
- Possible to form a triangle from array values
- Maximum difference between frequency of two elements such that element having greater frequency is also greater
- Sort a Matrix in all way increasing order
- Sort array after converting elements to their squares
- Sort all even numbers in ascending order and then sort all odd numbers in descending order
- Sorting Big Integers
- Sort an array of large numbers
- Sort 3 Integers without using if condition or using only max() function
- Minimum difference between max and min of all K-size subsets
- Minimum swaps to reach permuted array with at most 2 positions left swaps allowed
- Convert an array to reduced form | Set 2 (Using vector of pairs)
- Find sum of non-repeating (distinct) elements in an array
- Minimum sum of absolute difference of pairs of two arrays
- Find the largest multiple of 3 from array of digits | Set 2 (In O(n) time and O(1) space)
- Noble integers in an array (count of greater elements is equal to value)
- Find maximum height pyramid from the given array of objects
- Program to check if an array is sorted or not (Iterative and Recursive)
- Smallest Difference pair of values between two unsorted Arrays
- Find whether it is possible to make array elements same using one external number
- Sort an array of strings according to string lengths
- Check if it is possible to sort an array with conditional swapping of adjacent allowed
- Sort an array after applying the given equation
- Print array of strings in sorted order without copying one string into another
- Sort elements on the basis of number of factors
- Selection Sort
- Bubble Sort
- Recursive Bubble Sort
- Insertion Sort
- Recursive Insertion Sort
- Iterative Merge Sort
- QuickSort
- Iterative Quick Sort
- HeapSort
- Counting Sort
- Radix Sort
- Bucket Sort
- ShellSort
- TimSort
- Comb Sort
- Pigeonhole Sort
- Cycle Sort
- Cocktail Sort
- Strand Sort
- Bitonic Sort
- Pancake sorting
- Binary Insertion Sort
- BogoSort or Permutation Sort
- Gnome Sort
- Sleep Sort – The King of Laziness / Sorting while Sleeping
- Structure Sorting (By Multiple Rules) in C++
- Stooge Sort
- Tag Sort (To get both sorted and original)
- Tree Sort
- Cartesian Tree Sorting
- Odd-Even Sort / Brick Sort
- QuickSort on Singly Linked List
- QuickSort on Doubly Linked List
- 3-Way QuickSort (Dutch National Flag)
- Merge Sort for Linked Lists
- Merge Sort for Doubly Linked List
- 3-way Merge Sort