c - Quicksort C - 有点不同的版本

Question

代码确实运行了。这是我正在研究的快速排序的一个不同版本。我遇到了一些主要问题。首先，它将数组中的第一个元素打印为 n:例如(如果您设置 n = 3，即使您将数组中的第一个元素设置为 1，它仍然会打印出 3 作为第一个元素)。此外，当您打印出排序后的版本时，它实际上并没有改变任何东西。

n = 3 的示例输入，

设置值 = 8、7、6

初始输出将等于 3 , 7 , 6

最终输出将等于 3 , 7 , 6

(输出应该是 6 , 7 , 8)

我一直无法在网上找到任何与我的代码相似的代码，所以这可能是新的东西!谢谢。

//preprocessor directives and header files
#include <stdio.h>
#define MAX_ARRAY_SIZE 50

//function prototypes separated by data types
void print_array( int array[], int n );              // Print out the array values
void swap( int array[], int index1, int index2 );    // Swap two array elements. 
void quicksort( int array[], int low, int high );    // Sorting algorithm

int populate_array( int array[] );                  // Fill array with values from user.
int partition( int array[], int low, int high );    // Find the partition point (pivot)

//the main function 
int main(void)
{
    int array[MAX_ARRAY_SIZE];
    //set n = to size of user created size of array

    int n = populate_array(&array[MAX_ARRAY_SIZE]);
    //print the original array to the screen
    print_array(&array[MAX_ARRAY_SIZE], n );
    //perform the algorithm
    quicksort(array, 0, n-1);

    printf("The array is now sorted:\n");
    print_array(&array[MAX_ARRAY_SIZE], n);
    return 0;
}
// *array and array[] are the same...
int populate_array(int array[])
{
    int n = -1;
    printf("Enter the value of n > ");
    scanf("%d", &n);

    if(n > MAX_ARRAY_SIZE)
    {
        printf("%d exceeds the maximum array size. Please try again.\n\n", n);
        populate_array( &array[MAX_ARRAY_SIZE]);
    }
    else if(n < 0)
    {
        printf("%d is less than zero. Please try again.\n\n", n);
        populate_array( &array[MAX_ARRAY_SIZE]);
    }
    else if(n == 0)
    {
        printf("%d Array of size 0? Please don't try this, and... Please try again.\n\n", n);
        populate_array( &array[MAX_ARRAY_SIZE]);
    }
    else
    {
        for(int i = 0; i < n; i++)
            scanf("%d", &array[i]);
    }
    printf("The initial array contains: \n");
    return n;
}

void print_array(int array[], int n)
{

    for(int i = 0; i < n; i++)
        printf("%+5d\n", array[i]);


}

void quicksort(int array[], int low, int high)
{

    if (low < high)
    {
        /* pivot is partitioning index, array[p] is now
           at right place */
        int pivot = partition(array, low, high);

        // Separately sort elements before
        // partition and after partition
        quicksort(array, low, pivot - 1);
        quicksort(array, pivot + 1, high);
    }

}

int partition(int array[], int low, int high)
{
    int pivot = array[high];

    int i = low;
    for (int j = low; j <= high- 1; j++)
    {
        // If current element is smaller than or
        // equal to pivot
        if (array[j] <= pivot)
        {
            swap(array, i, j);
            i = i +1;
        }
    }
    swap(array, i, high);
    return i;
}

void swap(int array[], int index1, int index2)
{
    int temp = array[index1];
    array[index1] = array[index2];
    array[index2] = temp;

}

Answer 1

这是一个评论很多的答案。我对代码做了相当大的改动。

现在这是一个用于用户输入的功能齐全的快速排序数组。

我之前遇到的问题是 &array[MAX_ARRAY_SIZE]。这需要改为仅“数组”。 &array[MAX_ARRAY_SIZE] 试图访问超出数组实际大小的内存位置。

把它改成just "array"意味着它正在访问数组中的第一个元素。(如果错误请更正)

我还将填充数组函数更改为一个健壮的 do-while 循环。而不是尝试重新调用其自身内部的函数。 do-while 循环只允许您更改“n”的值。

/*
Author: Zachary Alberda
*/
//preprocessor directives and header files
#include <stdio.h>
#define MAX_ARRAY_SIZE 50

//function prototypes separated by data types
void print_array( int array[], int n );              // Print out the array values
void swap( int array[], int index1, int index2 );    // Swap two array elements. 
void quicksort( int array[], int low, int high );    // Sorting algorithm

int populate_array( int array[] );                  // Fill array with values from user.
int partition( int array[], int low, int high );    // Find the partition point (pivot)

//the main function 
int main(void)
{
    int array[MAX_ARRAY_SIZE]; //set n = to size of user created size of array

    int n = populate_array(array); //print the original array to the screen

    print_array(array, n ); //print array of size n 

    quicksort(array, 0, n-1); //perform the algorithm low is 0, high is size of array -1.

    printf("The array is now sorted:\n");//Inform user that the array is sorted.

    print_array(array, n);//print the sorted array

    return 0; // exit without errors.
}
// *array and array[] are the same...
int populate_array(int array[])
{

    int n = -1;//initialize variable n(local variable to function populate_array)
    printf("Enter the value of n > ");//inform user of what to input
    scanf("%d", &n);

    /*
        CHECK IF N IS VALID 


        This is a robust do while loop!

        1) Performs the if-statements while 'n' is not valid in a do-while loop.
         -The reason I do this is because it will cause errors
            if the if-statements are individual without the do-while loop.
        2)The program will not crash if you try different combinations
            of inputs for 'n'. :) 
        3)Checks if user input is > MAX_ARRAY_SIZE
        4)Checks if user input is < 0
        5)Checks if user input is == 0
    */
    do
    {
        if(n > MAX_ARRAY_SIZE)
        {
            printf("%d exceeds the maximum array size. Please try again.\n\n", n);
            printf("Enter the value of n > ");
            scanf("%d", &n);
        }
        else if(n < 0)
        {
            printf("%d is less than zero. Please try again.\n\n", n);
            printf("Enter the value of n > ");
            scanf("%d", &n);
        }
        else if(n == 0)
        {
            printf("%d Array of size 0? Please don't try this, and... Please try again.\n\n", n);
            printf("Enter the value of n > ");
            scanf("%d", &n);
        }
    }while(n <= 0 || n > MAX_ARRAY_SIZE);

    //scan in array if user input is valid 
    for(int i = 0; i < n; i++)
        scanf("%d", &array[i]);

    printf("The initial array contains: \n");//Inform user of initial array

    return n;
}

void print_array(int array[], int n)
{
//print array in pre/post order before and after the algorithm.
    for(int i = 0; i < n; i++)
        printf("%+5d\n", array[i]);


}

void quicksort(int array[], int low, int high)
{

    if (low < high)
    {
        /* pivot is partitioning index, array[pivot] is now
           at right place */
        int pivot = partition(array, low, high);

        // Separately sort elements before
        // partition and after partition
        quicksort(array, low, pivot - 1);
        quicksort(array, pivot + 1, high);
    }

}

int partition(int array[], int low, int high)
{
    int pivot = array[high];

    int i = low;

    for (int j = low; j <= high- 1; j++)
    {
        // If current element is smaller than or
        // equal to pivot
        if (array[j] <= pivot)
        {
            swap(array, i, j);
            i = i +1;
        }
    }
    swap(array, i, high);
    return i;
}

void swap(int array[], int index1, int index2)
{
    //swap positions of array index 1 and 2 
    int temp = array[index1];
    array[index1] = array[index2];
    array[index2] = temp;

}