用C语言编写合并排序伪代码过程 [英] Writing Merge Sort Pseudo-Code Procedure in C

问题描述

我一直在尝试算法简介，并一直在尝试实施使用C编程语言的MERGE-SORT算法可以更好地理解它.

I have been going through Introduction to Algorithms, and have been trying to implement the MERGE-SORT algorithm in C programming language to gain a better understanding of it.

这本书提出了两个伪代码:

The book presents two pseudo-codes:

和

虽然我确实了解上述过程，但是在实施过程中我一定会遗漏一些东西.

While I do understand the above procedures, I must be missing something during the implementation.

我必须从伪代码中丢失一些东西，但还不能弄清楚.关于为什么发生这种情况的任何建议，将不胜感激.

I must be missing something from the pseudo-code but cannot figure it out yet. Any suggestions as to why this is happening would be appreciated.

更新了代码和输出

/* C program for Merge Sort */
#include<stdlib.h>
#include<stdio.h>

void MERGE(int [], int , int , int );
void printArray(int [], int );
void MERGE_SORT(int [], int , int );

int main(void)
{
   int A[] = { 12, 11, 13, 5, 6, 7, 2, 9 };
   int arr_size = sizeof(A) / sizeof(A[0]);

   printf("Given array is \n");
   printArray(A, arr_size);

   MERGE_SORT(A, 0, arr_size); //Fixed: Index to start from zero

   printf("\nSorted array is \n");
   printArray(A, arr_size);

   return 0;
}

void MERGE(int A[], int p, int q, int r)
{
   int i = 0;
   int j = 0;
   int n1 = q - p + 1;                  //Computing length of sub-array 1
   int n2 = r - q;                      //Computing length of sub-array 2
   int *L = malloc((n1 + 2) * sizeof(*L + 1));        //Creating Left array
   int *R = malloc((n2 + 2) * sizeof(*R + 1));        //Creating Right array

   for (int i = 0; i <= n1; i++) { //Fixed: <=, i start from 0
       L[i] = A[p + i - 1];
   }
   for (int j = 0; j <= n2; j++) { //Fixed: <=, i start from 0
       R[j] = A[q + j];
   }

   L[n1 + 1] = 99;  //Placing Sentinel at the end of array
   R[n2 + 1] = 99;

   i = 1;
   j = 1;

   /*Prior to the first iteration k = p, so the subarray is empty.
   Both L[i] and R[j] are the smallest elements of their arrays and have not
   been copied back to A*/
   for (int k = p; k <= r; k++) { //Fixed: <=
       if (L[i] <= R[j]) {
           A[k] = L[i];
           i++;
       }
       else { //Fixed: Assignment and not condition check for A[k]
           A[k] = R[j];
           j++;
       }
   }

   free(L);
   free(R);
}

void MERGE_SORT(int A[], int p, int r)
{
   //During first iteration p = 1 & r = 8
   if (p < r) {
       int q = (p + r) / 2;
       MERGE_SORT(A, p, q);
       MERGE_SORT(A, q + 1, r);
       MERGE(A, p, q, r);
   }
}

/* Function to print an array */
void printArray(int Arr[], int size)
{
   int i;
   for (i = 0; i < size; i++)
       printf("%d ", Arr[i]);
   printf("\n");
}

推荐答案

查看伪代码，发现有些东西被错误地写错了.
1.您需要注意数组索引从0或1开始
2.在for循环中合并最后一部分实际上是分配，而不是条件检查.

Looked in the pseudo code and found out that some things have been mistakenly written wrong.
1. You need to be careful with the array index to start from 0 or 1
2. Merge last part in for loop is actually an assignment instead for conditional check.

已更新代码以解决错误Stack around the variable A was corrupted

Have updated the code to fix for the error Stack around the variable A was corrupted

请在此处找到更正的代码(请注意//修复问题)

Please find the corrected code here(Lookout for //Fixed for fixes)

/* C program for Merge Sort */
#include<stdlib.h>
#include<stdio.h>

void MERGE(A, p, q, r);
void printArray(Arr, size);
void MERGE_SORT(A, p, r);

int main(void)
{
   int A[] = { 12, 11, 13, 5, 6, 7, 2, 9 };
   int arr_size = sizeof(A) / sizeof(A[0]);

   printf("Given array is \n");
   printArray(A, arr_size);

   MERGE_SORT(A, 0, arr_size - 1); //Fixed: Index to start from zero, arr_size - 1

   printf("\nSorted array is \n");
   printArray(A, arr_size);

   return 0;
}

void MERGE(int A[], int p, int q, int r)
{
   int i = 0;
   int j = 0;
   int n1 = q - p + 1;                  //Computing length of sub-array 1
   int n2 = r - q;                      //Computing length of sub-array 2
   int *L = malloc((n1+1) * sizeof(*L+1));          //Creating Left array
   int *R = malloc((n2+1) * sizeof(*R+1));          //Creating Right array
   for (int i = 0; i < n1; i++) { //Fixed: i start from 0
       L[i] = A[p + i];

   }
   // int arr_size = sizeof(A) / sizeof(A[0]);
   for (int j = 0; j < n2; j++) { //Fixed: j start from 0
       R[j] = A[q + j + 1];

   }

   L[n1] = 99;  //Placing Sentinel at the end of array
   R[n2] = 99;

   i = 0; //Fixed: i and j to start from 0
   j = 0;

   /*Prior to the first iteration k = p, so the subarray is empty.
   Both L[i] and R[j] are the smallest elements of their arrays and have not
   been copied back to A*/
   for (int k = p; k <= r; k++) { //Fixed: <=
       if (L[i] <= R[j]) {
           A[k] = L[i];
           i++;
       }
       else { //Fixed: Assignment and not condition check for A[k]
        A[k] = R[j];
        j++;
       }
   }

   free(L);
   free(R);
}

void MERGE_SORT(int A[], int p, int r)
{
   //During first iteration p = 1 & r = 8
   if (p < r) {
       int q = (p + r) / 2;
       MERGE_SORT(A, p, q);
       MERGE_SORT(A, q + 1, r);
       MERGE(A, p, q, r);
   }
}

/* Function to print an array */
void printArray(int Arr[], int size)
{
   int i;
   for (i = 0; i < size; i++)
       printf("%d ", Arr[i]);
   printf("\n", size);
}

希望有帮助.
如有任何疑问，请回复.

Hope it helps.
Revert for any doubts.

这篇关于用C语言编写合并排序伪代码过程的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！