Author | Message |
---|---|
skim144
Posts: 63
|
Posted 12:56 Oct 08, 2014 |
Can anyone explain again why the # of operations taken in merging part was 'An + B' ? I'm trying to understand but I can't This was from 2nd quiz last Thursday(10/2). |
G190852562
Posts: 162
|
Posted 22:38 Oct 08, 2014 |
First off, an operation is typically any comparison or assignment. So something like
would run in 2 operations. (Chances are the compiler would actually see that the comparison is always true and execute the code block without doing the comparison, so in only 1 operation). With me so far? Good. Next we will look at the merge part of merge sort(merge sort just calls merge a lot of times). What merge does is it takes 2 sorted arrays and spits out 1 sorted array. Let's take a look at how this works. Let's say we're merging [1, 4, 5] with [2, 3, 6]. Both arrays are sorted, and now we need to merge them. Let's try sticking one to the end of the other: [1, 4, 5, 2, 3, 6]. Nope not 1 big sorted array. Interweaving the two arrays(like bridging a deck of cards) is no good: [1, 2, 4, 3, 5, 6]. What we need to do is start by comparing the first elements in both arrays. So 1 is the smallest. So now that we know what merge sort should do, the pseudo-code should look like
verify that is the algorithm you were using when merging the two arrays from earlier. Now we start counting the number of operations. Each iteration, you are doing a comparison, an assignment, and then incrementing (either i or j). So you have to execute 3 operations each iteration. And how many iterations(loops) are there? Well this is fairly obvious for a But wait, what about when you increment k, when you perform the test condition before entering an iteration A*N + B |
skim144
Posts: 63
|
Posted 14:25 Oct 13, 2014 |
Beautiful explanation. Thank you so much! |