Quicksort实现及打印函数编写求助：代码开发遇阻求指导

Hey there! Let's work through your Quicksort and printing challenges together. I've put together a complete, heavily annotated code example that fixes the core sorting logic and solves your printing confusion, with clear markers for common pitfalls you might have run into.

Complete Annotated Quicksort Code #

#include <stdio.h>

// Helper function to swap two elements in the array
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// ✅ Core partition function: Finds the correct position for the pivot element
int partition(int arr[], int low, int high) {
    // We'll use the last element as our pivot (you can also pick a random element to avoid worst-case performance)
    int pivot = arr[high];
    // `i` tracks the end of the subarray where elements are smaller than the pivot
    int i = low - 1;

    // Iterate through all elements except the pivot
    for (int j = low; j <= high - 1; j++) {
        // If current element is <= pivot, move it to the smaller elements region
        if (arr[j] <= pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    // Place the pivot in its final sorted position
    swap(&arr[i + 1], &arr[high]);
    // Return the pivot's index to split the array for recursion
    return i + 1;
}

// ✅ Full Quicksort recursive function
void quicksort(int arr[], int low, int high) {
    // Base case: if low >= high, the subarray has 0 or 1 element (already sorted)
    if (low < high) {
        // Get the pivot's final position
        int pivotIndex = partition(arr, low, high);
        // Recursively sort the left subarray (elements smaller than pivot)
        quicksort(arr, low, pivotIndex - 1);
        // Recursively sort the right subarray (elements larger than pivot)
        quicksort(arr, pivotIndex + 1, high);
    }
}

// ✅ Array printing function (solves your printing confusion)
void printArray(int arr[], int size) {
    printf("Array elements: ");
    // Loop through every element to print
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    // Optional optimization to remove trailing space:
    // if (size > 0) {
    //     printf("%d", arr[0]);
    //     for (int i = 1; i < size; i++) printf(" %d", arr[i]);
    // }
    // printf("\n");
}

int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int arrSize = sizeof(arr) / sizeof(arr[0]);

    printf("Original ");
    printArray(arr, arrSize);

    // ❌ Common mistake: Passing `arrSize` instead of `arrSize - 1` as high index (causes out-of-bounds access)
    quicksort(arr, 0, arrSize - 1);

    printf("Sorted ");
    printArray(arr, arrSize);

    return 0;
}

Key Fixes & Explanations #

• Core Quicksort Logic:

  • ❌ A common pitfall is forgetting that the partition function must return the pivot's final index—this is how we split the array into smaller subarrays for recursion. Without this, the recursive calls can't target the right segments.
  • ❌ Another frequent error is incorrect boundary values in the quicksort call (like using the array length instead of length - 1 for the high index), which leads to accessing memory outside the array.
  • ✅ The partition function works by grouping elements smaller than the pivot to the left, then placing the pivot in its correct sorted spot.

• Printing Function:

  • ❌ If you were confused about formatting, the printArray function keeps it simple: it adds a descriptive label, loops through each element, and ends with a newline for clean output.
  • ✅ The optional commented-out code fixes the trailing space issue if that's something you care about—print the first element separately, then add a space before every subsequent element.

• Swap Helper:

  • ✅ Using pointers in the swap function ensures we modify the original array, not a local copy. This is essential for the sorting changes to persist.

内容的提问来源于stack exchange，提问作者bartb