Modified Bubble Sort
All submissions for this problem are available.
Advanced Bubble Sort is announced!
The basic operation of the standard bubble sort algorithm is to examine a pair of adjacent numbers, and reverse that pair if the left number is larger than the right number.
But the new algorithm examines a group of three adjacent numbers, and if the leftmost number is larger than the rightmost number, it reverses that entire group. Hence its called "triplet bubble sort".
For example, for L = 5 6 6 4 3, Triplet Bubble Sort would proceed as follows:
- First pass:
- inspect 5 6 6, do nothing: 5 6 6 4 3
- inspect 6 6 4, see that 6 > 4, reverse the triplet: 5 4 6 6 3
- inspect 6 6 3, see that 6 > 3, reverse the triplet: 5 4 3 6 6
- inspect 5 4 3, see that 5 > 3, reverse the triplet: 3 4 5 6 6
- inspect 4 5 6, do nothing: 3 4 5 6 6
- inspect 5 6 6, do nothing: 3 4 5 6 6
- Then the third pass inspects the three triplets and does nothing, so the algorithm terminates.
A bug has just been pointed out: it is possible that Triplet Bubble Sort does not correctly sort the list! Consider the list 8 9 7, for example.
Given a list of N integers, determine whether Triplet Bubble Sort will successfully sort the list into non-decreasing order.
If it will not, find the index (counting starting from 0) of the first sorting error after the algorithm has finished: that is, the first value that is larger than the value that comes directly after it when the algorithm is done.
- Input line consists of two lines: one line with an integer N, the number of values in the list, and then another line with N integers Vi, the list of values.
Output in single line "OK" (without double quotes) if Triplet Bubble Sort correctly sorts the list, or the index (counting starting from 0) of the first sorting error, as described in the problem.
###Sample Input 1:
5 6 8 4 3
###Sample Input 2:
8 9 7
Explanation: Sample Input #1 is similar to the first one described in the problem statement. Triplet Bubble Sort correctly sorts this list, so the answer is OK.
Explanation Sample Input #2 is the second one described in the problem statement. Triplet Bubble Sort does not correctly sort this list, since it terminates with the list 7 9 8. The 9 is the first value in the list that is larger than the next value, so the index of the first sorting error is 1.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS|
Fetching successful submissions