Sorting of data structure experiment II: exchange sorting

Sorting of data structure experiment II: exchange sorting

Time Limit: 1000MS Memory Limit: 65536KB
Submit Statistic

Problem Description

Bubble sorting and fast sorting are sorting methods based on "exchange". Your task is to sort the N integers (in the range of long integers) given by the topic from small to large, and output the number of data exchanges required for bubble and fast sorting of these n numbers.

Input

For consecutive groups of input data, the first row of each group of data gives a positive integer N(N ≤ 10 ^ 5), followed by N integers separated by spaces.

Output

The output data takes up one line, representing the number of exchanges required for bubble sorting and quick sorting respectively. The numbers are separated by one space, and no extra space is allowed at the end of the line.

Example Input

8
49 38 65 97 76 13 27 49

Example Output

15 9

Hint

Note: do not exchange when data is equal

The code is as follows:

#include<bits/stdc++.h>

using namespace std;
int cnt,sum;

int Mao_Pao(int *f,int n)
{
    int i,j,t;
    for(i=0; i<n; i++)
    {
        for(j=0; j<n-i-1; j++)
        {
            if(f[j]>f[j+1])
            {
                t=f[j];
                f[j]=f[j+1];
                f[j+1]=t;
                cnt++;
            }
        }
    }
    return cnt;
}

void qsort(int *f,int left,int right)
{
    if(left>=right)
        return ;
    int key=f[left];
    int i=left;
    int j=right;
    while(i<j)
    {
        while(i<j&&f[j]>=key)
            j--;
        if(f[i]!=f[j])
        {
            f[i]=f[j];
            sum++;
        }
        while(i<j&&f[i]<=key)
            i++;
        if(f[j]!=f[i])
        {
            f[j]=f[i];
            sum++;
        }
    }
    f[i]=key;
    qsort(f,left,i-1);
    qsort(f,i+1,right);
}

int main()
{
    int a[10001],b[10001];
    int n;
    while(cin>>n)
    {
        sum=0;
        cnt=0;
        for(int i=0; i<n; i++)
        {
            cin>>a[i];
            b[i]=a[i];
        }
        qsort(b,0,n-1);
        cout<<Mao_Pao(a,n)<<" "<<sum<<endl;
    }
    return 0;
}


Posted on Thu, 30 Apr 2020 21:54:25 -0700 by Welling