Searching and Sorting

1. What is searching and sorting?

Searching means to search for a value inside a collection, usually an array. Normally traversing through an array, element by element and checking if an element exists is called linear search. There's a more optimized approach called binary search, which is a more popular searching technique for array data. However, for binary search to work, the data should be sorted.

Sorting means to reorder the elements of a collection, usually an array, in increasing or decreasing order of value. We might often be given unsorted arrays and would need to sort it to perform some operations.

There are a number of sorting techniques like Bubble Sort, Insertion Sort, Quick Sort, Merge Sort and more. Each of them have a slightly different approach and a different time complexity. You can start with the ones listed here since these are the most interview-popular ones and come back to the others when a use case arises.

2. Why is searching and sorting such a big deal?

This is a critical topic from the interview as well as conceptual point of view. These are some of the initial questions that interviewers may ask candidates in interviews. Moreover, searching and sorting find ready application in several other problems too. For instance, you might need to sort an array before performing some other operation on it or you might just need to search for a matching value in a data structure.

3. Playlist on common sorting algos

This is a playlist of some standard sorting algorithms and questions

You can start with videos 6, 5, 3, 2, 4(in that order) in the playlist. You can refer back to the others on a need basis.

4. Binary search videos

Watch videos 30 and 31 in this playlist for binary search

5. Compare Complexities

Refer to this page for a comparison of the Complexities of Sorting Algorithms