C Lang：快速排序5个元素，但不排序10个元素

Question

我对为什么代码只对5个元素而不对10个元素进行排序感到困惑。我在与教授进行办公室访问时向我介绍了这种方法。所以我在编写代码时遵循了他的指示。有人可以帮我解决这个问题吗？我的代码可以工作，但是不能在更大的数组上工作。我知道有人在到期之前提供帮助已经为时已晚，但是我只想了解我在这段代码中所做的事情。

谢谢

/* Homework3.c
Qucksort arrays
Jared DaRocha
3/1/2020

 */


#include <stdio.h>// preprocessor 

int partition(int arr[], int first, int end);// function declaration

void quickSort(int arr[], int first, int end);// function declaration

int main(void)// beginning of main

{
    //Data
    int array[5];// creates an array of 5 elements
    int size = sizeof(array) / sizeof(array[0]); // calculates size of the array


    // prompt user to input data to input int the array
    printf("Enter 5 numbers to add in the array");
    // prompts user to input 10 numbers
    for(int i =0;i<size; i++)
    {
      scanf("%d", &array[i]);// stores user-defined data into the array
    }


    // call the function to sort the array
    quickSort(array, 0, size -1);


    // prints array 
    for (int i = 0; i < size; i++)
    {
        printf("%d ", array[i]);
    }
    printf("\n");

    return 0;
}


int partition(int arr[], int low, int high)// Function declaration
{
    //Data
    int partition = arr[low]; // partition number


        // infinite for loop
        for (;;)
        {
          // decrement high while partition is smaller than element of high
            while(partition <arr[high]) 
            {

              high--;


            }


            // if partition is greater than element of high, swap high with low element since low element is the pivot
            if(partition > arr[high]){
              int temp = arr[low];

              arr[low] = arr[high];
              arr[high] = temp;
              low++;

            }           
            // increment low while partition is greater than element of low
            while(partition > arr[low])
            {

              low++;

            }

            // swap low and next element in the right if  partition is less than element of low
            if(partition < arr[low])
            {
              int temp = arr[low];
              arr[low] = arr[low+1];
              arr[low+1] = temp;
            }

            // if low is same as high then  exit loop
            if(high == low)
            {
              break;
            }


    }


    return low;
}

void quickSort(int arr[], int first, int end) // function definition
{
    if (first < end) 
    {
        int partitionIndex = partition(arr, first, end);
        quickSort(arr, first, (partitionIndex - 1));
        quickSort(arr, (partitionIndex+1 ), end);
    }
}

`

Answer 1

如果检查算法快速排序，您会发现如何将数组划分为两个不重叠的切片，而且也不会留下单个元素。您只需在两个切片之间执行此操作，就剩下一个元素。您将数组分为两个切片，一个数组元素不参与对其他切片的递归调用..那是不正确的。您知道的是，下层切片的所有元素都小于标记，其余元素都大于或等于标记...但是分割点可以是数组子部分中与之对应的任何元素。

顺便说一下，代码或分区是完全不正确的。首先选择一个将用作标记的元素，可以将其选择为数组的任何元素或所有元素的平均值，这没关系……您不会将其放入数组中。然后从数组下的结尾元素开始搜索，并从标记上的开始元素开始搜索，一旦有一对这样的对，将它们切换，但是将找到的元素与标记交换，这不仅不会执行预期的操作，但是引入令牌的副本（并更改其值），这将破坏您的数组。

[您不是在寻找数组元素...您正在寻找一个位置（在相邻元素之间），该位置用于划分数组，子数组将从beg到pos-1，从pos到末尾， （或从beg到pos，然后从pos + 1到末尾），但不要忽略中心元素，因为您知道它属于数组，但这不是令牌的必要。