Data Structure : Heap Sort
The binary heap data structures is an array that can be viewed as a complete binary tree. Each node of the binary tree corresponds to an element of the array. The array is completely filled on all levels except possibly lowest.
We represent heaps in level order, going from left to right. The array corresponding to the heap above is [25, 13, 17, 5, 8, 3].
The root of the tree A[1] and given index i of a node, the indices of its parent, left child and right child can be computed
PARENT (i)
return floor(i/2)
LEFT (i)
return 2i
RIGHT (i)
return 2i + 1
Let's try these out on a heap to make sure we believe they are correct. Take this heap,
which is represented by the array [20, 14, 17, 8, 6, 9, 4, 1].
We'll go from the 20 to the 6 first. The index of the 20 is 1. To find the index of the left child, we calculate 1 * 2 = 2. This takes us (correctly) to the 14. Now, we go right, so we calculate 2 * 2 + 1 = 5. This takes us (again, correctly) to the 6.
Now let's try going from the 4 to the 20. 4's index is 7. We want to go to the parent, so we calculate 7 / 2 = 3, which takes us to the 17. Now, to get 17's parent, we calculate 3 / 2 = 1, which takes us to the 20.
Heap Property
In a heap, for every node i other than the root, the value of a node is greater than or equal (at most) to the value of its parent.
A[PARENT (i)] ≥ A[i]
Thus, the largest element in a heap is stored at the root.
Following is an example of Heap:
By the definition of a heap, all the tree levels are completely filled except possibly for the lowest level, which is filled from the left up to a point. Clearly a heap of height h has the minimum number of elements when it has just one node at the lowest level. The levels above the lowest level form a complete binary tree of height h -1 and 2h -1 nodes. Hence the minimum number of nodes possible in a heap of height h is 2h. Clearly a heap of height h, has the maximum number of elements when its lowest level is completely filled. In this case the heap is a complete binary tree of height h and hence has 2h+1 -1 nodes.
Following is not a heap, because it only has the heap property - it is not a complete binary tree. Recall that to be complete, a binary tree has to fill up all of its levels with the possible exception of the last one, which must be filled in from the left side.
Height of a node
We define the height of a node in a tree to be a number of edges on the longest simple downward path from a node to a leaf.
Height of a tree
The number of edges on a simple downward path from a root to a leaf. Note that the height of a tree with n node is
lg n
which is
(lgn). This implies that an n-element heap has height
lg n
In order to show this let the height of the n-element heap be h. From the bounds obtained on maximum and minimum number of elements in a heap, we get
2h ≤ n ≤ 2h+1-1
Where n is the number of elements in a heap.
2h ≤ n ≤ 2h+1
Taking logarithms to the base 2
h ≤ lgn ≤ h +1
It follows that h =
lgn
.
We known from above that largest element resides in root, A[1]. The natural question to ask is where in a heap might the smallest element resides? Consider any path from root of the tree to a leaf. Because of the heap property, as we follow that path, the elements are either decreasing or staying the same. If it happens to be the case that all elements in the heap are distinct, then the above implies that the smallest is in a leaf of the tree. It could also be that an entire subtree of the heap is the smallest element or indeed that there is only one element in the heap, which in the smallest element, so the smallest element is everywhere. Note that anything below the smallest element must equal the smallest element, so in general, only entire subtrees of the heap can contain the smallest element.
Inserting Element in the Heap
Suppose we have a heap as follows
Let's suppose we want to add a node with key 15 to the heap. First, we add the node to the tree at the next spot available at the lowest level of the tree. This is to ensure that the tree remains complete.
Let's suppose we want to add a node with key 15 to the heap. First, we add the node to the tree at the next spot available at the lowest level of the tree. This is to ensure that the tree remains complete.
Now we do the same thing again, comparing the new node to its parent. Since 14 < 15, we have to do another swap:
Now we are done, because 15
20.
Four basic procedures on heap are
- Heapify, which runs in O(lg n) time.
- Build-Heap, which runs in linear time.
- Heap Sort, which runs in O(n lg n) time.
- Extract-Max, which runs in O(lg n) time.
Maintaining the Heap Property
Heapify is a procedure for manipulating heap data structures. It is given an array A and index i into the array. The subtree rooted at the children of A[i] are heap but node A[i] itself may possibly violate the heap property i.e., A[i] < A[2i] or A[i] < A[2i +1]. The procedure 'Heapify' manipulates the tree rooted at A[i] so it becomes a heap. In other words, 'Heapify' is let the value at A[i] "float down" in a heap so that subtree rooted at index i becomes a heap.
Outline of Procedure Heapify
Heapify picks the largest child key and compare it to the parent key. If parent key is larger than heapify quits, otherwise it swaps the parent key with the largest child key. So that the parent is now becomes larger than its children.
It is important to note that swap may destroy the heap property of the subtree rooted at the largest child node. If this is the case, Heapify calls itself again using largest child node as the new root.
Heapify (A, i)
- l ← left [i]
- r ← right [i]
- if l ≤ heap-size [A] and A[l] > A[i]
- then largest ← l
- else largest ← i
- if r ≤ heap-size [A] and A[i] > A[largest]
- then largest ← r
- if largest ≠ i
- then exchange A[i] ↔ A[largest]
- Heapify (A, largest)
Analysis
If we put a value at root that is less than every value in the left and right subtree, then 'Heapify' will be called recursively until leaf is reached. To make recursive calls traverse the longest path to a leaf, choose value that make 'Heapify' always recurse on the left child. It follows the left branch when left child is greater than or equal to the right child, so putting 0 at the root and 1 at all other nodes, for example, will accomplished this task. With such values 'Heapify' will called h times, where h is the heap height so its running time will beθ(h) (since each call does
(1) work), which is
(lgn). Since we have a case in which Heapify's running time
(lg n), its worst-case running time is Ω(lgn).
Example of Heapify
Suppose we have a complete binary tree somewhere whose subtrees are heaps. In the following complete binary tree, the subtrees of 6 are heaps:
The Heapify procedure alters the heap so that the tree rooted at 6's position is a heap. Here's how it works. First, we look at the root of our tree and its two children.
We then determine which of the three nodes is the greatest. If it is the root, we are done, because we have a heap. If not, we exchange the appropriate child with the root, and continue recursively down the tree. In this case, we exchange 6 and 8, and continue.
Now, 7 is greater than 6, so we exchange them.
We are at the bottom of the tree, and can't continue, so we terminate.
Building a Heap
We can use the procedure 'Heapify' in a bottom-up fashion to convert an array A[1 . . n] into a heap. Since the elements in the subarray A[
n/2
+1 . . n] are all leaves, the procedure BUILD_HEAP goes through the remaining nodes of the tree and runs 'Heapify' on each one. The bottom-up order of processing node guarantees that the subtree rooted at children are heap before 'Heapify' is run at their parent.
BUILD_HEAP (A)
- heap-size (A) ← length [A]
- For i ← floor(length[A]/2) down to 1 do
- Heapify (A, i)
We can build a heap from an unordered array in linear time.
Heap Sort Algorithm
The heap sort combines the best of both merge sort and insertion sort. Like merge sort, the worst case time of heap sort is O(n log n) and like insertion sort, heap sort sorts in-place. The heap sort algorithm starts by using procedure BUILD-HEAP to build a heap on the input array A[1 . . n]. Since the maximum element of the array stored at the root A[1], it can be put into its correct final position by exchanging it with A[n] (the last element in A). If we now discard node n from the heap than the remaining elements can be made into heap. Note that the new element at the root may violate the heap property. All that is needed to restore the heap property.
HEAPSORT (A)
- BUILD_HEAP (A)
- for i ← length (A) down to 2 do
exchange A[1] ↔ A[i]
heap-size [A] ← heap-size [A] - 1
Heapify (A, 1)
The HEAPSORT procedure takes time O(n lg n), since the call to BUILD_HEAP takes time O(n) and each of the n -1 calls to Heapify takes time O(lg n).
Now we show that there are at most én/2h+1ù nodes of height h in any n-element heap. We need two observations to show this. The first is that if we consider the set of nodes of height h, they have the property that the subtree rooted at these nodes are disjoint. In other words, we cannot have two nodes of height h with one being an ancestor of the other. The second property is that all subtrees are complete binary trees except for one subtree. Let Xh be the number of nodes of height h. Since Xh-1 o ft hese subtrees are full, they each contain exactly 2h+1 -1 nodes. One of the height h subtrees may not full, but contain at least 1 node at its lower level and has at least2h nodes. The exact count is 1+2+4+ . . . + 2h+1 + 1 = 2h. The remaining nodes have height strictly more than h. To connect all subtrees rooted at node of height h., there must be exactly Xh -1 such nodes. The total of nodes is at least
(Xh-1)(2h+1 + 1) + 2h + Xh-1 which is at most n.
Simplifying gives
Xh ≤ n/2h+1 + 1/2.
In the conclusion, it is a property of binary trees that the number of nodes at any level is half of the total number of nodes up to that level. The number of leaves in a binary heap is equal to n/2, where n is the total number of nodes in the tree, is even and
n/2
whenn is odd. If these leaves are removed, the number of new leaves will be
lg(n/2/2
or
n/4
. If this process is continued for h levels the number of leaves at that level will be
n/2h+1
.
Implementation
void heapSort(int numbers[], int array_size)
{
int i, temp;
for (i = (array_size / 2)-1; i >= 0; i--)
siftDown(numbers, i, array_size);
for (i = array_size-1; i >= 1; i--)
{
temp = numbers[0];
numbers[0] = numbers[i];
numbers[i] = temp;
siftDown(numbers, 0, i-1);
}
}
void siftDown(int numbers[], int root, int bottom)
{
int done, maxChild, temp;
done = 0;
while ((root*2 <= bottom) && (!done))
{
if (root*2 == bottom)
maxChild = root * 2;
else if (numbers[root * 2] > numbers[root * 2 + 1])
maxChild = root * 2;
else
maxChild = root * 2 + 1;
if (numbers[root] < numbers[maxChild])
{
temp = numbers[root];
numbers[root] = numbers[maxChild];
numbers[maxChild] = temp;
root = maxChild;
}
else
done = 1;
}
}
Data Structure: Selection Sort
This type of sorting is called "Selection Sort" because it works by repeatedly element. It works as follows: first find the smallest in the array and exchange it with the element in the first position, then find the second smallest element and exchange it with the element in the second position, and continue in this way until the entire array is sorted.
SELECTION_SORT (A)
for i ← 1 to n-1 do
min j ← i;
min x ← A[i]
for j ← i + 1 to n do
If A[j] < min x then
min j ← j
min x ← A[j]
A[min j] ← A [i]
A[i] ← min x
Selection sort is among the simplest of sorting techniques and it work very well for small files. Furthermore, despite its evident "naïve approach "Selection sort has a quite important application because each item is actually moved at most once, Section sort is a method of choice for sorting files with very large objects (records) and small keys.
The worst case occurs if the array is already sorted in descending order. Nonetheless, the time require by selection sort algorithm is not very sensitive to the original order of the array to be sorted: the test "if A[j] < min x" is executed exactly the same number of times in every case. The variation in time is only due to the number of times the "then" part (i.e., min j ← j; min x ← A[j] of this test are executed.
The Selection sort spends most of its time trying to find the minimum element in the "unsorted" part of the array. It clearly shows the similarity between Selection sort and Bubble sort. Bubble sort "selects" the maximum remaining elements at each stage, but wastes some effort imparting some order to "unsorted" part of the array. Selection sort is quadratic in both the worst and the average case, and requires no extra memory.
For each i from 1 to n - 1, there is one exchange and n - i comparisons, so there is a total of n -1 exchanges and (n -1) + (n -2) + . . . + 2 + 1 = n(n -1)/2 comparisons. These observations hold no matter what the input data is. In the worst case, this could be quadratic, but in the average case, this quantity is O(n log n). It implies that the running time of Selection sort is quite insensitive to the input.
Implementation
void selectionSort(int numbers[], int array_size) { int i, j; int min, temp; for (i = 0; i < array_size-1; i++) { min = i; for (j = i+1; j < array_size; j++) { if (numbers[j] < numbers[min]) min = j; } temp = numbers[i]; numbers[i] = numbers[min]; numbers[min] = temp; } }
Data Structure: Insertion Sort
If the first few objects are already sorted, an unsorted object can be inserted in the sorted set in proper place. This is called insertion sort. An algorithm consider the elements one at a time, inserting each in its suitable place among those already considered (keeping them sorted). Insertion sort is an example of an incremental algorithm; it builds the sorted sequence one number at a time. This is perhaps the simplest example of the incremental insertion technique, where we build up a complicated structure on n items by first building it on n − 1 items and then making the necessary changes to fix things in adding the last item. The given sequences are typically stored in arrays. We also refer the numbers as keys. Along with each key may be additional information, known as satellite data. [Note that "satellite data" does not necessarily come from satellite!]
Algorithm: Insertion Sort
It works the way you might sort a hand of playing cards:
- We start with an empty left hand [sorted array] and the cards face down on the table [unsorted array].
- Then remove one card [key] at a time from the table [unsorted array], and insert it into the correct position in the left hand [sorted array].
- To find the correct position for the card, we compare it with each of the cards already in the hand, from right to left.
Note that at all times, the cards held in the left hand are sorted, and these cards were originally the top cards of the pile on the table.
Pseudocode
We use a procedure INSERTION_SORT. It takes as parameters an array A[1.. n] and the length n of the array. The array A is sorted in place: the numbers are rearranged within the array, with at most a constant number outside the array at any time.
INSERTION_SORT (A)
1. FOR j ← 2 TO length[A]
2. DO key ← A[j]
3. {Put A[j] into the sorted sequence A[1 . . j − 1]}
4. i ← j − 1
5. WHILE i > 0 and A[i] > key
6. DO A[i +1] ← A[i]
7. i ← i − 1
8. A[i + 1] ← key
2. DO key ← A[j]
3. {Put A[j] into the sorted sequence A[1 . . j − 1]}
4. i ← j − 1
5. WHILE i > 0 and A[i] > key
6. DO A[i +1] ← A[i]
7. i ← i − 1
8. A[i + 1] ← key
Example: Following figure (from CLRS) shows the operation of INSERTION-SORT on the array A= (5, 2, 4, 6, 1, 3). Each part shows what happens for a particular iteration with the value of j indicated. j indexes the "current card" being inserted into the hand.
Read the figure row by row. Elements to the left of A[j] that are greater than A[j] move one position to the right, and A[j] moves into the evacuated position.
Analysis
Since the running time of an algorithm on a particular input is the number of steps executed, we must define "step" independent of machine. We say that a statement that takes ci steps to execute and executed n times contributes cin to the total running time of the algorithm. To compute the running time, T(n), we sum the products of the cost and times column [see CLRS page 26]. That is, the running time of the algorithm is the sum of running times for each statement executed. So, we have
T(n) = c1n + c2 (n − 1) + 0 (n − 1) + c4 (n − 1) + c5 ∑2 ≤ j ≤ n ( tj )+ c6 ∑2 ≤ j ≤ n (tj − 1) + c7 ∑2 ≤ j ≤ n (tj − 1) + c8 (n −1)
In the above equation we supposed that tj be the number of times the while-loop (in line 5) is executed for that value of j. Note that the value of j runs from 2 to (n − 1). We have
T(n) = c1n + c2 (n − 1) + c4 (n − 1) + c5 ∑2 ≤ j ≤ n ( tj )+ c6 ∑2 ≤ j ≤ n (tj − 1) + c7 ∑2 ≤ j ≤ n (tj − 1) + c8 (n − 1) Equation (1)
Best-Case
The best case occurs if the array is already sorted. For each j = 2, 3, ..., n, we find that A[i] less than or equal to the key when i has its initial value of (j − 1). In other words, when i = j −1, always find the key A[i] upon the first time the WHILE loop is run.
Therefore, tj = 1 for j = 2, 3, ..., n and the best-case running time can be computed using equation (1) as follows:
T(n) = c1n + c2 (n − 1) + c4 (n − 1) + c5 ∑2 ≤ j ≤ n (1) + c6 ∑2 ≤ j ≤ n (1 − 1) + c7 ∑2 ≤ j ≤ n (1 − 1) + c8 (n − 1)
T(n) = c1n + c2 (n − 1) + c4 (n − 1) + c5 (n − 1) + c8 (n − 1)
T(n) = (c1 + c2 + c4 + c5 + c8 ) n + (c2 + c4 + c5 + c8)
This running time can be expressed as an + b for constants a and b that depend on the statement costs ci. Therefore, T(n) it is a linear function of n.
The punch line here is that the while-loop in line 5 executed only once for each j. This happens if given array A is already sorted.
T(n) = an + b = O(n)
It is a linear function of n.
Worst-Case
The worst-case occurs if the array is sorted in reverse order i.e., in decreasing order. In the reverse order, we always find that A[i] is greater than the key in the while-loop test. So, we must compare each element A[j] with each element in the entire sorted subarray A[1 ..j − 1] and so tj = j for j = 2, 3, ..., n. Equivalently, we can say that since the while-loop exits because i reaches to 0, there is one additional test after (j − 1) tests. Therefore, tj = j for j = 2, 3, ..., n and the worst-case running time can be computed using equation (1) as follows:
T(n) = c1n + c2 (n − 1) + c4 (n − 1) + c5 ∑2 ≤ j ≤ n ( j ) + c6 ∑2 ≤ j ≤ n(j − 1) + c7 ∑2 ≤ j ≤ n(j − 1) + c8 (n − 1)
And using the summations in CLRS on page 27, we have
T(n) = c1n + c2 (n − 1) + c4 (n − 1) + c5 ∑2 ≤ j ≤ n [n(n +1)/2 + 1] + c6 ∑2 ≤ j ≤ n [n(n − 1)/2] + c7 ∑2 ≤ j ≤ n [n(n − 1)/2] + c8 (n −1)
T(n) = (c5/2 + c6/2 + c7/2) n2 + (c1 + c2 + c4 + c5/2 − c6/2 − c7/2 + c8) n − (c2 + c4 + c5 + c8)
This running time can be expressed as (an2 + bn + c) for constants a, b, and c that again depend on the statement costs ci. Therefore, T(n) is a quadratic function of n.
Here the punch line is that the worst-case occurs, when line 5 executed j times for each j. This can happens if array A starts out in reverse order
T(n) = an2 + bn + c = O(n2)
It is a quadratic function of n.
The graph shows the n2 complexity of the insertion sort.
Worst-case and average-case Analysis
We usually concentrate on finding the worst-case running time: the longest running time for any input size n. The reasons for this choice are as follows:
- The worst-case running time gives a guaranteed upper bound on the running time for any input. That is, upper bound gives us a guarantee that the algorithm will never take any longer.
- For some algorithms, the worst case occurs often. For example, when searching, the worst case often occurs when the item being searched for is not present, and searches for absent items may be frequent.
- Why not analyze the average case? Because it's often about as bad as the worst case.
Example: Suppose that we randomly choose n numbers as the input to insertion sort.
On average, the key in A[j] is less than half the elements in A[1 .. j − 1] and it is greater than the other half. It implies that on average, the while loop has to look halfway through the sorted subarray A[1 .. j − 1] to decide where to drop key. This means that tj = j/2.
Although the average-case running time is approximately half of the worst-case running time, it is still a quadratic function of n.
Stability
Since multiple keys with the same value are placed in the sorted array in the same order that they appear in the input array, Insertion sort is stable.
Extra Memory
This algorithm does not require extra memory.
- For Insertion sort we say the worst-case running time is θ(n2), and the best-case running time is θ(n).
- Insertion sort use no extra memory it sort in place.
- The time of Insertion sort is depends on the original order of a input. It takes a time in Ω(n2) in the worst-case, despite the fact that a time in order of n is sufficient to solve large instances in which the items are already sorted.
Implementation
void insertionSort(int numbers[], int array_size)
{
int i, j, index;
for (i = 1; i < array_size; i++)
{
index = numbers[i];
j = i;
while ((j > 0) && (numbers[j − 1] > index))
{
numbers[j] = numbers[j − 1];
j = j − 1;
}
numbers[j] = index;
}
}
Data Structure: Bubble Sort
Bubble Sort is an elementary sorting algorithm. It works by repeatedly exchanging adjacent elements, if necessary. When no exchanges are required, the file is sorted.
SEQUENTIAL BUBBLESORT (A)
for i ← 1 to length [A] do
for j ← length [A] downto i +1 do
If A[A] < A[j-1] then
Exchange A[j] ↔ A[j-1]
Here the number of comparison made
1 + 2 + 3 + . . . + (n - 1) = n(n - 1)/2 = O(n2)
1 + 2 + 3 + . . . + (n - 1) = n(n - 1)/2 = O(n2)
Clearly, the graph shows the n2 nature of the bubble sort.
In this algorithm the number of comparison is irrespective of data set i.e., input whether best or worst.
Memory Requirement
Clearly, bubble sort does not require extra memory.
Implementation
void bubbleSort(int numbers[], int array_size) { int i, j, temp; for (i = (array_size - 1); i >= 0; i--) { for (j = 1; j <= i; j++) { if (numbers[j-1] > numbers[j]) { temp = numbers[j-1]; numbers[j-1] = numbers[j]; numbers[j] = temp; } } } }
Algorithm for Parallel Bubble Sort
PARALLEL BUBBLE SORT (A)
- For k = 0 to n-2
- If k is even then
- for i = 0 to (n/2)-1 do in parallel
- If A[2i] > A[2i+1] then
- Exchange A[2i] ↔ A[2i+1]
- Else
- for i = 0 to (n/2)-2 do in parallel
- If A[2i+1] > A[2i+2] then
- Exchange A[2i+1] ↔ A[2i+2]
- Next k
Parallel Analysis
Steps 1-10 is a one big loop that is represented n -1 times. Therefore, the parallel time complexity is O(n). If the algorithm, odd-numbered steps need (n/2) - 2 processors and even-numbered steps require (n/2) - 1 processors. Therefore, this needs O(n)processors.
Sorting: Algorithm and Data Structure
The objective of the sorting algorithm is to rearrange the records so that their keys are ordered according to some well-defined ordering rule.
Problem: Given an array of n real number A[1.. n].
Objective: Sort the elements of A in ascending order of their values. Internal Sort
External Sort
- Sorting files from tape or disk.
- In this method, an external sort algorithm must access records sequentially, or at least in the block.
Memory Requirement
- Sort in place and use no extra memory except perhaps for a small stack or table.
- Algorithm that use a linked-list representation and so use N extra words of memory for list pointers.
- Algorithms that need enough extra memory space to hold another copy of the array to be sorted.
Stability
The Decision Tree Model
A Lower Bound for the Worst Case
Taking logarithms on both sides
(lg(n!) ≤ hh ≥ lg(n!)
Taking logarithms on both sides
(lg(n!) ≤ hh ≥ lg(n!)
(lg(n!) ≤ hh ≥ lg(n!)
h ≥ lg(n!)
If the file to be sorted will fit into memory or equivalently if it will fit into an array, then the sorting method is called internal. In this method, any record can be accessed easily.
A sorting algorithm is called stable if it is preserves the relative order of equal keys in the file. Most of the simple algorithm are stable, but most of the well-known sophisticated algorithms are not.
There are two classes of sorting algorithms namely, O(n2)-algorithms and O(n log n)-algorithms. O(n2)-class includes bubble sort, insertion sort, selection sort and shell sort. O(n log n)-class includes heap sort, merge sort and quick sort.
O(n2) Sorting Algorithms
O(n log n) Sorting Algorithms
Now we show that comparison-based sorting algorithm has an Ω(n log n) worst-case lower bound on its running time operation in sorting, then this is the best we can do. Note that in a comparison sort, we use only comparisons between elements to gain information about an input sequence <a1, a2, . . . , an>. That is, given two elements ai and aj we perform one of the tests, ai < aj, ai ≤ aj,ai = aj and ai ≥ aj to determine their relative order.
Given all of the input elements are distinct (this is not a restriction since we are deriving a lower bound), comparisons of the form ai =aj are useless, so no comparison of ai = aj are made. We also note that the comparison ai ≤ aj , ai ≥ aj and ai < aj are all equivalent. Therefore we assume that all comparisons have form ai ≥ aj.
Each time a sorting algorithm compares two elements ai and aj , there are two outcomes: "Yes" or "No". Based on the result of this comparison, the sorting algorithm may perform some calculation which we are not interested in and will eventually perform another comparison between two other elements of input sequence, which again will have two outcomes. Therefore, we can represent a comparison-based sorting algorithm with a decision tree T.
As an example, consider the decision tree for insertion sort operating on given elements a1, a2 and a3. There are are 3! = 6 possible permutations of the three input elements, so the decision tree must have at least 6 leaves.
In general, there are n! possible permutations of the n input elements, so decision tree must have at least n! leaves.
The length of the longest path from the root to any of its leaves represents the worst-case number of comparisons the sorting algorithm perform. Consequently, the worst-case number of comparisons corresponds to the height of its tree. A lower bound on the height of the tree is therefore a lower bound on the running time of any comparison sort algorithm.
Theorem The running time of any comparison-based algorithm for sorting an n-element sequence is Ω(n lg n) in the worst case.
Examples of comparison-based algorithms (in CLR) are insertion sort, selection sort, merge sort, quicksort, heapsort, and treesort.
Proof Consider a decision tree of height h that sorts n elements. Since there are n! permutation of n elements and the tree must have at least n! leaves. We have
n! ≤ 2h
Since the lg function is monotonically increasing, from Stirling's approximation we have
n! > (n/e)n where e = 2.71828 . . .
Divide-and-Conquer Algorithm
Unknown
6:57 AM
Divide-and-conquer is a top-down technique for designing algorithms that consists of dividing the problem into smaller subproblems hoping that the solutions of the subproblems are easier to find and then composing the partial solutions into the solution of the original problem.
Little more formally, divide-and-conquer paradigm consists of following major phases:
- Breaking the problem into several sub-problems that are similar to the original problem but smaller in size,
- Solve the sub-problem recursively (successively and independently), and then
- Combine these solutions to subproblems to create a solution to the original problem.
Binary Search (simplest application of divide-and-conquer)
Binary Search is an extremely well-known instance of divide-and-conquer paradigm. Given an ordered array of n elements, the basic idea of binary search is that for a given element we "probe" the middle element of the array. We continue in either the lower or upper segment of the array, depending on the outcome of the probe until we reached the required (given) element.
Problem Let A[1 . . . n] be an array of non-decreasing sorted order; that is A [i] ≤ A [j] whenever 1 ≤ i ≤ j ≤ n. Let'q' be the query point. The problem consist of finding 'q' in the array A. If q is not in A, then find the position where 'q' might be inserted.
Formally, find the index i such that 1 ≤ i ≤ n+1 and A[i-1] < x ≤ A[i].
Sequential Search
Look sequentially at each element of A until either we reach at the end of an array A or find an item no smaller than 'q'.
Sequential search for 'q' in array A
for i = 1 to n do
if A [i] ≥ q then
return index i
return n + 1
Analysis
This algorithm clearly takes a θ(r), where r is the index returned. This is Ω(n) in the worst case and O(1) in the best case.
If the elements of an array A are distinct and query point q is indeed in the array then loop executed (n + 1) / 2 average number of times. On average (as well as the worst case), sequential search takes θ(n) time.
Binary Search
Look for 'q' either in the first half or in the second half of the array A. Compare 'q' to an element in the middle,
n/2
, of the array. Let k =
n/2
. If q ≤ A[k], then search in the A[1 . . . k]; otherwise search T[k+1 . . n] for 'q'. Binary search for q in subarray A[i . . j] with the promise that
A[i-1] < x ≤ A[j]
If i = j then
return i (index)
k= (i + j)/2
if q ≤ A [k]
then return Binary Search [A [i-k], q]
else return Binary Search [A[k+1 . . j], q]
Analysis
Binary Search can be accomplished in logarithmic time in the worst case , i.e., T(n) = θ(log n). This version of the binary search takes logarithmic time in the best case.
Iterative Version of Binary Search
Interactive binary search for q, in array A[1 . . n]
if q > A [n]
then return n + 1
i = 1;
j = n;
while i < j do
k = (i + j)/2
if q ≤ A [k]
then j = k
else i = k + 1
return i (the index)
Analysis
The analysis of Iterative algorithm is identical to that of its recursive counterpart.
Subscribe to:
Posts
(
Atom
)