What is passes in sorting algorithm?

Answer 1

Assuming you're talking about comparison-based sorting algorithms, the number of passes is the number of comparisons that the algorithm makes internally while sorting. In a programming language, this would be the total number of times the loop executes. This number is defined by the computational complexity (Big-O notation), which defines an upper bound.

Answer 2

We use the term "pass" whenever we perform a complete traversal over a set of data. In sorting algorithms, the number of operations that must be performed is a function of the number of elements, such that a single pass over n elements will take O(n) time. If we perform n passes in O(n) time then the overall complexity is O(n*n).

Although sorting algorithms reduce in complexity with each pass (because the unsorted set is reduced on each pass), a sorting algorithm with O(n*n) complexity does not reduce significantly enough with each pass to merit notating the individual reductions. That is, O(n*n) is sufficient to inform us that only one element is in its correct place with each pass. It can be assumed that the number of elements processed on each pass is reduced by at least 1, but the number of passes required remains the same. BubbleSort is an example of an O(n*n) sorting algorithm.

An efficient sorting algorithm places an increasing number of elements on each pass, thus significantly reducing the number of passes required. Quicksort is a typical example because each complete pass doubles the number of elements in their correct place (starting with one element on the first pass) and thus halves the number of passes required to sort the remaining elements. These algorithms are quadratic and have a complexity of O(log n).

Note that the complexity of an algorithm is merely an indication of its performance. There will always be fringe cases where an algorithm performs better or worse than its indicated complexity and we denote these using best case, worst case and average case.