Sorting and Searching
The sorting and searching of large lists can take appreciable amounts of time and the choice of suitable methods can be crucial to the success of software. In coursework, sophisticated searching and sorting with careful explanations of the algorithms chosen provide opportunities to impress the marker and moderator.
We cover sorting and searching in the same tutorial because once you have sorted a list, you can search it more quickly. The efficient binary search only works with sorted data. Even for a linear (sequential) search of sorted data, you can save time by quitting the search for absent data once you have passed the calculated position for the search item. Also, the choices of searching and sorting methods may be related; if you choose a tree sort then you will search that tree.
The number of possible implementations of sorting and searching algorithms is immense so you need to be prepared to adapt code. Sorting and searching may use different data types and data structures such as an array or file of integers or strings or an array or file of records to sort on a key field, perhaps using pointers. Having seen demonstration code for one situation you should by this stage be able develop the program to suit your needs. For example, you should be able to convert code for sorting and searching an array of integers to be able to handle instead key fields of records in an array. (If you experience difficulty, see several routines for handling records in program SortSearchDemo in our third section below). We have covered the comparison of strings (necessary for sorting and searching strings) in our tutorial on string manipulation). You may also have a choice of recursive or iterative solutions. We supply both alternatives for binary searching.
Follow these links to the main sections of this tutorial.