Sorting and Searching

Telephone directories are sorted alphabetically by last name. Why? 

 

Because a sorted index can be searched quickly. Even in the telephone directory of a huge city, one can usually find a name in a few seconds. In an unsorted index, nobody would even try to find a name.

---

There are thousands of examples, where items are to be sorted based on some logic. For example: 

1. we have a list of students which is to be sorted based on name/roll no etc. 
2. a list of jobs to be sorted based on their execution time, 
3. a group of customers to be sorted based on their age. etc.

---

There are different sorting techniques, which will be discussed in brief.

In developing most of the software, we have to work with data that are to be kept in some data structure. To reduce access time, these data have to be stored in a sorted way. Based on the application area a suitable sorting technique needs to be applied. Moreover, if these data are not sorted we need linear time to search an item. If the data are sorted, we need much lesser time (logarithmic) to search an item. The techniques will be discussed in following tutorials.

---

Searching Techniques

• Linear Search (Sequential Search): In linear search, each element of the data structure is checked sequentially until the desired element is found or the end of the structure is reached. This is one of the simplest and most straightforward searching methods but is inefficient for large datasets.
• Binary search: It is a highly efficient search technique that works on sorted datasets. It repeatedly divides the search interval in half, reducing the search space exponentially. It requires that the dataset be sorted before performing the search.
• Jump search: It is used for sorted arrays, and the idea is to jump ahead by fixed steps, instead of checking each element like linear search. After jumping ahead, a linear search is performed in the smaller block where the element might exist.
  
• Interpolation Search: It improves upon binary search by making more intelligent guesses as to where the target is located, based on the values being searched (assuming a uniform distribution). Instead of always checking the middle, it estimates where the target value might be based on a formula that considers the value at the current bounds.
  
• Exponential Search: Exponential search is used when the array is infinite or has an unknown size. It combines binary search with a growing search space, making it faster than binary search in such cases. It starts with a small range and expands exponentially until it finds a range where the target may be present.
  
• Fibonacci search: is similar to binary search but uses Fibonacci numbers to divide the search range. This technique works well when the data is sorted and there are sequential memory accesses.
  
• Depth-First Search (DFS) (for trees and graphs): DFS is used to search in graphs or tree data structures. It starts at a root node and explores as far as possible along each branch before backtracking.
  
• Breadth-First Search (BFS) (for trees and graphs): BFS is another technique used to search graphs or trees. It starts at the root and explores all neighbors at the present depth before moving on to nodes at the next depth level.
  

---

Sorting Techniques

• Bubble Sort repeatedly compares adjacent elements and swaps them if they are in the wrong order. The largest unsorted element "bubbles" up to its correct position after each pass.
• Selection Sort repeatedly selects the smallest (or largest) element from the unsorted portion of the array and places it at the beginning (or end) of the sorted portion.
• Insertion Sort builds the sorted array one element at a time. It picks elements from the unsorted portion and inserts them into their correct position in the sorted portion.
• Merge Sort is a divide-and-conquer algorithm. It divides the array into two halves, recursively sorts each half, and then merges the sorted halves back together.
• Quick Sort is another divide-and-conquer algorithm. It selects a "pivot" element, partitions the array such that elements smaller than the pivot are to the left and larger elements are to the right, and then recursively sorts the subarrays.
• Heap Sort is based on the binary heap data structure. It constructs a max-heap (or min-heap) from the array, then repeatedly extracts the largest (or smallest) element from the heap and rebuilds the heap.
• Counting Sort is a non-comparison-based algorithm, which works by counting the occurrences of each unique element and using that information to place the elements in their correct positions.
• Radix Sort is another non-comparison-based sorting algorithm. It sorts numbers by processing individual digits, starting from the least significant digit to the most significant digit.
• Bucket Sort distributes elements into several buckets, then sorts the elements in each bucket using another sorting algorithm (like insertion sort or quick sort), and finally concatenates the buckets.

---

Happy Exploring!