We are given a list of random integer values. This list may or may not be sorted
Question:
We are given a list of random integer values. This list may or may not be sorted - or it may be partially sorted. Our task is to sort the list from low to high.
We decide to write a quickSort method to do this.
Part of our quickSort method is a secondary method we call partition.
The partition method, as we know, takes a random element of the array (we like to use the first one) then arranges the array such that all values less than the value of the selected element are to the left of it, and all values greater than the selected element are to the right of it.
We don't care about the arrangement of the values to the left or to the right.
We need to test our partition method to see if it is working correctly.
Unfortunately, we only have the resulting array after the partition method was run one time.
We don't know the state of the array prior to running the partition method.
If we are sure that the partition method did not work - how could we tell? - output "Not working"
Otherwise, output "Possibly working"
How to Input Format
first line is an integer n - the number of integer values in the array
the next line will have n integers separated by spaces. This list is our array after being run through our partition method one time.
Stipulation
all values are valid java integers
1 <= n <= 50000
How to Output Format
Not working if we are certain the partition method does not work
Possibly working if it is possible the partition method did what it is supposed to do.
Example Input 0
5
100000 99998 99999 99996 99994
Example Output 0
Not working
Explanation 0
There is no value in the list with all values to the left less, and all values to the right greater
Example Input 1
11
50000 49999 49998 49996 49994 55000 80000 79999 79997 79995 79993
Example Output 1
Possibly working
Explanation 1
The value 55000 is in the proper location. All values to the left are less and all values to the right are greater.
Introduction to Algorithms
ISBN: 978-0262033848
3rd edition
Authors: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest