Hi On Nov 22, 8:26 pm, Sherry <[EMAIL PROTECTED]> wrote:
> I know how the complexity of an algorithms is calculated, but how > would this relate to the time it takes? Let's say I have 25000 random > numbers I'd like to sort with the selection sort. Now how could I use > Big O notation to calculate the time taken to sort these numbers?? First thing is to analyse processing done to sort the list. Total time depends on 1) time taken to do comparisons - fetching data items, plus 2) time taken to move data items in memory - fetches and puts, plus 3) time to update indices to the list and possibly a buffer - again fetches and puts. We can say that all 1) and 2) items result in a corresponding 3) item and concentrate on the first two. For a basic selection sort the number of comparisons is (n^2)/2 irrespective of the order of items in the list. The number of data moves is zero for an in-order list, 3n/2 for reverse order. Insertion sort comparisons can vary between n-1 and (n^2-n)/2 for in-order and reverse order lists, moves between zero and (n^2+3n-4)/2. Both these sorts are classified O(n^2) but the time taken in relation to n varies with the algorithm used as well as the disposition of items in the unsorted list. Two recurrence relations are involved, one for comparisons, one for moves. See for example, http://en.wikipedia.org/wiki/Quicksort : Average Complexity. Maybe note that changing the base of the log just results in different constants. Solving these recurrencies will get a formula: T = k.Fc(n) + j.Fm(n) where Fc(n) and Fm(n) are functions of n for average comparisons and moves, k and j are respective constants. If we choose our sorting algorithms carefully, say bubble sort and quicksort, Fc(n) and Fm(n) are the same and can write T = K.F(n) where F(n) is (n^2) for bubblesort and (n log n) for quicksort. (could use selection sort, its (n^2)/2 comparisons on an average list far outways moves but bubblesort's symetry is more convincing) > .... but how do you approximate time taken?? To do this we need a K for the test machine which makes the whole thing fairly academic. If we restrict our investigations to sorting small binaries in a contiguous list, integers say, machine architecture side effects are minimized. Compute an average K for each of the two algorithms from timed tests on many different random order lists for each of a set of list sizes (suggest writing an application to do this). There should be a good match between values calculated from K.F(n) and tests on additional list sizes. Possibly the values of K will be similar for the two algorithms. There are several reasons why this approach should not be taken too seriously: OS intrusion under preemptive multitasking; cache thrashing when sorting pointers to large records for algorithms that use any element of binary search, list division or insertion sort i.e. all except selection sort. Basically we know that sorting random numbers or records with random ordered keys quicksort will be faster than other comparison algorithms because it needs fewer comparisons and moves. Why not use it in preference to selection sort? Quicksort optimization techniques are widely known. Mergesort comes a close second and provides stability making it preferable to quicksort in many cases but, looking at some of the non-working and below optimum merging implementations around it may be harder to optimize. For what its worth, output from a timing program for several different sorts on a random number key is shown below but keep in mind that this is sorting pointers to large records not integers in a list: 25000 random order InsertionSort : 2.06371235513341 Secs SimpleSort : 0.15609483378997 Secs ShellSort : 0.0141451883337958 Secs Mergesort : 0.00804883131314883 Secs QuickSort : 0.00606510008439111 Secs SimpleSort is an insertion sort variant using binary search to find the insertion point and block data moves. It gets O(n log n) comparisons and O(n^2) moves. - Martin --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
