{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003ch1\u003e\u003c/h1\u003e\n\n\u003cp\u003e\nWrite a program of the Insertion Sort algorithm which sorts a sequence A in ascending order. The algorithm should be based on the following pseudocode:\n\u003c/p\u003e\n\n\u003cpre\u003efor i \u003d 1 to A.length-1\n key \u003d A[i]\n /* insert A[i] into the sorted sequence A[0,...,j-1] */\n j \u003d i - 1\n while j \u0026gt;\u003d 0 and A[j] \u0026gt; key\n A[j+1] \u003d A[j]\n j--\n A[j+1] \u003d key\n\u003c/pre\u003e\n\n\u003cp\u003e\nNote that, indices for array elements are based on 0-origin.\n\u003c/p\u003e\n\n\u003cp\u003e\nTo illustrate the algorithms, your program should trace intermediate result for each step.\n\u003c/p\u003e\n\n\u003ch2\u003eInput\u003c/h2\u003e\n\n\u003cp\u003e\nThe first line of the input includes an integer N, the number of elements in the sequence.\n\u003c/p\u003e\n\u003cp\u003e\nIn the second line, \u003ci\u003eN\u003c/i\u003e elements of the sequence are given separated by a single space.\n\u003c/p\u003e\n\n\u003ch2\u003eOutput\u003c/h2\u003e\n\n\u003cp\u003e\nThe output consists of \u003ci\u003eN\u003c/i\u003e lines. Please output the intermediate sequence in a line for each step. Elements of the sequence should be separated by single space.\n\u003c/p\u003e\n\n\u003ch2\u003eConstraints\u003c/h2\u003e\n\n\u003cp\u003e\n1 ≤ \u003ci\u003eN\u003c/i\u003e ≤ 100\n\u003c/p\u003e\n\n\u003ch2\u003eSample Input 1\u003c/h2\u003e\n\u003cpre\u003e6\n5 2 4 6 1 3\n\u003c/pre\u003e\n\u003ch2\u003eSample Output 1\u003c/h2\u003e\n\u003cpre\u003e5 2 4 6 1 3\n2 5 4 6 1 3\n2 4 5 6 1 3\n2 4 5 6 1 3\n1 2 4 5 6 3\n1 2 3 4 5 6\n\u003c/pre\u003e\n\n\u003ch2\u003eSample Input 2\u003c/h2\u003e\n\u003cpre\u003e3\n1 2 3\n\u003c/pre\u003e\n\u003ch2\u003eSample Output 2\u003c/h2\u003e\n\u003cpre\u003e1 2 3\n1 2 3\n1 2 3\n\u003c/pre\u003e\n\n\n\n\n\n"}}]}