Efficiency and Order of a Sorting Program

Efficiency Considerations

The following are the efficiency considerations while planning for a sorting program / algorithm –

1. Time required to code the program and the type of sorting technique to be selected
2. Execution time
3. Amount of space required by program

In cases where the type of data to be sorted is known, it is easier to select a particular sorting technique to be implemented as a program. But if there is no such idea about data, we go for the worst possible case or average case. New according to the application of the sorting program, the programmer could spend as much on the program.

Execution time of a program is usually calculated as the number of key comparisons made expressed as a function of file size ‘n’. It is often a programmer’s practice to sacrifice the readability of the program for the sake of efficiency and reduced execution time since time of execution is the critical factor which determines the efficiency of a sorting program. Usually function calls are avoided to reduce the execution time.

Now, space considerations is not a crucial factor but perfect sorting programs compensates for both space and time requirements.

Order of a sorting program

The execution time of a sorting program is usually expressed in terms of the magnitude of the input or file size ‘n’. It is often called the order of execution of a program. Consider the for loops (i), (ii) –

(i) for  (i = 0; i < n; i++) {

       x++;

    }

(ii)for  (i = 0; i < n; i++) {

        for  (j = 0; j < n; j++) {

              x++;

        }

     }

The (i) for loop executes n times while the second for loop executes nxn = n<sup2 times. So we say that order of (i) is O(n) and that of (ii) is O(n<sup2). This idea can be extended to all the time determining statements of a whole program to calculate the order of the whole sorting program. Some order of execution are –

O(1) -> Constant time
O(n) -> Linear
O(n<sup2) ->  Quadratic
O(n<sup3) -> cubic
O(logn) -> logarithmic
O(nlogn) -> linear logarithmic
O(nk) -> polynomial
O(dn) -> exponential

where,

O(1) < O(logn) < O(n) < O(nlogn) < O(n<sup2) < O(n<sup3) < O(dⁿ)

—————–> exeuction time increases—————————>

Most of the sorting programs are of the order O(n²) and O(logn).