So I've been trying to write a random list sorting code with bubble and insertion sort in c; the intention of the code is to generate a random array, sort it with bubble sort then quicksort, then tell how many steps bubble sort took versus how many quicksort took. It then repeats this ten times and then finds the average number of steps that quicksort did and the average number of steps bubble sort did.
The issue I've encountered is that when I call for the number of steps that quicksort uses, I end up getting the number 1, and when I call for the average of the ten quicksorts, I get back 4950 (every time). I got it to work for bubble sort, but for some reason, it won't work for insertion sort - I think it has to do with optimizing my code to not being repetitive, but I don't know what to do next; any help would be greatly appreciated!
link to my code (to show output): https://onlinegdb.com/r14EPAGqm
My code:
#include <time.h>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
static int num_count_bubble_sort = 0;
static double avg_bubble = 0;
static int num_count_quick_sort = 0;
static double avg_quick = 0;
void swap(int *xp, int *yp)
{
int temp = *xp;
*xp = *yp;
*yp = temp;
}
// A function to implement bubble sort
void bubbleSort(int arr[], int n)
{
int i, j;
num_count_bubble_sort = 0;
for (i = 0; i < n-1; i++)
{
int swapped = 0;
// Last i elements are already in place
for (j = 0; j < n-i-1; j++)
{
num_count_bubble_sort++;
avg_bubble++;
if (arr[j] > arr[j+1])
{
swap(&arr[j], &arr[j+1]);
swapped = 1;
}
}
if (swapped == 0) break;
}
}
/* This function takes last element as pivot, places
the pivot element at its correct position in sorted
array, and places all smaller (smaller than pivot)
to left of pivot and all greater elements to right
of pivot */
int partition (int arr[], int low, int high)
{
int pivot = arr[high]; // pivot
int i = (low - 1); // Index of smaller element
num_count_quick_sort =0;
for (int j = low; j <= high- 1; j++)
{
// If current element is smaller than or
// equal to pivot
num_count_quick_sort++;
avg_quick++;
if (arr[j] <= pivot)
{
i++; // increment index of smaller element
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}
/* The main function that implements QuickSort
arr[] --> Array to be sorted,
low --> Starting index,
high --> Ending index */
void quickSort(int arr[], int low, int high)
{
if (low < high)
{
/* pi is partitioning index, arr[p] is now
at right place */
int pi = partition(arr, low, high);
// Separately sort elements before
// partition and after partition
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
/* Function to print an array */
void printArray(int arr[], int size)
{
int i;
for (i=0; i < size; i++)
{
printf("%d ", arr[i]);
}
}
/* random array generator */
int main()
{
srand(time(NULL));
int l;
for (int l = 10; l>0; l--)
{
int r;
int arr[100];
printf("Original Array: \n");
for (int r = 99; r>=0; r--)
{
int rand_num = rand() % 100;
printf("%d ",rand_num);
arr[r] = rand_num;
}
/* bubble sort */
int n = sizeof(arr)/sizeof(arr[0]);
bubbleSort(arr, n);
printf("\n");
printf("Bubble Sorted Array: \n");
printArray(arr, n);
/*quick sort */
num_count_quick_sort=0;
quickSort(arr, 0, n-1);
printf("\n");
printf("Quick Sorted Array: \n");
printArray(arr, n);
printf("\n");
/* printing amount of comparisons done by each sort */
printf("comparisons done by bubble sort: %d ",
num_count_bubble_sort);
printf("\n");
printf("comparisons done by Quick sort: %d ",num_count_quick_sort);
printf("\n");
}
printf("\n");
avg_quick = avg_quick/10.0;
avg_bubble = avg_bubble/10.0;
printf("average number of comparisons done by Bubble Sort (list length
of 100 elements): %f", avg_bubble);
printf("\n");
printf("average number of comparisons done by Quick Sort(list length of
100 elements): %f", avg_quick);
}
Just as a disclaimer, I just started learning c, so I will definitely not understand certain things about the language.
There are two things happening here.
First, your test code does this:
So you're always passing a sorted array to quick sort. That's why your average for quick sort is always equal to 4,950.
To fix that problem, make a copy of the array and pass the copy to bubble sort. Then you're sure that quick sort and bubble sort are being supplied the same input.
The reason num_count_quick_sort is always 1 is because you set it to 0 every time you enter the partition function. And since the last call to partition will always have high and low differ by 1, you'll only go through the iteration loop once. You need to remove that assignment in the partition function.
One other thing is that your method for computing the average is a little odd, although in this case it produces the same result. What you're doing is accumulating a total for all runs at the same time you're accumulating the total for a single run. That is, you have:
num_count_quick_sort++;
avg_quick++;
The more common way of doing this is to update avg_quick only at the end of a run. In your code you have:
/* printing amount of comparisons done by each sort */
printf("comparisons done by bubble sort: %d ", num_count_bubble_sort);
printf("\n");
printf("comparisons done by Quick sort: %d ,num_count_quick_sort);
printf("\n");
So you would remove the increment of avg_quick (and avg_bubble) from your loops, and instead write:
/* printing amount of comparisons done by each sort */
printf("comparisons done by bubble sort: %d\n", num_count_bubble_sort);
avg_bubble += num_count_bubble_sort;
printf("comparisons done by Quick sort: %d\n",num_count_quick_sort);
avg_quick += num_count_quick_sort;
(Note that I added a newline to the end of those printf statements. No need for a separate statement just to print a new line.)
The primary reason for this isn't efficiency, but rather simplicity. It reduces the scope of the avg_quick and avg_bubble variables, making it easier to prevent them from being modified inadvertently by other, unrelated, code.