Searching and Sorting

on

Searching and Sorting

Searching: It is the process of comparing for given search elements whether it is present in the List or not, If s is present in the list, the searching is said to be successful, otherwise, we say that the search is unsuccessful.


There are 2 basic types of searching :
1. Linear Search or Sequential Search
2. Binary Search

1. Linear Search: In this method, we compare the search elements beginning from the first element of the list to the last element of the list, until the element is found or all the elements are exhausted.


2. Binary Search: In this technique, the elements of the List must be in an order(either Ascending or Descending) to implement Binary Search. Let us assume, the elements of the List are in Ascending order and discuss the technique. The search element sis first

compared with the middle element of the List. If s==middle element then, we say that the Search is Successful and stop the further search. If s<middle element, then we apply the Binary Search technique on the First Half of the List, by discarding the Second Half of the List. If s>middle element of the list, we apply the Binary search technique on the Second Half of the List, by discarding the First Half.

This will continue until thesis Found or the List is Exhausted.

Sorting:
This is the technique of arranging a List of given elements in an Order (either Ascending or Descending). There are many techniques for Sorting. some of them we learn here are:
  1. Bubble Sort
  2. Selection Sort
  3. Insertion Sort
  4. Quick Sort
  5. Merge Sort etc.

1. Bubble Sort: In this technique, starting from the first element to the last element of the list, every 2 consecutive elements r compared and arranged in order. This will take 'n-1' iterations if there are 'n' elements to be sorted.


2. Selection Sort: In this technique, as the name indicates, First, the first element is compared with all other elements of the list and the least element is replaced in the first position. In second iteratithe on, the second position is filled with the next least element, and so on, till the last element.

3. Insertion Sort: In this technique, the elements are not read directly into the list, instead, every time after reading an element we apply the insertion sort technique, and insert the element into the List in its correct position.


Comments

Post a Comment