Решение задачи №1231 «Сортировка пузырьком» с ACMP





Решение задачи №1231 «Сортировка пузырьком» с ACMP

Условие задачи

Задан целочисленный массив, состоящий из N элементов. Требуется посчитать число инверсий (обмена значений соседних элементов массива) в процессе сортировки элементов массива по неубыванию при использовании алгоритма сортировки «пузырьком» (BubbleSort).

Входные данные
Первая строка входного файла INPUT.TXT содержит натуральное число N – количество элементов в массиве (N ≤ 1000). Во второй строке содержатся N целых чисел, не превосходящих 109 по абсолютной величине.

Выходные данные
В выходной файл OUTPUT.TXT выведите целое число – количество инверсий в процессе сортировки методом «пузырька».

#include<iostream>
using namespace std;
void Swap(int &a,int &b)
{
int c=a;a=b;b=c;
}
void SelectSort(int a[],int n)
{
int i,j,k;
for(i=0;i<n;i++)
{
k=i;
for(j=i+1;j<n;j++)
if(a[j]<a[k])k=j;
if(k>i)Swap(a[k],a[i]);
}
}
int BubbleSort (int a[],int n)
{
int i,f,k=0;
do{f=0;
for (i=0;i<n-1;i++)if(a[i]>a[i+1])
{
Swap(a[i],a[i+1]);f=1;k++;
}
}while(f);
return k;
}
void InsertSort(int a[],int n)
{
int i,j,k;
for(i=1;i<n;i++)
{
j=i;k=a[i];
while(j&&k<a[j-1])
{
a[j]=a[j-1];j--;}
a[j]=k;
}
}

void Print(int a[],int n)
{
for(int i=0;i<n;i++)cout<<a[i]<<' ';
}
main ()
{
int a[1000],n,i;
cin>>n;
for(i=0;i<n;i++)cin>>a[i];
cout<<BubbleSort(a,n);
}



Условия задач взяты с сайта acmp.ru