Quicksort is a sorting algorithm that works as follows. Given a sequence S
of n numbers, take S[0], the first number in S, let us call it pivot. Go
through the remaining numbers in S in the following way. Start with i = 1
and j = n-1. Compare S[i] and S[j] with pivot. If S[i] is less than or equal
to pivot, then set i = i+1. If S[j] is greater than or equal to pivot, set j
= j-1. Continue this way until S[i] is greater than pivot and S[j] is less
than pivot for some 1 <= i < j <= n-1. Swap S[i] with S[j]. Now S[i] becomes
less than equal to pivot and S[j] greater than equal to pivot. Continue as
before. At some point j = i+1 and S[i] is less than or equal to pivot and
S[j] is greater than or equal to pivot. Swap S[i] with pivot. Now numbers
S[0] thru S[i-1] are less than or equal to S[i] and numbers S[i+1] thru
S[n-1] are greater than or equal to S[i]. Hence S[i] is in its correct
location. Recursively sort S[0] thru S[i-1] and S[i+1] thru S[n-1].

Write a program implementing Quicksort.