Question

Write a program to implement and analyzing the Bubble Sort. a. Write a C++ function for Bubble Sort b. Use a dynamic array of integers in a variable size of n. c. Display the following information: 1) Total counts of comparisons 2) Total counts of shifts / moves / swaps, whichever applies d. Write a main() function to test a best, and an average cases in terms of time efficiency i. Fill out the array with random numbers for an average case ii. Fill out the array with selected numbers for the best case

Answer 1

// Optimized implementation of Bubble sort

#include <stdio.h>

struct me

{

    int a, b;

};

typedef struct me Struct;

void swap(int *xp, int *yp)

{

    int temp = *xp;

    *xp = *yp;

    *yp = temp;

}

// A utility function to print an array of size n

void printArray(int array[], int n)

{

    int i;

    if (n > 0)

        printf("|");

    for (i = 0; i < n; i++)

        printf(" %d |", array[i]);

    printf("\n\n");

}

// An optimized version of Bubble Sort

Struct bubbleSort(int array[], int n)

{

    Struct t;

    t.a = 0;

    t.b = 0;

    int i, j, s, c, st = 0, ct = 0;

    int swapped;

    for (i = 0; i < n - 1; i++)

    {

        s = 0;

        c = 0;

        swapped = 0;

        for (j = 0; j < n - i - 1; j++)

        {

            c++;

            if (array[j] > array[j + 1])

            {

                swap(&array[j], &array[j + 1]);

                swapped = 1;

                s++;

            }

        }

        printf("\n\nNumber of comparison & swaps in iteration number %d are respectively: %d & %d", i + 1, c, s);

        printf("\nResult after iteration number %d is: ", i + 1);

        printArray(array, n);

        t.a += s;

        t.b += c;

        // IF no two elements were swapped by inner loop, then break

        if (swapped == 0)

        {

            printf("\nAs there's no swapping so, stop the algorithm, This further means that Array is already sorted.");

            break;

        }

    }

    return t;

}

// Driver program to test above functions

int main()

{

    Struct t;

    int array[] = {12, 8, 4, 13, 7, 17, 15, 2};

    int n = sizeof(array) / sizeof(array[0]);

    printf("\nArray Given to me: ");

    printArray(array, n);

    t = bubbleSort(array, n);

    printf("\n\n\nTotal number of comparison & swaps are respectively: %d & %d", t.b, t.a);

    printf("\nFinally Sorted Array: ");

    printArray(array, n);

    return 0;

}

SAMPLE OUTPUT:

PLEASE LIKE IT RAISE YOUR THUMBS UP
IF YOU ARE HAVING ANY DOUBT FEEL FREE TO ASK IN COMMENT SECTION