Итак, я пытался написать случайный код сортировки списков с пузырьком и вставкой сортировки в c;Цель кода - создать случайный массив, отсортировать его с помощью пузырьковой сортировки, затем быстрой сортировки, а затем указать, сколько шагов пошло с помощью пузырьковой сортировки, по сравнению с количеством быстрой сортировки.Затем он повторяет это десять раз, а затем находит среднее количество шагов, которые выполнила быстрая сортировка, и среднее количество шагов, которые выполнила пузырьковая сортировка.
Проблема, с которой я столкнулся, заключается в том, что когда я вызываю количество шагов,использует быструю сортировку, в итоге я получаю число 1, и когда я вызываю среднее из десяти быстрых сортировок, я получаю 4950 (каждый раз).Я заставил его работать для пузырьковой сортировки, но по какой-то причине он не будет работать для вставной сортировки - я думаю, что это связано с оптимизацией моего кода, чтобы он не был повторяющимся, но я не знаю, что делать дальше;любая помощь будет принята с благодарностью!
ссылка на мой код (чтобы показать вывод): https://onlinegdb.com/r14EPAGqm
Мой код:
#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);
}
Так же, как отказ от ответственности, ятолько начал изучать c, так что я определенно не пойму некоторые вещи о языке.