Description

Bubble sort is a simple sorting algorithm that works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted. Note that the order of the bubble sort is ascending.

 

Step-by-step example

Let us take the array of numbers "5 1 4 2 8", and sort the array from the lowest number to the greatest number using the bubble sort. In each step, the elements written in bold are being compared. There are some passes as follows.

( 5 1 4 2 8 ) → ( 1 5 4 2 8 ). Here, the algorithm compares the first two elements, and swaps them since 5 > 1.

( 1 5 4 2 8 ) → ( 1 4 5 2 8 ). Swap since 5 > 4

( 1 4 5 2 8 ) → ( 1 4 2 5 8 ). Swap since 5 > 2

( 1 4 2 5 8 ) → ( 1 4 2 5 8 ). Now, since the two elements are already in order (8 > 5), the algorithm does not swap them.

Therefore, we note that after 4 comparisons, the largest number 8 can be determined.

 

( 1 4 2 5 8 ) → ( 1 4 2 5 8 ).

( 1 4 2 5 8 ) → ( 1 2 4 5 8 ). Swap since 4 > 2

( 1 2 4 5 8 ) → ( 1 2 4 5 8 ).

Therefore, after 3 comparisons, the second largest number 5 can be determined.

.

.

.

<(5-1=4)-th Pass>

After this pass, the smallest number 1 can then be determined.

 

You need to write double for-loops (nested for-loops):

l   The outer for-loop runs through the required n-1 passes.

l   The inner for-loop carries out the swaps in each pass.

 

The following is an excerpt of incomplete code:

#include 
void bubblesort(???);
int main(void)
{
    int i, n, list[100];

    scanf("%d", &n);
    for (i = 0; i < n; i++)
        scanf("%d", &list[i]);

    bubblesort(???);

    for (i = 0; i < n; i++)
        printf("%d ", list[i]);
    printf("\n");

    return 0;
}

void bubblesort(???)
{
    
    /* your code */
    
}

Input

The input contains two lines.

The first line contains an integer N (0

The second line contains a list of the values of the N elements, which are separated by blanks.

Output

In the output you should print the sorted list.

Be sure to add a newline character '\n' at the end.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Find the median from an unsorted list.

Note that if a < b < c, then the median of the list {a, b, c} is b, and, if a < b < c < d, then the median of the list {a, b, c, d} is the mean of b and c; i.e., it is (b + c)/2.

 

You can use the bubble sort first and then find the median from the sorted list.

Input

The input contains two lines.

The first line contains an integer N (0

The second line contains a list of the values of the N elements, which are separated by blanks.

Output

Print the median of the list of the input. The answer should be expressed as a floating point number with precision to the first decimal place. For example, 4.0 or 6.5.

Be sure to add a newline character '\n' at the end.

Sample Input  Download

Sample Output  Download

Tags

Discuss