Number of sort bubbles in an array without bubble sort

Question

Hi, I am trying to count the number of bubblesort swaps in an array of size N, but I would like to do this without making bubblesort, I heard about merge sorting, and someone already told me that its some kind of merge sort modification ... I don't want to use this basic algorithm>

void bubbleSort(int * array, int size){
    for(int i = 0; i < size - 1; i++){
        for(int j = 0; j < size - i - 1; j++){
            if(array[j+1] < array[j]){
                int tmp = array[j + 1];
                array[j + 1] = array[j];
                array[j] = tmp;
            }   
        }   
    }   
}  

Do any of you guys have an idea?

Answer 1

It seems that you can use the following function to calculate the total number of swaps:

int calcSwaps(int *array, int size) {
    int cnt = 0;

    for (int i = 0; i + 1 < size; ++i) {
        for (int j = i + 1; j < size; ++j) {
            if (array[j] < array[i]) {
                ++cnt;
            }
        }
    }

    return cnt;
}

The basic idea is that in this type of sorting each element array[i]will be replaced with all the elements array[j], j > i, array[j] < array[i].

, . . . . array[i], ? , array[j] array[j + 1], array[j] > array[j + 1]. . , array[i] > array[j], i < j, , . , array[i], array[j], array[j] < array[i], j > i ( , array[i] ), , , array[i], .

Answer 2

, , . .

: Easy - return 0 inversion, 1

: .

, . ? (i, j) ( ), , j ( , < j). , ( j ).

? ( ). left [i] ​​ , right [j] [i] . , left [i] ​​ , , j , left [i] ( [i]). , , left [i] , j.

#include <stdio.h>

long long int MS(int a[],int temp[],int left,int right);
long long int Merge(int a[],int temp[],int left,int mid,int right);

long long int MS(int a[],int temp[],int left,int right)
{
    long long int cnt=0;
    int mid;
    if(right>left)
    {
        mid=(right+left)/2;
        cnt=MS(a,temp,left,mid);
        cnt+=MS(a,temp,mid+1,right);
        cnt+=Merge(a,temp,left,mid+1,right);
    }
    return cnt;
}

long long int Merge(int a[],int temp[],int left,int mid,int right)
{
    int i,j,k;
    long long int cnt=0;
    i=left;
    j=mid;
    k=left;
    while(i<=mid-1 && j<=right)
    {
        if(a[i]<=a[j])
            temp[k++] = a[i++];
        else
        {
            temp[k++] = a[j++];
            cnt+=(mid-i);
        }
    }
    while (i<=mid-1)
        temp[k++]=a[i++];
    while(j<=right)
        temp[k++]=a[j++];
    for(i=left;i<=right;i++)
        a[i]=temp[i];
    return cnt;
}

int main()
{
    int *a,*tmp,t,n;
    scanf("%d",&t);
    for(int i=0;i<t;i++)
    {
        scanf("%d",&n);
        a=new int [n];
        tmp=new int [n];
        for(int j=0;j<n;j++)
            scanf("%d",&a[j]);
        printf("%lld\n",MS(a,tmp,0,n-1));
    }
    return 0;
}

Answer 3

. , , . - :

int bubbleSort(int * array, int size){
    std::vector<int> temp_array(array, array + size);
    int count{0};
    for(int i = 0; i < size - 1; i++){
        for(int j = 0; j < size - i - 1; j++){
            if(temp_array[j+1] < temp_array[j]){
                int tmp = temp_array[j + 1];
                temp_array[j + 1] = temp_array[j];
                temp_array[j] = tmp;
                count++;
            }
        }
    }
    return count;
}

Answer 4

: , , , !

:

{3, 5, 1, 4, 2}

index. , index . 1 - , 1, index 2, , 2 . :

{1, 3, 5, 4, 2}

1 , , :

{3, 5, 4, 2}

:

#include <algorithm>
#include <vector>

unsigned swaps(std::vector<double>& data) {
    unsigned result = 0;
    while (!data.empty()) {
        auto smallest = std::min_element(data.begin(), data.end());
        result += smallest - data.begin();
        data.erase(smallest);
    }
    return result;
}

, (, )