CODEWITHSUNDEEP
javadata-structures
user355002
user355002

Reputation: 871

about the usage of modulus operator

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]

Upvotes: 3

Views: 169

Answers (2)

GG.
GG.

Reputation: 2951

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.

Upvotes: 0

Snehal
Snehal

Reputation: 7486

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.

Upvotes: 2

Related Questions