about the usage of modulus operator

Question

Hi this a part of code for Quick Sort algorithm but realy I do not know that why it uses rand() %n please help me thanks

Swap(V,0,rand() %n)  // move pivot elem to V[0]

Answer 1

It is used for randomizing the Quick Sort to achieve an average of nlgn time complexity.

To Quote from Wikipedia:

What makes random pivots a good choice?

Suppose we sort the list and then divide it into four parts. The two parts in the middle will contain the best pivots; each of them is larger than at least 25% of the elements and smaller than at least 25% of the elements. If we could consistently choose an element from these two middle parts, we would only have to split the list at most 2log2n times before reaching lists of size 1, yielding an algorithm.

Answer 2

Quick sort has its average time complexity O(nlog(n)) but worst case complexity is n^2 (when array is already sorted). So to make it O(nlog(n)) pivot is chosen randomly so rand()%n is generating a random index between 0 to n-1.