时间戳

首页 > 解决方案 > C 中的 QuickSort 实现似乎随机跳过了一些运行

c - C 中的 QuickSort 实现似乎随机跳过了一些运行

问题描述

我正在以 C 语言实现快速排序作为练习。我认为我处于一个相当不错的位置，因为我对为什么我的代码有时似乎不调用 QuickSort 的第一次调用感到困惑。

主程序


#include <stdlib.h>

#include <time.h>

#include "quicksort.h"
#include "utils.h"

//----------------------------------------

void main(int argc, char* argv[]) {
    unsigned int SIZE;
    int* numbers;
    
    if (argc > 1) {
        SIZE = argc-1;
        numbers = (int*) malloc(sizeof(unsigned int) * SIZE);
        if (numbers == NULL) { exit(1); }
        
        for (unsigned int i = 0; i < SIZE; i++) {
            numbers[i] = atoi(argv[i+1]);
        }
    } else {
        SIZE = 100;
        numbers = (int*) malloc(sizeof(unsigned int) * SIZE);
        if (numbers == NULL) { exit(1); }
        
        srandom(time(NULL));
        
        for (int i = 0; i < SIZE; i++) {
            numbers[i] = (random() % 60000) - 30000;    // Random numbers between (-30000, 30000)
        }
    }
    printf("Array filled!\n");

    quicksort(numbers, 0, SIZE-1);
    printf("%s\n", isSorted(numbers, SIZE) ? "Sorted!" : "Not sorted!");

    free(numbers);
    printf("Memory released\n");

    exit(0);
}

快速排序.c

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

#include "quicksort.h"
#include "utils.h"

//----------------------------------------

unsigned int partition(int* const array, const unsigned int low, const unsigned int high) {
    const int pivot = array[(unsigned int)((low + high)/2)];
    unsigned int i = low;
    unsigned int j = high;
    
    while (1) {
        while (array[i] < pivot) { i += 1; }
        while (pivot < array[j]) { j += -1; }
        if (i == j) { return i; }
        swap(array+i, array+j);
    }
}

void quicksort(int* const array, const unsigned int low, const unsigned int high) {
    unsigned int pivot = partition(array, low, high);
    printf(".");

    // We only want to recurse if there at least two elements to order.
    //  Otherwise we simply don't recurse on the subarray because one element is in order with itself.
    if (low+1 < pivot) { quicksort(array, low, pivot-1); }
    if (pivot+1 < high) { quicksort(array, pivot+1, high); }
}

实用程序.c

#include <stdio.h>

#include "utils.h"

//----------------------------------------

void print_array(int* const array, const unsigned int size) {
    printf("%d", array[0]);
    for (unsigned int i = 1; i < size; i++) {
        printf(" %d", array[i]);
    }
    printf("\n");
}

void swap(int* a, int* b) {
    const int temp = *a;
    *a = *b;
    *b = temp;
}

unsigned short isSorted(int* const array, const unsigned int size) {
    for (int i = 0; i < size-1; i++) {
        if (array[i] > array [i+1]) {
            return 0;
        }
    }
    
    return 1;
}

问题是有时第一次调用 quicksort() 会运行，我可以在终端上看到每个调用的点。有时它会卡住，我什至看不到一个点。

我真的很困惑，因为这是一个随机错误，我什至不知道如何开始调试它。

这是一个总是卡住的特殊实例。

./main -22167 -8962 -12961 -8232 -1118 -22237 -7872 -8654 15744 -28388 -12088 402 17865 3515 -10380 -1672 -6731 24435 14161 14906 -21791 -9593 -2111 -1323 6065 1955 -23011 17216 29229 -8988 21034 -22938 -11598 14425 -24818 -6364 -1460 -2689 14983 -15716 -24725 9247 -8962 23141 -17238 -12989 27821 -17616 -18554 11982 27290 26008 -27611 -28468 -5315 -15194 -20161 -21974 -27977 -20932 -24610 -591 22483 -29856 20186 27665 -6219 25078 -28672 15116 -20638 -23396 -5637 -23247 6097 -16523 -6236 3918 -4139 5210 22252 29504 -22430 994 7388 -21393 15800 17227 -13367 -5825 2647 28375 -64 -28518 28520 26474 5500 28653 21552 6828

标签： crecursionrandomquicksort

解决方案

分区方案和快速排序中有不少错误。

正确版本： quicksort.c

unsigned int partition(int* const array, const unsigned int low, const unsigned int high) {
    const int pivot = array[(unsigned int)((low + high)/2)];
    long i = (long)low - 1;
    long j = (long)high + 1;
    
    while (1) {
        do { i += 1; } while (array[i] < pivot);
        do { j += -1; } while (pivot < array[j]);
        if (i >= j) { return j; }
        swap(array+i, array+j);
    }
}

void quicksort(int* const array, const unsigned int low, const unsigned int high) {
    if (low < high) {
        unsigned int pivot = partition(array, low, high);

        quicksort(array, low, pivot);
        quicksort(array, pivot+1, high);
    }
}

推荐阅读