Count the number of operations for a sorting algorithm_问答_开发者

This is my assignment question: Explain with an开发者_如何学运维 example quick sort , merge sort and heap sort . further count the number of operations, by each of these sorting methods.

I don't understand what exactly i have to answer in the context of " count the number of operations " ?

I found something in coremen book in chapter 2, they have explained insertions sort the running time of an algorithm by calculating run time of each statement ....

do i have to do in similar way ?

To count the number of operations is also known as to analyze the algorithm complexity. The idea is to have a rough idea how many operations are in the worst case needed to execute the algorithm on an input of size N, which gives you the upper bound of the computational resources required for that algorithm. And since each operation by itself (like multiplication or comparison for example) is a finite operation and takes deterministic time (even though it might be different on different machines), to get an idea of how good or bad an algorithm is, especially compared to other algorithms, all you need to know is the rough number of operations.

Here's an example with bubble sort. Let's say you have an array of two numbers. To sort it you need to compare both numbers and potentially exchange them. Since comparing and exchanging are single operations, the exact time for executing them is minimal and not important by itself. Thus, you can say that with N=2, the number of operations is O(N)=1. For three numbers, though, you need three operations in the worst case - compare the first and the second one and potentially exchange them, then compare the second one and the third one and exchange them, then compare the first one with the second one again. When you continue to generalize the bubble sort, you will find out that potentially to sort N numbers, you need to do N operations for the first number, N-1 for the second and so on. In other words, O(N) = N + (N-1) + ... + 2 + 1 = N * (N-1) / 2, which for big enough N can be simplified to O(N) = N^2.

Of course, you could just cheat and find out on the web the O(N) number for each of the three sort algorithms, but I would urge you to spend the time and try to come up with that number yourself at first. Even if you get it wrong, comparing your estimate and how you got it with the actual way to estimate their complexity will help you understand better the process of analyzing the complexity of particular piece of software you write in future.

This is called the big O notation.

This page shows you the most common sorting algorithms and their comparison expressed through big O.

Computational complexity (worst, average and best number of comparisons for several typical test cases, see below). Typically, good average number of comparisons/operations is O(n log n) and bad is O(n^2)

From http://www.softpanorama.org/Algorithms/sorting.shtml

I think this assignment is to give you an idea that how a complexity of an algorithm is calculated. For example bubble sort algorithm has a complexity of O(n^2).

// Bubble sort method.
// ref: [http://www.metalshell.com/source_code/105/Bubble_Sort.html][1]
for(x = 0; x < ARRAY_SIZE; x++)
  for(y = 0; y < ARRAY_SIZE-1; y++)
  if(iarray[y] > iarray[y+1]) {
    holder = iarray[y+1];
    iarray[y+1] = iarray[y];
    iarray[y] = holder;
  }

As you see above, two loops are used to sort the array. Let ARRAY_SIZE be n. Then the number of operations is n*(n-1). That makes n^2-n which is denoted by O(N^2). That is big O notation. We just take the n that has the largest exponent, the highest growth rate. If it were 2n^2+2n, that would be still O(N^2) because constants are also omitted in calculating complexity. The wikipedia article on Big O Notation is really helpful (as Leniel mentioned in his post).

That's your homework so I did not get into details of algorithms you mentioned. But you need to do the math like this. But I think what you are asked is the actual number of operations. So, for the example above, if ARRAY_SIZE is 10, the answer gets 10*9=90. To see the differences you need to use the same array in your sample codes.