18-08-2012, 03:44 PM
SORTING AND SEARCHING TECHNIQUES
SORTING AND SEARCHING TECHNIQUES.pdf (Size: 535.74 KB / Downloads: 136)
INTRODUCTION
Sorting and Searching are fundamental operations in computer science. Sorting refers to
the operation of arranging data in some given order. Searching refers to the operation of
searching the particular record from the existing information. Normally, the information retrieval
involves searching, sorting and merging. In this chapter we will discuss the searching and sorting
techniques in detail.
OBJECTIVES
After going through this unit you will be able to:
Know the fundamentals of sorting techniques
Know the different searching techniques
Discuss the algorithms of internal sorting and external sorting
Difference between internal sorting and external sorting
Complexity of each sorting techniques
Discuss the algorithms of various searching techniques
Discuss Merge sort
Discuss algorithms of sequential search, binary search and binary tree search.
Analyze the performance of searching methods
Internal Sorting
Internal Sorting takes place in the main memory of a computer. The internal sorting methods are
applied to small collection of data. It means that, the entire collection of data to be sorted in
small enough that the sorting can take place within main memory. We will study the following
methods of internal sorting
1. Insertion sort
2. Selection sort
3. Merge Sort
4. Radix Sort
5. Quick Sort
6. Heap Sort
7. Bubble Sort
Merge Sort
Combing the two lists is called as merging. For example A is a sorted list with r elements
and B is a sorted list with s elements. The operation that combines the elements of A and B into
a single sorted list C with n = r + s elements is called merging. After combing the two lists the
elements are sorted by using the following merging algorithm
Suppose one is given two sorted decks of cards. The decks are merged as in Fig. 2.1.
That is, at each step, the two front cards are compared and the smaller one is placed in the
combined deck. When one of the decks is empty, all of the remaining cards in the other deck are
put at the end of the combined deck. Similarly, suppose we have two lines of students sorted by
increasing heights, and suppose we want to merge them into a single sorted line. The new line is
formed by choosing, at each step, the shorter of the two students who are at the head of their
respective lines. When one of the lines has no more students, the remaining students line up at
the end of the combined line.