在 C 中的合并排序程序中实现冒泡排序时出错

Question

我正在学习数据结构和算法。该程序在数组中获取一定数量的输入，并使用归并排序对它们进行排序。条件是每当子数组的大小等于或小于 10 时，它应该使用 冒泡排序 对元素进行排序，然后将它们合并在一起。我的问题是让程序进行冒泡排序。到目前为止，我一直无法找出程序中的错误。我仍然每天都在学习。如果有人可以帮我找到错误并修复它，我将不胜感激。非常感谢，祝您愉快。

代码如下：

#include<stdio.h>
#include<stdlib.h>
#define arrsize 10
void merge_sort(int, int);
void merge_array(int, int, int, int);
int arr_sort[arrsize];
void bubblesort(int a[],int size);
void main()
{
  int a[50],n,i;
   printf("\nEnter %d Elements for Sorting\n", arrsize);
  for (i = 0; i < arrsize; i++)
    scanf("%d", &arr_sort[i]);

  printf("\nYour Data   :");
  for (i = 0; i < arrsize; i++) {
    printf("\t%d", arr_sort[i]);
  }

  merge_sort(0, arrsize - 1);

  printf("\n\nSorted Data :");
  for (i = 0; i < arrsize; i++) {
    printf("\t%d", arr_sort[i]);
  }

}
void bubblesort(int arr_sort[],int size)
{
  int temp,i,j;
  for(i=0;i<size;i++)
  {
   for(j=0;j<size-1;j++)
   {
    if(arr_sort[j]>arr_sort[j+1])
    {
     temp=arr_sort[j];
     arr_sort[j]=arr_sort[j+1];
     arr_sort[j+1]=temp;
    }
  }
 }
}
void merge_sort(int i, int j) {
  int m;
  if (i < j) {
    m = (i + j) / 2;
       if(m<=5)
    {
        for(i=0;i<=m;i++){
            for(j=i+1;j<=m;j++){
        bubblesort(arr_sort[i],m);
        bubblesort(arr_sort[j],m);}}
        merge_array(i,m,m+1,j);
    }
    else
         merge_sort(i, m);
    merge_sort(m + 1, j);
    merge_array(i, m, m + 1, j);
  }
}

void merge_array(int a, int b, int c, int d) {
  int t[50];
  int i = a, j = c, k = 0;

  while (i <= b && j <= d) {
    if (arr_sort[i] < arr_sort[j])
      t[k++] = arr_sort[i++];
    else
      t[k++] = arr_sort[j++];
  }
  while (i <= b)
    t[k++] = arr_sort[i++];

  while (j <= d)
    t[k++] = arr_sort[j++];

  for (i = a, j = 0; i <= d; i++, j++)
    arr_sort[i] = t[j];
}

Answer 1

您的代码中存在以下问题：

从 merge_sort，你应该调用 bubble_sort 给定的 floor 幅度，固定在你的 merge_sort，全局指定，或作为函数的参数。前者最容易实现。
您从 merge_sort 调用 bubble_sort 从一开始就是错误的，因为您传递的 int 值应该是 int*。
你的函数应该所有将要排序的数组作为参数，并且至少长度.这使得函数更健壮，并且由于指针算法，比您想象的更容易实现。

解决这个问题需要大手术。

已更新merge_array

首先对 merge_array 函数进行一些手术。这假定您支持可变长度数组 (VLA)。请注意，该函数接受数组基地址、中点和总长度。

void merge_array(int a[], int mid, int len)
{
    // change to int tmp[arrsize], or use dynamic allocation, if your
    // platform doesn't support VLAs
    int tmp[len];

    int i = 0, j = mid, k = 0;
    while (i < mid && j < len)
        tmp[k++] = ((a[i] < a[j]) ? a[i++] : a[j++]);

    while (i < mid)
        tmp[k++] = a[i++];

    for (i = 0; i < k; ++i)
        a[i] = tmp[i];
}

已更新merge_sort

现在merge_sort功能如问题分析所述。像上面一样，它应该有一个数组基地址和一个长度，但这就是它所需要的。指针运算将让我们对递归调用进行分区。

void merge_sort(int a[], int len)
{
    if (len < 5)
    {
        // bubblesort short partitions (less than length:5)
        bubble_sort(a, len);
    }
    else
    {
        int mid = len / 2;
        merge_sort(a, mid);
        merge_sort(a + mid, len - mid); // note pointer arithmetic here
        merge_array(a, mid, len);
    }
}

已更新bubble_sort

这个简单的冒泡排序使用前向交换检测在已经排序的检测中提前离开。像前面的函数一样，我们有一些数组的基地址和指定的长度。

void bubble_sort(int a[], int size)
{
    int swapped = 1;
    while (swapped && size-- > 0)
    {
        swapped = 0;
        for (int i = 0; i < size; ++i)
        {
            if (a[i + 1] < a[i])
            {
                int tmp = a[i];
                a[i] = a[i + 1];
                a[i + 1] = tmp;
                swapped = 1;
            }
        }
    }
}

综合考虑

下面是完整的程序，其中包括一个用于将数组转储到控制台的打印助手，以及一个用于避免冗长键盘输入的随机生成器。提供的 main() 创建一个随机填充的数组，打印它，排序它，然后打印结果。显然每个运行的输出会有所不同，但您希望了解上述函数的调用方式。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define arrsize 40

void merge_sort(int a[], int len);
void merge_array(int a[], int mid, int len);
void bubble_sort(int a[], int size);

void merge_array(int a[], int mid, int len)
{
    // change to int tmp[arrsize], or use dynamic allocation, if your
    // platform doesn't support VLAs
    int tmp[len];

    int i = 0, j = mid, k = 0;
    while (i < mid && j < len)
        tmp[k++] = ((a[i] < a[j]) ? a[i++] : a[j++]);

    while (i < mid)
        tmp[k++] = a[i++];

    for (i = 0; i < k; ++i)
        a[i] = tmp[i];
}

void merge_sort(int a[], int len)
{
    if (len < 5)
    {
        // bubblesort short partitions (less than length:5)
        bubble_sort(a, len);
    }
    else
    {
        int mid = len / 2;
        merge_sort(a, mid);
        merge_sort(a + mid, len - mid); // note pointer arithmetic here
        merge_array(a, mid, len);
    }
}

void bubble_sort(int a[], int size)
{
    int swapped = 1;
    while (swapped && size-- > 0)
    {
        swapped = 0;
        for (int i = 0; i < size; ++i)
        {
            if (a[i + 1] < a[i])
            {
                int tmp = a[i];
                a[i] = a[i + 1];
                a[i + 1] = tmp;
                swapped = 1;
            }
        }
    }
}

void print_arr(int const arr[], int len)
{
    while (len-- > 0)
        printf("%d ", *arr++);
    fputc('\n', stdout);
}

int main()
{
    srand((unsigned)time(NULL));

    int arr_sort[arrsize];

    // generate random array
    for (int i = 0; i < arrsize; ++i)
        arr_sort[i] = 1 + rand() % 99;
    print_arr(arr_sort, arrsize);

    // sort the array
    merge_sort(arr_sort, arrsize);
    print_arr(arr_sort, arrsize);
}

示例输出

16 81 73 86 87 66 14 93 19 13 62 32 70 56 29 88 20 21 7 27 70 46 72 42 95 83 24 2 5 43 67 79 8 18 82 39 81 56 56 45
2 5 7 8 13 14 16 18 19 20 21 24 27 29 32 39 42 43 45 46 56 56 56 62 66 67 70 70 72 73 79 81 81 82 83 86 87 88 93 95

希望对您有所帮助。

在 C 中的合并排序程序中实现冒泡排序时出错

Error in implementing bubble sorting in a merge sort program in C

c

sorting

algorithm

mergesort

array-merge