QUESTION 1 (C language only) Write a function for Bubble Sort that sorts the arr
ID: 3689798 • Letter: Q
Question
QUESTION 1 (C language only)
Write a function for Bubble Sort that sorts the array and produces a trace of how the array is being sorted. Each time the array is modified, it’s printed out so the user can observe how the array is changing. Your code should have: (in C language only)
A function PrintArray that prints the whole array
A function BubbleSort that sorts the array and calls PrintArray
The sample output below shows how the Bubble Sort modifies the array to make it sorted. The last two passes don’t print anything since they don’t perform any changes on the array.
Original data...
5 1 4 3 2
*** Pass 1 ***
1 5 4 3 2
1 4 5 3 2
1 4 3 5 2
1 4 3 2 5
*** Pass 2 ***
1 3 4 2 5
1 3 2 4 5
*** Pass 3 ***
1 2 3 4 5
*** Pass 4 ***
*** Pass 5 ***
Explanation / Answer
#include <stdio.h>
#include <stdbool.h>
void bubbleSort (int array[], int length);
void printArray (int array[]);
int main(void)
{
// initializes an unsorted array
int array[] = {4, 15, 16, 50, 8, 23, 42, 108};
// prints unsorted array
printf(" Unsorted array: ");
printArray(array);
// size of array
int length = (sizeof(array) / (sizeof(array[0])) );
// sorts an array using bubble sort
bubbleSort(&array[0], length);
}
// bubblesort, runs in O(n^2)
void bubbleSort (int* pointerArray, int length)
{
// counts passes
int pass = 0;
// counts number of swaps
int swap = 0;
// make new array
int array[length-1];
// fills in the values
for (int i = 0; i < length; i++)
{
array[i] = pointerArray[i];
}
// determines if array is sorted
bool sorted;
do
{
// assume array is sorted
sorted = true;;
// keeps track of swaps per pass
int swapsPer = 0;
// for every element in array
for (int i = 0; i < length; i++)
{
// test to see if current element is greater than the next element
if (array[i] > array[i+1])
{
// if true, then swap the elements
int tmp = array[i];
array[i] = array[i+1];
array[i+1] = tmp;
// acknowledge that array isn't fully sorted
sorted = false;
// update number of swaps
swap++;
swapsPer++;
}
}
// update pass count
pass++;
// prints the number of passes thus far
printf("Pass # %d made %d swaps: ", pass, swapsPer);
// prints array
printArray(array);
// repeat this while the array is unsorted
} while (sorted == false);
// prints number of swaps
printf("Total number of swaps: %d ", swap);
printf("Total number of passes: %d ", pass);
}
// function to print ever element in an array
void printArray(int array[])
{
// length of array
int length = 8;
// prints every element in array
for (int i = 0; i < length; i++)
{
printf("%d ", array[i]);
}
printf(" ");
}
sample output
Unsorted array:
4 15 16 50 8 23 42 108
Pass # 1 made 3 swaps:
4 15 16 8 23 42 50 108
Pass # 2 made 1 swaps:
4 15 8 16 23 42 50 108
Pass # 3 made 1 swaps:
4 8 15 16 23 42 50 108
Pass # 4 made 0 swaps:
4 8 15 16 23 42 50 108
Total number of swaps: 5
Total number of passes: 4
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.