Searching
1.Sequential search
- Idea: start from the first element of the linear list and compare the elements of the list with the element being searched for one by one. If they are equal, the search succeeds and stops; if the whole linear list has been scanned and no element equal to the target has been found, that means the linear list does not contain the element being searched for, and the search fails.
- In the best case, the first element is the one being searched for, so the number of comparisons is 1
- In the worst case, the last element is the one being searched for, or the linear list contains no such element at all; then every element in the list must be compared, and the number of comparisons is n
- On average, about n/2 comparisons are needed
- The only choice:
- If the linear list is unordered, then no matter whether it uses sequential storage or linked storage, sequential search is the only option
- Even if the linear list is ordered, sequential search is still the only option when linked storage is used
2.Binary search
- Conditions to satisfy
- Sequential storage is used
- The linear list is ordered, where ordered means the elements are arranged in non-decreasing order, that is, from smallest to largest, and adjacent elements are allowed to be equal
- For an ordered linear list of length n, the process of locating element X by binary search
- If the value of X equals the value of the middle item, the search succeeds and ends
- If X is less than the value of the middle item, continue searching in the first half of the linear list by binary search
- If X is greater than the value of the middle item, continue searching in the second half of the linear list by binary search
- Each comparison in sequential search reduces the search range by only 1, whereas with binary search each comparison can halve the search range, greatly improving efficiency. For an ordered linear list of length n, in the worst case binary search needs only $log_{2}n$ comparisons
Sorting
1.Exchange sorting
- Bubble sort
- Bubble sort compares and swaps adjacent data elements pairwise, continuously eliminating inversions until all data elements are in order
- In the worst case, when sorting a linear list of length n, bubble sort needs n(n-1)/2 comparisons
- Quicksort
- Quicksort takes one element K from the n elements to be sorted and uses element K as the dividing criterion, moving all data elements smaller than K ahead of K and all data elements greater than K behind K. In this way, with K as the dividing line, the linear list is split into two sublists, which is called one pass of sorting. Then the same process is repeated separately for the two sublists before and after K. This continues until the sublists being divided have length 1.
- In the worst case quicksort needs n(n-1)/2 comparisons, but in practice it is more efficient than bubble sort
2.Insertion sorting
- Insertion sort takes one element to be sorted at a time and inserts it, according to the size of its value, into the proper position of the sublist that has already been sorted ahead of it, until all elements have been inserted
- Simple insertion sort
- Think of the n elements to be sorted as one ordered list and one unordered list. At the start, the ordered list contains only one element, while the unordered list contains the other n-1 elements. Each time, the first element of the unordered list is taken and inserted into the correct position in the ordered list, making it a new ordered list with one more element. When an element is inserted, the insertion position and the records after it are shifted back one by one. Finally the ordered list has length n and the unordered list is empty, at which point sorting is complete
- In the worst case, simple insertion sort needs n(n-1)/2 comparisons
- Shell sort
- First take an integer $d{1} < n$ and divide all data elements into $d{1}$ groups, putting all elements whose distance is a multiple of $d{1}$ into one group, which forms a subsequence, and apply simple insertion sort to each subsequence separately. Then take $d{2} < d{1}$ and repeat the grouping and sorting work, until $d{i} = 1$, that is, all records are in a single group
- The efficiency of Shell sort depends on the increment sequence chosen; in the worst case the number of comparisons Shell sort needs is $n ^{r}(1<r<2)$
3.Selection sorting
- Each pass selects the smallest-valued element from the sequence to be sorted and places it in order behind the already-ordered sublist, until the whole sequence meets the sorting requirement
- Simple selection sort
- First select the smallest element from all n data elements to be sorted and swap it with the 1st element, then select the smallest element from the remaining n-1 elements and swap it with the 2nd element. Repeat this operation until all elements are in order
- In the worst case, simple selection sort needs n(n-1)/2 comparisons
- Heap sort
- Given a sequence of n elements $(h{1},h{2},\cdots h{n})$, arrange the elements in order into a complete binary tree; it is called a heap if and only if the following conditions are met. $ \begin{cases} h{i} \geq h{2i} \newline h{i} \geq h{2i+1} \end{cases}$ or $ \begin{cases} h{i} \leq h{2i} \newline h{i} \leq h_{2i+1} \end{cases}$ where $ i=1,2,3,\cdots,n/2 $
- The first case is called a max-heap, where the value of every node is greater than or equal to the values of its left and right child nodes. The second case is called a min-heap, where the value of every node is less than or equal to the values of its left and right child nodes
- In the worst case heap sort needs $ nlog_{2}n$ comparisons
