#include<stdio.h>

//bubble sort
void BubbleSort(int A[], int n) {
    int i, j, tmp, flag = 1;
    j = n - 1;
    while (flag) {
        flag = 0;
        for (i = 0; i < j; i++) {
            if (A[i] > A[i + 1]) {
                tmp = A[i];
                A[i] = A[i + 1];
                A[i + 1] = tmp;
                flag = 1;
            }
        }
        j = i;
    }
}

//insert sort 
void InsertSort(int A[], int n) {
    int i, j, tmp;
    for (i = 1; i < n; i++) {
        tmp = A[i];
        if (A[i] < A[i - 1]) {
            for (j = i - 1; j >= 0; j--) {
                if (A[j] <= tmp) {
                    A[j + 1] = tmp;
                    break;
                }
                else A[j + 1] = A[j];
            }
            if (j < 0) A[0] = tmp;
        }
    }
}

//shell sort
void ShellSort (int A[], int n) {
    int gap = n / 2;
    int i, j, k, tmp;
    while (gap > 0) {
        for (k = 0; k < gap; k++) {
            for (i = k; i < n; i += gap) {
                tmp = A[i];
                if (A[i] < A[i - gap]) {
                    for (j = i - gap; j >= 0; j = j - gap) {
                        if (A[j] <= tmp) {
                            A[j + gap] = tmp;
                            break;
                        }
                        else A[j + gap] = A[j];
                    }
                    if (j < 0) A[j + gap] = tmp;
                }
            }
            gap = gap / 2;
        }
    }
}

//Merge sort
void merge (int A[], int low, int mid, int high, int tmp[]) {
    int i, j, k;
    for (k = 0, i = low, j = mid + 1; i <= mid && j <=high; k++) {
        if (A[i] < A[j]) {
            tmp[k] = A[i];
            i++;
        }
        else {
            tmp[k] = A[j];
            j++;
        }
    }
    while (i <= mid) {
        tmp[k] = A[i++];
        k++;
    }
    while (j <= high) {
        tmp[k] = A[j++];
        k++;
    }
    for (i = low, k = 0; i <= high; i++, k++) A[i] = tmp[k];
}

void MergeSort (int A[], int low, int high, int tmp[]) {
    if (low < high) {
        int mid = (low + high) / 2;
        MergeSort(A, low, mid, tmp);
        MergeSort(A, mid + 1, high, tmp);
        merge(A, low, mid, high ,tmp);
    }
}

//quick sort
void QuickSort(int A[], int l, int h)
{
    if (l < h) {
        int low = l, high = h, tmp = A[low];
        while (low < high) {
            while (low < high && A[high] >= tmp) {
                high--;
            }
            A[low] = A[high];
            while (low < high && A[low] <= tmp) {
                low++;
            }
            A[high] = A[low];
        }
        A[low] =  tmp;
        QuickSort(A, l, low);
        QuickSort(A, low + 1, h);
    }
}

void main()
{
    int A[100], B[100], C[100], D[100], E[100];
    int n, i = 0, data;
    scanf("%d", &data);
    while (data != -1) {
        A[i] = B[i] = C[i] = D[i] = E[i] = data;
        i++;
        scanf("%d", &data);
    }
    n = i;
    int tmp[n];
    for (i = 0; i < n; i++) printf("%d ", A[i]);
    printf("\nBubbleSort:");
    BubbleSort(A, n);
    for (i = 0; i < n; i++) printf("%d ", A[i]);
    printf("\nInsertSort:");
    InsertSort(B, n);
    for (i = 0; i < n; i++) printf("%d ", B[i]);
    printf("\nShellSort:");
    InsertSort(C, n);
    for (i = 0; i < n; i++) printf("%d ", C[i]);
    printf("\nMergeSort:");
    MergeSort(D, 0, n - 1, tmp);
    for (i = 0; i < n; i++) printf("%d ", D[i]);
    printf("\nQuickSort:");
    QuickSort(E, 0, n - 1);
    for (i = 0; i < n; i++) printf("%d ", E[i]);
    printf("\n");
}

sort