Answer to Question #188076 in C for Neel

Question

Write a program with analysis to sort in descending manner using 'p' number of values and analyze the complexity.(bubble sort)

Answer 1

#include<stdio.h>
void Bubble_sort(int arr[], int n)
{
    int i,j,temp,flag=0;
    for(i=0;i<n;i++)
    {
        for(j=0;j<n-i-1;j++)
        {
            if(arr[j]<arr[j+1])
            {
                temp=arr[j+1];
                arr[j+1]=arr[j];
                arr[j]=temp;


                flag=1;
            }
        }
        if(flag==0)
        {
            break;
        }
    }
    printf("\nSorted Array: ");
    for(i=0;i<n;i++)
    {
        printf("%d ",arr[i]);
    }
}
int main()
{
    int n;
    printf("Enter the number of elements of array ");
    scanf("%d",&n);
    int arr[n],i;
    printf("\nEnter elements of array ");
    for(i=0;i<n;i++)
    {
        scanf("%d",&arr[i]);
    }
    Bubble_sort(arr,n);
}

In Bubble Sort, n-1 comparisons will be done in the 1st pass, n-2 in 2nd pass, n-3 in 3rd pass and so on. So the total number of comparisons will be,

$(n-1) + (n-2) + (n-3) + ..... + 3 + 2 + 1$

$Sum = \dfrac{n(n-1)}{2}$

$that\space is\space O(n^2)$