import java.util.Random;
import java.util.Arrays;

class Sequential implements A2Solver {

	// The actual A2 algorithm, which ensures the array is sorted
	// biggest to smallest from in A[0] to A[k-1], but doesn't sort
	// the entire array
	public void solveA2(int[] a, int k) {
		Util.insertionSortReverse(a, 0, Math.min(k, a.length));

		// Insert the biggest values in a[k..n] into a[0..k-1]
		for (int i = k; i < a.length; ++i) {
			if (a[i] > a[k-1]) {
				Util.swap(a, i, k-1);
				int j = k - 2;
				while (j >= 0 && a[j + 1] > a[j]) {
					Util.swap(a, j + 1, j);
					j -= 1;
				}
			}
		}
	}
}