Python: Search and Sorting - Exercises, Practice, Solution

Search and Sorting [ 39 exercises with solution]

[An editor is available at the bottom of the page to write and execute the scripts. Go to the editor]

1. Write a Python program for binary search.
Binary Search : In computer science, a binary search or half-interval search algorithm finds the position of a target value within a sorted array. The binary search algorithm can be classified as a dichotomies divide-and-conquer search algorithm and executes in logarithmic time.
Test Data :
binary_search([1,2,3,5,8], 6) -> False
binary_search([1,2,3,5,8], 5) -> True
Click me to see the sample solution

2. Write a Python program for sequential search.
Sequential Search : In computer science, linear search or sequential search is a method for finding a particular value in a list that checks each element in sequence until the desired element is found or the list is exhausted. The list need not be ordered.
Test Data :
Sequential_Search([11,23,58,31,56,77,43,12,65,19],31) -> (True, 3)
Click me to see the sample solution

3. Write a Python program for binary search of an ordered list.
Test Data :
Ordered_binary_Search([0, 1, 3, 8, 14, 18, 19, 34, 52], 3) -> True
Ordered_binary_Search([0, 1, 3, 8, 14, 18, 19, 34, 52], 17) -> False
Click me to see the sample solution

4. Write a Python program to sort a list of elements using the bubble sort algorithm.
Note : According to Wikipedia "Bubble sort, sometimes referred to as sinking sort, is a simple sorting algorithm that repeatedly steps through the list to be sorted, compares each pair of adjacent items and swaps them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted. The algorithm, which is a comparison sort, is named for the way smaller elements "bubble" to the top of the list. Although the algorithm is simple, it is too slow and impractical for most problems even when compared to insertion sort. It can be practical if the input is usually in sort order but may occasionally have some out-of-order elements nearly in position."
Sample Data: [14,46,43,27,57,41,45,21,70]
Expected Result: [14, 21, 27, 41, 43, 45, 46, 57, 70]
Click me to see the sample solution

5. Write a Python program to sort a list of elements using the selection sort algorithm.
Note : The selection sort improves on the bubble sort by making only one exchange for every pass through the list. 
Sample Data: [14,46,43,27,57,41,45,21,70]
Expected Result: [14, 21, 27, 41, 43, 45, 46, 57, 70]
Click me to see the sample solution

6. Write a Python program to sort a list of elements using the insertion sort algorithm.
Note : According to Wikipedia "Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort."
Sample Data: [14,46,43,27,57,41,45,21,70]
Expected Result : [14, 21, 27, 41, 43, 45, 46, 57, 70]
Click me to see the sample solution

7. Write a Python program to sort a list of elements using shell sort algorithm.
Note : According to Wikipedia "Shell sort or Shell's method, is an in-place comparison sort. It can be seen as either a generalization of sorting by exchange (bubble sort) or sorting by insertion (insertion sort). The method starts by sorting pairs of elements far apart from each other, then progressively reducing the gap between elements to be compared. Starting with far apart elements can move some out-of-place elements into position faster than a simple nearest neighbor exchange."
Click me to see the sample solution

8. Write a Python program to sort a list of elements using the merge sort algorithm.
Note: According to Wikipedia "Merge sort (also commonly spelled mergesort) is an O(n log n) comparison-based sorting algorithm. Most implementations produce a stable sort, which means that the implementation preserves the input order of equal elements in the sorted output."
Click me to see the sample solution

9. Write a Python program to sort a list of elements using the quick sort algorithm.
Note: According to Wikipedia "Quicksort is a comparison sort, meaning that it can sort items of any type for which a "less-than" relation (formally, a total order) is defined. Inefficient implementations it is not a stable sort, meaning that the relative order of equal sort items is not preserved. Quicksort can operate in-place on an array, requiring small additional amounts of memory to perform the sorting."
Click me to see the sample solution

10. Write a Python program for counting sort.
According to Wikipedia "In computer science, counting sort is an algorithm for sorting a collection of objects according to keys that are small integers; that is, it is an integer sorting algorithm. It operates by counting the number of objects that have each distinct key value, and using arithmetic on those counts to determine the positions of each key value in the output sequence. Its running time is linear in the number of items and the difference between the maximum and minimum key values, so it is only suitable for direct use in situations where the variation in keys is not significantly greater than the number of items. However, it is often used as a subroutine in another sorting algorithm, radix sort, that can handle larger keys more efficiently".
Click me to see the sample solution

11. Write Python code to create a program for Bitonic Sort.
Bitonic Sort: According to rutgers.edu - Bitonic sort is a comparison-based sorting algorithm that can be run in parallel. It focuses on converting a random sequence of numbers into a bitonic sequence, one that monotonically increases, then decreases. Rotations of a bitonic sequence are also bitonic. More specifically, bitonic sort can be modelled as a type of sorting network. The initial unsorted sequence enters through input pipes, where a series of comparators switch two entries to be in either increasing or decreasing order. The algorithm, created by Ken Batcher in 1968, consists of two parts. First, the unsorted sequence is built into a bitonic sequence; then, the series is split multiple times into smaller sequences until the input is in sorted order.
Click me to see the sample solution

12. Write a Python program to sort a list of elements using Bogosort sort.
In computer science, Bogosort is a particularly ineffective sorting algorithm based on the generation and test paradigm. The algorithm successively generates permutations of its input until it finds one that is sorted. It is not useful for sorting, but may be used for educational purposes, to contrast it with other more realistic algorithms. Two versions of the algorithm exist: a deterministic version that enumerates all permutations until it hits a sorted one, and a randomized version that randomly permutes its input. An analogy for the working of the latter version is to sort a deck of cards by throwing the deck into the air, picking the cards up at random, and repeating the process until the deck is sorted. Its name comes from the word bogus.
Click me to see the sample solution

13. Write a Python program to sort a list of elements using Gnome sort.
Gnome sort is a sorting algorithm originally proposed by Dr. Hamid Sarbazi-Azad (Professor of Computer Engineering at Sharif University of Technology) in 2000 and called "stupid sort" (not to be confused with bogosort), and then later on described by Dick Grune and named "gnome sort". The algorithm always finds the first place where two adjacent elements are in the wrong order, and swaps them. It takes advantage of the fact that performing a swap can introduce a new out-of-order adjacent pair only next to the two swapped elements.
Click me to see the sample solution

14. Write a Python program to sort a list of elements using Cocktail shaker sort.
From Wikipedia, Cocktail shaker sort,[1] also known as bidirectional bubble sort,[2] cocktail sort, shaker sort (which can also refer to a variant of selection sort), ripple sort, shuffle sort,[3] or shuttle sort, is a variation of bubble sort that is both a stable sorting algorithm and a comparison sort. The algorithm differs from a bubble sort in that it sorts in both directions on each pass through the list. This sorting algorithm is only marginally more difficult to implement than a bubble sort, and solves the problem of turtles in bubble sorts. It provides only marginal performance improvements, and does not improve asymptotic performance; like the bubble sort, it is not of practical interest (insertion sort is preferred for simple sorts), though it finds some use in education.
Click me to see the sample solution

15. Write a Python program to sort a list of elements using Comb sort.
The Comb Sort is a variant of the Bubble Sort. Like the Shell sort, the Comb Sort increases the gap used in comparisons and exchanges. Some implementations use the insertion sort once the gap is less than a certain amount. The basic idea is to eliminate turtles, or small values near the end of the list, since in a bubble sort these slow the sorting down tremendously. Rabbits, large values around the beginning of the list do not pose a problem in bubble sort. In bubble sort, when any two elements are compared, they always have a gap of 1. The basic idea of comb sort is that the gap can be much more than 1.
Click me to see the sample solution

16. Write a Python program to sort a list of elements using Cycle sort.
Cycle sort is an in-place, unstable sorting algorithm, a comparison sort that is theoretically optimal in terms of the total number of writes to the original array, unlike any other in-place sorting algorithm. It is based on the idea that the permutation to be sorted can be factored into cycles, which can individually be rotated to give a sorted result.
Click me to see the sample solution

17. Write a Python program to sort a list of elements using Heap sort.
In computer science, heapsort (invented by J. W. J. Williams in 1964) is a comparison-based sorting algorithm. Heapsort can be thought of as an improved selection sort: like that algorithm, it divides its input into a sorted and an unsorted region, and it interactively shrinks the unsorted region by extracting the largest element and moving that to the sorted region. The improvement consists of the use of a heap data structure rather than a linear-time search to find the maximum. Although somewhat slower in practice on most machines than a well-implemented quicksort, it has the advantage of a more favorable worst-case O(n log n) runtime. Heapsort is an in-place algorithm, but it is not a stable sort. A run of the heapsort algorithm sorting an array of randomly permuted values. In the first stage of the algorithm the array elements are reordered to satisfy the heap property. Before the actual sorting takes place, the heap tree structure is shown briefly for illustration.
Click me to see the sample solution

18. Write a Python program to sort a list of elements using Pancake sort.
Pancake sorting is the colloquial term for the mathematical problem of sorting a disordered stack of pancakes in order of size when a spatula can be inserted at any point in the stack and used to flip all pancakes above it. A pancake number is the minimum number of flips required for a given number of pancakes. The problem was first discussed by American geometer Jacob E. Goodman. It is a variation of the sorting problem in which the only allowed operation is to reverse the elements of some prefix of the sequence.
Click me to see the sample solution

19. Write a Python program to sort a list of elements using Radix sort.
According to Wikipedia "In computer science, radix sort is a non-comparative integer sorting algorithm that sorts data with integer keys by grouping keys by the individual digits which share the same significant position and value".
Click me to see the sample solution

20. Write a Python program to sort a list of elements using Selection sort.
According to Wikipedia "In computer science, selection sort is a sorting algorithm, specifically an in-place comparison sort. It has O(n2) time complexity, making it inefficient on large lists, and generally performs worse than the similar insertion sort".
Click me to see the sample solution

21. Write a Python program to sort a list of elements using Time sort.
Click me to see the sample solution

22. Write a Python program to sort a list of elements using Topological sort.
Click me to see the sample solution

23. Write a Python program to sort a list of elements using Tree sort.
Click me to see the sample solution

24. Write a Python program to sort an unsorted array of numbers using Wiggle sort.
Wiggle Sort:
Given an unsorted array nums, reorder it in-place such that nums[0] <= nums[1] >= nums[2] <= nums[3]....
For example, given nums = [3, 5, 2, 1, 6, 4], one possible answer is [1, 6, 2, 5, 3, 4].
Click me to see the sample solution

25. Write a Python program to sort unsorted numbers using Timsort.
From Wikipedia:
Timsort is a hybrid stable sorting algorithm, derived from merge sort and insertion sort, designed to perform well on many kinds of real-world data. It was implemented by Tim Peters in 2002 for use in the Python programming language. The algorithm finds subsequences of the data that are already ordered (runs) and uses them to sort the remainder more efficiently. This is done by merging runs until certain criteria are fulfilled. Timsort has been Python's standard sorting algorithm since version 2.3.
Click me to see the sample solution

26. Write a Python program to sort unsorted numbers using Strand sort.
Strand sort is a recursive sorting algorithm that sorts items of a list into increasing order. It has O(n2) worst time complexity which occurs when the input list is reverse sorted. It has a best case time complexity of O(n) which occurs when the input is a list that is already sorted. Strand sort is not in-place as its space complexity is O(n).
Click me to see the sample solution

27. Write a Python program to sort unsorted numbers using Stooge sort.
Stooge sort is a recursive sorting algorithm. It is notable for its exceptionally bad time complexity of O(n^{log 3 / log 1.5} ) = O(n^2.7095...). The running time of the algorithm is thus slower compared to reasonable sorting algorithms, and is slower than Bubble sort, a canonical example of a fairly inefficient sort. It is however more efficient than Slowsort. The name comes from The Three Stooges.
Click me to see the sample solution

28. Write a Python program to sort unsorted numbers using Recursive Quick Sort.
Quicksort is a divide and conquer algorithm. It first divides the input array into two smaller sub-arrays: the low elements and the high elements. It then recursively sorts the sub-arrays.
Click me to see the sample solution

29. Write a Python program to sort a given collection of numbers and their length in ascending order using Recursive Insertion Sort.
Click me to see the sample solution

30. Write a Python program to sort unsorted numbers using Recursive Bubble Sort.
Click me to see the sample solution

31. Write a Python program to sort unsorted numbers using Random Pivot Quick Sort. Pick a random index as the pivot.
Click me to see the sample solution

32. Write a Python program to sort unsorted numbers using Multi-key quicksort.
From Wikipedia-
Multi-key quicksort:
This algorithm is a combination of radix sort and quicksort. Pick an element from the array (the pivot) and consider the first character (key) of the string (multikey). Partition the remaining elements into three sets: those whose corresponding character is less than, equal to, and greater than the pivot's character. Recursively sort the "less than" and "greater than" partitions on the same character.
Click me to see the sample solution

33. Write a Python program to sort unsorted numbers using Pigeonhole sorting.
Pigeonhole sorting is a sorting algorithm that is suitable for sorting lists of elements where the number of elements (n) and the length of the range of possible key values (N) are approximately the same. It requires O(n + N) time. It is similar to counting sort, but differs in that it "moves items twice: once to the bucket array and again to the final destination [whereas] counting sort builds an auxiliary array then uses the array to compute each item's final destination and move the item there."
The pigeonhole algorithm works as follows:
1. Given an array of values to be sorted, set up an auxiliary array of initially empty "pigeonholes", one pigeonhole for each key in the range of the keys in the original array.
2. Going over the original array, put each value into the pigeonhole corresponding to its key, such that each pigeonhole eventually contains a list of all values with that key.
3. Iterate over the pigeonhole array in increasing order of keys, and for each pigeonhole, put its elements into the original array in increasing order.
Click me to see the sample solution

34. Write a Python program to sort unsorted numbers using patience sorting.
From Wikipedia:
In computer science, patience sorting is a sorting algorithm inspired by, and named after, the card game patience. A variant of the algorithm efficiently computes the length of a longest increasing subsequence in a given array.
The algorithm's name derives from a simplified variant of the patience card game. The game begins with a shuffled deck of cards. The cards are dealt one by one into a sequence of piles on the table, according to the following rules.
1. nitially, there are no piles. The first card dealt forms a new pile consisting of the single card.
2. Each subsequent card is placed on the leftmost existing pile whose top card has a value greater than or equal to the new card's value, or to the right of all of the existing piles, thus forming a new pile.
3. When there are no more cards remaining to deal, the game ends.
Click me to see the sample solution

35. Write a Python program to sort an odd-even sort or odd-even transposition sort.
From Wikipedia:
In computing, an odd-even sort or odd-even transposition sort (also known as brick sort self-published source] or parity sort) is a relatively simple sorting algorithm, developed originally for use on parallel processors with local interconnections. It is a comparison sort related to bubble sort, with which it shares many characteristics. It functions by comparing all odd/even indexed pairs of adjacent elements in the list and, if a pair is in the wrong order (the first is larger than the second) the elements are switched. The next step repeats this for even/odd indexed pairs (of adjacent elements). Then it alternates between odd/even and even/odd steps until the list is sorted.
Click me to see the sample solution

36. Write a Python program to sort unsorted numbers using non-parallelized implementation of odd-even transposition sort.
From Wikipedia:
In computing, an odd-even sort or odd-even transposition sort (also known as brick sort or parity sort) is a relatively simple sorting algorithm, developed originally for use on parallel processors with local interconnections. It is a comparison sort related to bubble sort, with which it shares many characteristics. It functions by comparing all odd/even indexed pairs of adjacent elements in the list and, if a pair is in the wrong order (the first is larger than the second) the elements are switched. The next step repeats this for even/odd indexed pairs (of adjacent elements). Then it alternates between odd/even and even/odd steps until the list is sorted.
Click me to see the sample solution

37. Write a Python program to sort unsorted numbers using Odd Even Transposition Parallel sort.
Odd Even Transposition Parallel sort:
This is an implementation of odd-even transposition sort.
It works by performing a series of parallel swaps between odd and even pairs of variables in the list.
This implementation represents each variable in the list with a process and each process communicates with its neighbouring processes in the list to perform comparisons.
They are synchronized with locks and message passing but other forms of synchronization could be used.
Click me to see the sample solution

38. Write a Python program to sort unsorted strings using natural sort.
Natural sort order is an ordering of strings in alphabetical order, except that multi-digit numbers are treated atomically, i.e., as if they were a single character. Natural sort order has been promoted as being more human-friendly ("natural") than the machine-oriented pure alphabetical order.
For example, in alphabetical sorting "z11" would be sorted before "z2" because "1" is sorted as smaller than "2", while in natural sorting "z2" is sorted before "z11" because "2" is sorted as smaller than "11".
Alphabetical sorting:
z11
z2
Natural sorting:
z2
z11
Click me to see the sample solution

39. Write a Python program to sort unsorted numbers using Merge-insertion sort.
From Wikipedia,
In computer science, merge-insertion sort or the Ford-Johnson algorithm is a comparison sorting algorithm published in 1959 by L. R. Ford Jr. and Selmer M. Johnson.It uses fewer comparisons in the worst case than the best previously known algorithms, binary insertion sort and merge sort, and for 20 years it was the sorting algorithm with the fewest known comparisons. Although not of practical significance, it remains of theoretical interest in connection with the problem of sorting with a minimum number of comparisons. The same algorithm may have also been independently discovered by Stanislaw Trybula and Czen Ping.
Click me to see the sample solution

Python Code Editor:

More to Come !

Do not submit any solution of the above exercises at here, if you want to contribute go to the appropriate exercise page.

Test your Python skills with w3resource's quiz