Hour3 Ordered Array
Binary Search (Sorted array):
Given the range, we want to know how many comparisons it will take to complete a search.
a binary search provides a significant speed increase over a linear search. For very small numbers of items, the difference isn’t dramatic.
But the more items there are, the bigger the difference.
repeatedly dividing a range (from the first column) in half until it’s too small to divide further.
Given the range, we want to know how many comparisons it will take to complete a search. That is, given r, we want an equation that gives us s. (Logorithm)
s = log2(r)
you can convert easily to base 2 (log2)to base 10 by multiplying by 3.322
For example, log10(100) = 2, so log2 (100) = 2 times 3.322, or 6.644. Rounded up to 7
Big O Notation
how efficient a computer algorithm
1. Inserting into an Unordered Array: Constant
depend on how many items are in the array. The new item is always placed in the next available position, at a[nElems], and nElemsis then incremented.
We can say the time, T, to insert an item into an unsorted array is a constant K: T = K
2. Linear Searching: Proportional to N
3. a linear search of items in an array, the number of comparisons that
must be made to find a specified item is, on the average, half of the total number of
items.
T = K * N / 2
4. Binary Searching: Proportional to log(N)
T = K * log2(N)
Eliminating the Constant K
Big O notation uses the uppercase letter O, which you can think of as meaning “order
of.”
In Big O notation, we would say that a linear search takes O(N) time, and a binary
search takes O(log N) time.
Figure 3.5 graphs some Big O relationships between time and number of items. Based on
this graph, we might rate the various Big O values (very subjectively) like this: O(1) is
excellent, O(log N) is good, O(N) is fair, and O(N2) is poor. O(N2) occurs in certain sort-ing algorithms that we’ll look at in Hours 4 and 5.
Hour4: Bubble Sort (sorting)
To Do: Bubble-Sort the Baseball Players
1. Compare two players.
2. If the one on the left is taller, swap them.
3. Move one position right.
You continue down the line this way until you reach the right end. You have by no means finished sorting the kids, but you do know that the tallest kid is on the right.
Efficiency of the Bubble Sort(how fast)
1 for(int i = 0; i < nElems - 1; ++i)
2
3 int times = 0;
4
5 for(int j = i + 1; j < nElems; ++j)
6
7 {
8
9 times += 1;
10
11 if(v[i] > v[j])
12
13 swap(i, j);
14
15 }
For 10 items this is
9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 45
In general, N items:
(N-1) + (N-2) + (N-3) + ... + 1 = N*(N-1)/2
N*(N-1)/2 is 45 when N is 10.
Thus the algorithm makes about N2/2 comparisons
Because constants don’t count in Big O notation in Big O notation, we can ignore the divisors 2 and 4 and say that the bubble sort runs in O(N2) time. And this is slow
Whenever you see nested loops such as those in the bubble sort, you can suspect that an algorithm runs in O(N2) time. The outer loop executes N times, and the inner loop exe-cutes N (or perhaps N divided by some constant) times for each cycle of the outer loop.
This means you’re doing something approximately N*N or N2 times.
HOUR5 The Insertion Sort
“The Bubble Sort,” is the easiest sort to understand. However, it’s also the least sophisticated. We can improve it at the cost of some additional complexity. It still executes in O(N2) time, but it’s about twice as fast as the bubble sort.
It’s often used as the final stage of more sophisticated sorts, such as quicksort.
Insertion Sort on the Baseball Players
It’s easier to think about the insertion sort if we begin in the middle of the process, when the team is partly sorted
Partial Sorting(Inserting the Marked Player in the Appropriate Location)
The player where the marker is, whom we’ll call the “marked” player, and all the players on her right, is as yet unsorted.
1. insert the marked player in the appropriate place in the (partially) sorted group.
We take the marked player out of line, and shift the sorted players to make room
When shifting process stop?
when you’ve shifted the last player who is taller than the marked player.
void insertionSort() {
int out; int in;
for(out = 1; out << nElems; ++out) {
int temp = v[out]; // remove marked item , make room for replace
in = out;
while(in > 0 && v[in - 1] > temp) {
v[in] = v[in - 1];
--in;
}
v[in] = temp;
}
}
Efficiency of the Insertion Sort
How many comparisons and copies does this algorithm require?
On the first pass, it compares a maximum of one item. On the second pass, it’s a maximum of two items, and so on, up to a maximum of N–1 comparisons on the last pass.
1 + 2 + 3 + ... + N-1 = N*(N-1)/2
However, because on each pass an average of only half of the maximum number of items
are actually compared before the insertion point is found, we can divide by 2, which gives the following equation:
N*(N-1)/4
For data that is already sorted or almost sorted, the insertion sort does much better.
When data is in order, the condition in the while loop is never true, so it becomes a simple statement in the outer loop, which executes N–1 times. In this case the algorithm runs in O(N) time. If the data is almost sorted, insertion sort runs in almost O(N) time, which makes it a simple and efficient way to order a file that is only slightly out of order.
However, for data arranged in inverse sorted order, every possible comparison and shift is
carried out, so the insertion sort runs no faster than the bubble sort.
Q If both the bubble sort and the insertion sort run in O(N2) time, why not use
the bubble sort, which is simpler to program?
A Besides being somewhat faster for random data, the insertion sort is much faster
for data that is only slightly out of order.