Data Structure : Searching and Sorting – Notes

  • The process of placing or rearranging a collection of elements into a particular order is known as sorting.
  • Bubble sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements in case they are unordered in n-1 passes.
  • In Selection Sort, the smallest element is selected from the unsorted array and swapped with the leftmost element, and that element becomes a part of the sorted array. The process continues for the next element in the unsorted array till the list is sorted.
  • Insertion Sort places the element of a list at its suitable place in each pass. It is similar to the placing of cards at its right position while playing cards.
  • Complexity analysis is performed to explain how an algorithm will perform when the input grows larger.
  • Searching means trying to locate a particular element called key in a collection of elements. Search specifies whether that key is present in the collection or not. Also, if the key is present, it tells the position of that key in the given collection.
  • Linear search checks the elements of a list, one at a time, without skipping any element. It is useful when we need to search for an item in a small unsorted list, but it is slow and time-consuming when the list contains a large number of items.
    The time taken to search the list increases as the size of the list increases.
  • Binary search takes a sorted/ordered list and divides it in the middle. It then compares the middle element with the key to be searched. If the middle element matches the key, the search is declared successful and the program ends. If the middle element is greater than the key, the search repeats only in the first half of the list. If the middle element is lesser than the key, the search repeats only in the second half of the list. This splitting and reduction in list size continue till the key is found or the remaining list consists of only one item.
  • In binary search, comparisons that do not find the key still give us idea about the location where the key may probably be found! They reveal whether the key is before or after the current middle position in the list, and we can use this information to narrow down or reduce our searching efforts.
  • Hash based searching requires only one key comparison to discover the presence or absence of a key, provided every element is present at its designated position decided by a hash function. It calculates the position of the key in the list
    using a formula called the hash function and the key itself.
  • When two elements map to the same slot in the hash table, it is called collision.
  • The process of identifying a slot for the second and further items in the hash table in the event of collision, is called collision resolution.
  • A perfect hash function maps every input key to a unique index in the hash table. If the hash function is perfect, collisions will never occur.

Leave a Comment

You cannot copy content of this page

Scroll to Top