Challenge: Bubble Sort

Lab C Intermediate 20 points

Read n and n whole numbers. Sort them from smallest to biggest using bubble sort: go through the list again and again, swapping any two neighbours that are in the wrong order. Print the sorted list on one line.

Input

n (1 ≤ n ≤ 100), then n integers.

Output

The numbers in increasing order, separated by spaces.

Example

Input

5
5 1 4 2 8

Output

1 2 4 5 8

Sample input available Sample output available

Editor

Hints

Compare nums[i] with nums[i + 1] and swap if the first is bigger.

After each full pass, the biggest remaining number has "bubbled" to the end.

n - 1 passes are always enough.

Solution explanation

Each pass moves the largest unsorted number to its final place, so the sorted part grows from the end.

Show solution

#include <stdio.h>

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

int main() {
    int n;
    int nums[100];
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &nums[i]);
    }
    for (int pass = 0; pass < n - 1; pass++) {
        for (int i = 0; i < n - 1 - pass; i++) {
            if (nums[i] > nums[i + 1]) {
                swap(&nums[i], &nums[i + 1]);
            }
        }
    }
    for (int i = 0; i < n; i++) {
        printf("%d", nums[i]);
        if (i < n - 1) {
            printf(" ");
        }
    }
    printf("\n");
    return 0;
}

Output

Answer