Bubble Sort - Classic Problems | Repovive

CLS32. Bubble Sort

2s256 MB

Given an array of $n$ integers, sort them in non-decreasing order using the Bubble Sort algorithm.

Bubble Sort repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted.

Constraints

$1 \le n \le 3000$
$-10^9 \le a_i \le 10^9$

Input

\begin{array}{l} n \\ a_1 \quad a_2 \quad \cdots \quad a_n \end{array}

Output

$a_1 \quad a_2 \quad \cdots \quad a_n \text{ (sorted)}$

Samples

Input

5
5 3 1 4 2

Explanation

For this input, the required output is 1 2 3 4 5.

Output

1 2 3 4 5

Input

4
4 3 2 1

Explanation

For this input, the required output is 1 2 3 4.

Output

1 2 3 4

Input

3
1 1 1

Explanation

For this input, the required output is 1 1 1.

Output

1 1 1

Given an array of $n$ integers, sort them in non-decreasing order using the Bubble Sort algorithm.

Bubble Sort repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted.

$1 \le n \le 3000$
$-10^9 \le a_i \le 10^9$

\begin{array}{l} n \\ a_1 \quad a_2 \quad \cdots \quad a_n \end{array}

$a_1 \quad a_2 \quad \cdots \quad a_n \text{ (sorted)}$