Searching and Sorting 587
Time Complexity
It is known that the depth of the complete binary tree is (log2w). In worst case, the number of
comparisons in each step would be equal to the depth of the tree. The number of comparisons for
the above observation would be O (n log2n). Thus, the number of comparisons in this method
would be O (n log2 n).
SUMMARY
1) Searching is a technique of finding accurate location of an element in the given item list or set
of the elements of an array, list, or trees.
2) If the given element is present in the collected elements or array then the search process is said
to be successful. The search is said to be unsuccessful if the given element doesn't exist in the
array.
3) The search method in which an element to be searched, is checked in the entire data structure
in a sequential way from starting to end is called linear search.
4) Binary search is quicker than the linear search. However, it cannot be applied on unsorted
data structure. This is the precondition. Before applying binary search, the linear data structure
must be sorted in either ascending or descending order by using one of the sorted methods.
5) Sorting is a process in which records are arranged in ascending or descending order.
6) Exchange sort: The bubble sort is an example of exchange sort. In this method, repetitively
comparison among successive elements of an array or list is performed and appropriately
swapping of elements is done.
7) Insertion sort: In this type elements are compared and element are inserted at appropriate
place in the list according to the sorting order.
8) Quick sort: Partition exchange is also called as quick sort. It is based on partition of elements.
Hence, the method falls under divide and conquer technique. The main list of element is
divided into two sub-lists. The quick sort marks an element in a list called as pivot or key. All
the elements whose value is less than J are shifted towards the left and elements whose value
is grater than J to right of J. Now, the key element divides the main list in to two parts.
9) Tree sort: Inorder and Heap sort methods are elaborated under tree sorting. Inorder tree
sorting method involves arranging the elements as per rules. In this method, firstly the left
element of tree is chosen, then node and right node.
The rule for heap sort prescribes that each parent node should have bigger value than its child
node. The detail rule can be followed from the heap sort example as given above.
EXERCISES
A) Answer the following questions.
1) What is sorting and searching? How they are essential for data base applications.
2) Explain linear and binary search.
3) Differentiate between linear and binary search.
4) Explain types of sorting.
5) Distinguish between selection and exchange sort.
B) Select the appropriate option for each of the following questions.
1) The process of arranging records in an ordered manner is called
a) sorting b) searching
c) indexing d) none of the above
588 Programming and Data Structures
2) Th<? process of finding a particular record is called
a) sorting
b)
searching
c) indexing
d)
none of the above
Records must be sorted by
a) linear search
b)
binary search
c) selection search
d)
none of the above
One of the following sort lists is divided into two sub-lists
a) quick sort
b)
exchange sort
c) merge sort
d)
none of the above
Exchange sort is also called
a) bubble sort
b)
merge sort
c) shell sort
d)
none of the above
C) Attempt the tallowing programs.
1) Write a program to sort 15 elements using bubble sort.
2) Write a program to find the given number in an array of 50 elements. Search how many
times a given element exists in the list.
3) Write a program to demonstrate successful and unsuccessful search. Display appropriate
messages.
4) Write a program to demonstrate binary search. Use character array andstore 10 names. Find
the given name.
5) Write a program to search with linear search the given name in string array of 10 names.
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.