~ Sorting Algorithms - Sorting Algorithms in Python

Sorting Algorithms - Python Code Sorted

An introduction to Sorting Algorithms

In this series we provide a

  • video,
  • explanation,
  • flow chart and
  • python code implementation 
  • Download suggested classroom learning activities

for the various sorting algorithms.

In computer science, a sorting algorithm is exactly what you'd imagine it would be - it's simply an algorithm that puts elements of a list in a certain order. Sounds simple enough doesn't it, but if you really think about it, so much of what we do - particularly with data - involves sorting, and without it, well, we'd be stuck! Sorting a small list of say 10 names in alphabetical order is rather simple, but consider a list that is comprised of a million items - what then? Obviously, the more efficient the sorting algorithm, the better, particularly in terms of time efficiency. A ton of people have even dedicated their entire lives to this stuff ....so don't put it aside as boring just yet!

The most-used orders are numerical order and lexicographical order. Efficient sorting is important for optimizing the use of other algorithms (such as search and merge algorithms) which require input data to be in sorted lists; it is also often useful for canonicalizing data and for producing human-readable output. More formally, the output must satisfy two conditions: The output is in nondecreasing order (each element is no smaller than the previous element according to the desired total order); The output is a permutation (reordering but with all of the original elements) of the input. Further, the data is often taken to be in an array, which allows random access, rather than a list, which only allows sequential access, though often algorithms can be applied with suitable modification to either type of data.

This series will primarily look at python code for the various sorting algorithms, along with an explanation (video or presentation) for each. If you're really interested however, there is plenty of additional information on this topic below:

Basic :

  1. Sorting Terminology
  2. Stability in sorting algorithms
  3. Time complexities of Standard Sorting Algorithms
  4. External Sorting

Sorting Algorithms :

Library Implementations of Sorting Algorithms :

  1. Know Your Sorting Algorithm | Set 1 (Sorting Weapons used by Programming Languages)
  2. Know Your Sorting Algorithm | Set 2 (Introsort- C++’s Sorting Weapon)
  3. Comparator function of qsort() in C
  4. sort() in C++ STL
  5. C qsort() vs C++ sort()
  6. Arrays.sort() in Java with examples
  7. Collections.sort() in Java with Examples

Misc :

  1. Asymptotic Analysis and comparison of sorting algorithms
  2. Hoare’s vs Lomuto partition scheme in QuickSort
  3. Serial Sort v/s Parallel Sort in Java
  4. An Insertion Sort time complexity question
  5. Time complexity of insertion sort when there are O(n) inversions?
  6. Lower bound for comparison based sorting algorithms
  7. Which sorting algorithm makes minimum number of memory writes?
  8. When does the worst case of Quicksort occur?
  9. Can QuickSort be implemented in O(nLogn) worst case time complexity?
  10. QuickSort Tail Call Optimization (Reducing worst case space to Log n )
  11. Why Quick Sort preferred for Arrays and Merge Sort for Linked Lists?
  12. Where is Heap Sort used practically?
  13. Find memory conflicts among multiple threads

Coding Problems :

  1. Sort elements by frequency | Set 1
  2. Sort elements by frequency | Set 2
  3. Count Inversions in an array | Set 1 (Using Merge Sort)
  4. Sort an array of 0s, 1s and 2s
  5. Find the Minimum length Unsorted Subarray, sorting which makes the complete array sorted
  6. Find whether an array is subset of another array | Added Method 3
  7. Sort a nearly sorted (or K sorted) array
  8. Sort numbers stored on different machines
  9. Sort a linked list of 0s, 1s and 2s
  10. A Pancake Sorting Problem
  11. Find number of pairs (x, y) in an array such that x^y > y^x
  12. Count all distinct pairs with difference equal to k
  13. C Program for Bubble Sort on Linked List
  14. Sort n numbers in range from 0 to n^2 – 1 in linear time
  15. C Program to Sort an array of names or strings
  16. Sort an array according to the order defined by another array
  17. Given a sorted array and a number x, find the pair in array whose sum is closest to x
  18. Sort an array in wave form
  19. Check if any two intervals overlap among a given set of intervals
  20. How to efficiently sort a big list dates in 20’s
  21. Sort an almost sorted array where only two elements are swapped
  22. Find the point where maximum intervals overlap
  23. Sort a linked list that is sorted alternating ascending and descending orders?
  24. C++ program for Sorting Dates using Selection Sort
  25. How to sort an array of dates in C/C++?
  26. Sorting Strings using Bubble Sort
  27. Maximum product of a triplet (subsequnece of size 3) in array
  28. Find missing elements of a range
  29. Find a permutation that causes worst case of Merge Sort
  30. Minimum sum of two numbers formed from digits of an array
  31. Find minimum difference between any two elements
  32. Convert an array to reduced form | Set 1 (Simple and Hashing)
  33. Sorting Vector of Pairs in C++ | Set 1 (Sort by first and second)
  34. Sorting Vector of Pairs in C++ | Set 2 (Sort in descending order by first and second)
  35. Sorting 2D Vector in C++ | Set 1 (By row and column)
  36. Sorting 2D Vector in C++ | Set 2 (In descending order by row and column)
  37. Sorting 2D Vector in C++ | Set 3 (By number of columns)
  38. Find Surpasser Count of each element in array
  39. Rearrange positive and negative numbers with constant extra space
  40. Sort an array according to count of set bits
  41. Count distinct occurrences as a subsequence
  42. Minimum number of swaps required to sort an array
  43. Number of swaps to sort when only adjacent swapping allowed
  44. Minimum swaps to make two arrays identical
  45. Find elements larger than half of the elements in an array
  46. Count minimum number of subsets (or subsequences) with consecutive numbers
  47. Sum of all elements between k1’th and k2’th smallest elements
  48. Number of sextuplets (or six values) that satisfy an equation
  49. Sort an array according to absolute difference with given value
  50. Minimize the sum of product of two arrays with permutations allowed
  51. Position of an element after stable sort
  52. Chocolate Distribution Problem
  53. Sort even-placed elements in increasing and odd-placed in decreasing order
  54. Permute two arrays such that sum of every pair is greater or equal to K
  55. Chose k array elements such that difference of maximum and minimum is minimized
  56. Sort an array when two halves are sorted
  57. Find pair with greatest product in array
  58. Minimum swap required to convert binary tree to binary search tree
  59. K-th smallest element after removing some integers from natural numbers
  60. Check whether Arithmetic Progression can be formed from the given array
  61. Bucket Sort To Sort an Array with Negative Numbers
  62. Possible to form a triangle from array values
  63. Maximum difference between frequency of two elements such that element having greater frequency is also greater
  64. Check if reversing a sub array make the array sorted
  65. Find all triplets with zero sum
  66. Sort a Matrix in all way increasing order
  67. Sort array after converting elements to their squares
  68. Sort all even numbers in ascending order and then sort all odd numbers in descending order
  69. Sorting Big Integers
  70. Sort an array of large numbers
  71. Sort 3 Integers without using if condition or using only max() function
  72. Minimum difference between max and min of all K-size subsets
  73. Minimum swaps to reach permuted array with at most 2 positions left swaps allowed
  74. Convert an array to reduced form | Set 2 (Using vector of pairs)
  75. Find sum of non-repeating (distinct) elements in an array
  76. Minimum sum of absolute difference of pairs of two arrays
  77. Find the largest multiple of 3 from array of digits | Set 2 (In O(n) time and O(1) space)
  78. Noble integers in an array (count of greater elements is equal to value)
  79. Find maximum height pyramid from the given array of objects
  80. Program to check if an array is sorted or not (Iterative and Recursive)
  81. Smallest Difference Triplet from Three arrays
  82. Smallest Difference pair of values between two unsorted Arrays
  83. Find whether it is possible to make array elements same using one external number
  84. Sort an array of strings according to string lengths
  85. Check if it is possible to sort an array with conditional swapping of adjacent allowed
  86. Sort an array after applying the given equation
  87. Print array of strings in sorted order without copying one string into another
  88. Sort elements on the basis of number of factors

Quick Links :

  1. ‘Practice Problems’ on Sorting
  2. ‘Quizzes’ on Sorting
  3. Ask a Question on ‘Sorting’