In this chapter, we learned how to search for values in an array using a linear search method. Then, we explored four different sorting algorithms, and compared them based on their time complexity. Finally, we learned how we can use a sorted array to perform a faster binary search and saw how we can increase our performance by sorting our array before searching in certain situations.
Searching and sorting are two of the most common operations performed in computer programs, and it is very important to have a deep understanding of how they work. Many times the performance of a program can be improved simply by using the correct searching and sorting algorithms to fit the program’s needs, and understanding when you might run into a particularly bad worst-case input.
The project in this module will involve implementing several of these algorithms in the language of your choice. As we learn about more data structures, we’ll revisit these algorithms again to discuss how they can be improved or adapted to take advantage of different structures.
References
Mergesort iterative without a stack
- https://www.geeksforgeeks.org/iterative-merge-sort/
- https://www.techiedelight.com/iterative-merge-sort-algorithm-bottom-up/
Quicksort iterative with a stack
Bubble sort recursive
- Giordano, D., & Maiorana, F. (2015, March). Teaching algorithms: Visual language vs flowchart vs textual language. In 2015 IEEE Global Engineering Education Conference (EDUCON) (pp. 499-504). IEEE.