选择排序中动态数组和指针的问题

Question

我使用动态数组和指针制作了一个选择排序程序，但是在运行这段代码之后，我发现如果我们给出 4 和 6 之类的大小输入，则数组正在排序，但如果大小输入就像 5 和 7 等...我也在此之前使用相同的指针和动态数组技术编写了冒泡排序程序，但它在所有条件下都给出了完美的排序数组，我也尝试调试代码但仍然没有不明白为什么会这样，如果有人对此有想法，请帮助我。

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

int main()
{
  int * ptr,temp,min;
  int size,i,j,s;
  printf("Enter the size of array:");
  scanf("%d",&size);

  ptr = (int *)(calloc (size,sizeof(int)));

  if(ptr == NULL)
    printf("No memory");

  else
  {
    printf("\n=== RANDOM ELEMENTS OF ARRAY ===\n");

    for(s=0;s<size;s++)
      *(ptr+s) = rand()%100;

    for(s=0;s<size;s++)
      printf("\nElement [%d]  = %d ",s,*(ptr+s));

// selection sort algorithm

  for(i=0;i< size-1;i++)
  {
    min = i;
    for(j=i+1;j<size;j++)
    {
      if(*(ptr+j) < *(ptr+min))
      {
        min = j;
      }
      temp = *(ptr+i);
      *(ptr+i) = *(ptr+min);
      *(ptr+min) = temp;
    }
  }

// End of algorithm

    printf("\n\n=======  SORTED ELEMENTS  =======\n\n");
      for(s=0;s<size;s++)
        printf("Element [%d]  = %d \n",s,*(ptr+s));


  }

}

Answer 1

您的 Selection Sort 算法似乎有误。内部for循环完成迭代后，您必须将当前索引中的元素替换为最小值：

  for(i=0;i< size-1;i++)
  {
    min = i;
    for(j=i+1;j<size;j++)
    {
      if(*(ptr+j) < *(ptr+min))
      {
        min = j;
      }
    }
    temp = *(ptr+i);
    *(ptr+i) = *(ptr+min);
    *(ptr+min) = temp;
  }

现在，它应该适用于所有输入尺寸。

Answer 2

清除一些不必要的混淆因素...

*(ptr + index)

等同于

ptr[index]

但第二个更容易阅读。

接下来，在下面的部分中引入变量min，

  if(*(ptr+j) < *(ptr+min))
  {
       min = j;
  }

...但不是简单排序所必需的。只需坚持使用 i 和 j，排序将对偶数或奇数组正确进行。最后，为了消除内存泄漏，当不再需要 ptr 时调用 free(ptr);。以下是经过更正的清理版本。

int main(void)//added void
{
  int * ptr,temp/*,min*/;
  int size,i,j,s;
  printf("Enter the size of array:");
  scanf("%d",&size);

  ptr = calloc (size,sizeof(int));//casting is required in C++ 
                                  //but unnecessary in C.
                                  //(and can be problematic)
  if(ptr == NULL)
  {
    printf("No memory");
  }
  else
  {
    printf("\n=== RANDOM ELEMENTS OF ARRAY ===\n");

    for(s=0;s<size;s++)
      ptr[s] = rand()%100;

    for(s=0;s<size;s++)
      printf("\nElement [%d]  = %d ",s,ptr[s]);

// selection sort algorithm

    for(i=0;i< size-1;i++)
    {
        for(j=i+1;j<size;j++)//removed if section introducing 'min'
        {
            if(ptr[j] < ptr[i])
            {
                temp = ptr[i];
                ptr[i] = ptr[j];
                ptr[j] = temp;
            }
        }
    }

// End of algorithm

    printf("\n\n=======  SORTED ELEMENTS  =======\n\n");
    for(s=0;s<size;s++)
        printf("Element [%d]  = %d \n",s,*(ptr+s));

   free(ptr);
  }
  return 0;//added 
}

顺便说一句，这是用大小 == 3 和

测试的

  ptr[0] = 3;
  ptr[1] = 2;
  ptr[2] = 1;

以及其他几个随机值的奇数和偶数

选择排序中动态数组和指针的问题

problem with dynamic array and pointers in selection sort

c

arrays

sorting

pointers

dynamic-arrays