Algorithm and Data structure: Sorting and Searching

Introduction
•Sorting is a process of arranging a set of similar elements into an increasing or decreasing order.
•For example, we might want to arrange a list of student names into alphabetical order or a list of student marks into descending (highest to lowest) order. We usually stored all the data in an array.
•Specifically, given a sorted list i of n elements, then
i1 <= ... <= in 2 types of sorting : •Internal sorting –algorithms that sort arrays –the amount of data to be sorted is sufficiently small so that the entire process can be carried out in the computer's main memory •External sorting –algorithms that sort sequential disk or magnetic tape files –there are too many data to permit internal sorting. The data is stored in a secondary storage devices •Usually when information is sorted, a portion of the information is used as the sort key. •The key is that part of the data that determines which item comes before another. •Thus, the key is used in comparisons, but when an exchange is made, the entire data structure is swapped. •For example, in a mailing list the ZIP code field might be used as the key, but the entire address is sorted. Classes of Sorting Algorithms •There are three general methods for sorting arrays: •Exchange •Selection •Insertion •To understand these three methods, imagine a deck of cards. –To sort the cards by using exchange, spread them on a table, face up, and then exchange out-of-order cards until the deck is ordered. –Using selection, spread the cards on the table, selects the card of lowest value, take it out of the deck, and hold it in your hand. Then from the remaining cards on the table, select the lowest card and place it behind the one already in your hand. This process continues until all the cards are in your hand. The cards in your hand will be sorted when you finish the process. –To sort the cards by using insertion, hold all the cards in your hand. Place one card at a time on the table, always inserting it in the correct position. The deck will be sorted when you have no cards in your hand. •Preliminaries –The algorithm we describe will all be interchangeable. Each will be passed an array containing the elements and an integer containing the number of elements. –We will assume that N, the number of elements passed to our sorting routines, has already been checked and is legal. In accordance with C conventions, the data will start at position 0 for all sorts. –We will also assume the existence of the "<" and ">" operators, which can be used to place a consistent ordering on the input. Besides, the assignment operator, these are the only operations allowed on the input data. Sorting under these conditions is known as comparison based sorting.

Insertion Sort
•Is the simplest sorting algorithm.
•Insertion sort consists of N – 1 passes. For pass P = 1 through N – 1, insertion sort ensures that the elements in positions 0 through P are in sorted order. Insertion sort makes use of the fact that elements in position 0 through P – 1 are already known to be in sorted order.

Bubble Sort
•The most well known sort.
•Its popularity is derived from its simplicity.
•It is named Bubble sort because, during sorting, values seem to rise to the top of the list like bubbles in a fish tank. Larger values seem to sink like stones.
•Bubble sort variations:
–The simplest is the single bubble sort.
–The more complex double-bubble sort.

•Single bubble sort
–Bubble sort is an exchange sort.
–The basic operation is the exchange of an adjacent pair of elements.
–So in the single bubble sort algorithm, the program will pass through the data, switching consecutive items which are out of order.
–After each pass through the list, the program checks to see if any switches were made.
–If there were, it passes through the list again, switching consecutive items which are still out of order.
–If no switches are made during an entire pass through the list, the data is sorted.
–In the preceding code, item is a pointer to the character array to be sorted and count is the number of elements in the array.
–The bubble sort is driven by two loops.
–Given that there are count elements in the array, the outer loop causes the array to be scanned count-1 times.
–This ensures that, in the worst case, every element is in the proper position when the function terminates.
–The inner loop actually performs the comparisons and exchanges.
–Here is an example : we want to sort 390, 205, 182, 45, 235
•Bubble sort for the first pass (exchange of an adjacent pairs)
390 205 182 45 235 (Switch 1)
205 390 182 45 235 (Switch 2)
205 182 390 45 235 (Switch 3)
205 182 45 390 235 (Switch 4)
205 182 45 235 390 ( First pass-sorted list)
•The first pass moves the largest element (390) to the nth position, forming a sorted list of length one
•The second pass only has to consider (n-1) elements and moves the second largest element to the (n-1) position.

•Double Bubble Sort
–Same as the bubble sort except instead of continuing down the list after switching two consecutive items, the double bubble sort goes up the list, comparing and switching consecutive items until either two items in correct order are found or the top of the list is reached.
–This means that only one pass through the data is required because each out-of-order item 'bubbles up' to its correct position before the next out-of-order item is encountered.
–The number of comparisons is still N-1 and, in the worst case scenario, the program will have to move up and down the list an equivalent number of times to the single bubble sort, but no unnecessary passes through the data are needed.

Shell Sort
•Works by comparing elements that are distant; the distance between comparison decreases as the algorithm runs until the last phase, in which adjacent elements are compared. For this reason, Shell sort is sometimes referred to as diminishing increment sort.
•Shell sort uses a sequence h1, h2, …,ht, called the increment sequence. Any increment sequence will do as long as h1 = 1. But some choices are better than others are. After a phase, using some increment hk, for every I, we have A[i] < m =" n2,"> 7, so we traverse to the right child.
•On the third comparison, we succeed.

•Each comparison results in reducing the number of items to inspect by one-half.
•Figure above shows another tree containing the same values.
•While it is a binary search tree, its behavior is more like that of a linked list, with search time increasing proportional to the number of elements stored.
•This problem can be overcome using AVL tree