Quicksort 实现不在 C 中排序

Question

我尝试用 C 编写快速排序实现已经 2 天了，但它不起作用。我的意思是，它确实可以编译，但输出不是我所期望的。

我一直在学习一本数据结构的书，它被翻译成葡萄牙语了，我的母语，无论如何......我将在下面将说明与我的代码一起传递。

QuickSort Image Partition Image

//
//  Quick sort V2.c
//  IFTM Exercises
//
//  Created by Lelre Ferreira on 7/9/19.
//  Copyright © 2019 Lelre Ferreira. All rights reserved.
//

#define size 5
#include <stdio.h>

void printfArrays(int *array);
void receiveArray(int *array);
int QuickSortPartition(int *array, int begin, int end);
void QuickSortFunction(int *array, int begin, int end);


int main (int argc, const char * argv[]){

    int array[size];

    receiveArray(array);
    printfArrays(array);

    return 0;
}

void receiveArray(int* array){

    int i = 0;
    for (i = 0; i < size; i++) {
        printf("Insert value of [%d]: ", i);
        scanf("%d", &array[i]);
    }
}

void printfArrays(int *array){

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

int QuickSortPartition(int *array, int begin, int end){


    int pivot = array[end];
    int i = (begin - 1), j = 0;

    for (j = begin; j <= end - 1; j++) {
        if (array[j] <= pivot) {
            i++;
            array[i] = array[j];
        }
    }
    array[i + 1] = array[end];
    return (i + 1);
}

void QuickSortFunction(int *array, int begin, int end){

    if (begin < end) {
        int pivot = QuickSortPartition(array, begin, end);
        QuickSortPartition(array, begin, pivot - 1);
        QuickSortPartition(array, pivot + 1, end);
    }

}

Answer 1

编写函数后，在将其用于程序之前对其进行测试。

函数QuickSortPartition显然是错误的。

在您的函数实现中考虑以下演示程序

#include <stdio.h>

int QuickSortPartition(int *array, int begin, int end){


    int pivot = array[end];
    int i = (begin - 1), j = 0;

    for (j = begin; j <= end - 1; j++) {
        if (array[j] <= pivot) {
            i++;
            array[i] = array[j];
        }
    }
    array[i + 1] = array[end];
    return (i + 1);
}

int main( void )
{
    int a[] = { 5, 4, 2, 1, 3 };
    const size_t N = sizeof( a ) / sizeof( *a );

    for ( size_t i = 0; i < N; i++ ) printf( "%d ", a[i] );
    putchar( '\n' );

    QuickSortPartition( a, 0, ( int )( N - 1 ) );

    for ( size_t i = 0; i < N; i++ ) printf( "%d ", a[i] );
    putchar( '\n' );
}

它的输出是

5 4 2 1 3 
2 1 3 1 3

您需要在函数中交换值，而不是使用简单的赋值。例如

#include <stdio.h>

size_t QuickSortPartition( int *array, size_t begin, size_t end )
{
    const int pivot = array[end];

    size_t i = begin - 1;

    for ( size_t j = begin; j < end; j++ ) 
    {
        if ( array[j] <= pivot ) 
        {
            int tmp = array[++i];
            array[i] = array[j];
            array[j] = tmp;
        }
    }

    int tmp = array[++i];
    array[i] = array[end];
    array[end] = tmp;

    return i;
}

int main( void )
{
    int a[] = { 5, 4, 2, 1, 3 };
    const size_t N = sizeof( a ) / sizeof( *a );

    for ( size_t i = 0; i < N; i++ ) printf( "%d ", a[i] );
    putchar( '\n' );

    size_t partition = QuickSortPartition( a, 0, N - 1 );

    printf( "%zu: ", partition );
    for ( size_t i = 0; i < N; i++ ) printf( "%d ", a[i] );
    putchar( '\n' );
}

它的输出是

5 4 2 1 3 
2: 2 1 3 4 5

对于索引，我使用了 size_t 类型（你也应该这样做）而不是 int.

类型

并且在函数 QuickSortFunction 中你需要调用它本身而不是函数 QuickSortPartition.

void QuickSortFunction(int *array, size_t begin, size_t end){

    if (begin < end) {
        size_t pivot = QuickSortPartition(array, begin, end);
        QuickSortFunction(array, begin, pivot - 1);
        QuickSortFunction(array, pivot + 1, end);
    }

}

在函数声明中考虑到这个初始化QuickSortPartition

int i = (begin - 1), j = 0;
        ^^^^^^^^^^^

不好。（似乎每个人都从一个坏例子中复制了算法：））。当所有元素都小于或等于 pivot 的值时，该函数效率低下。

您也可以编写一个单独的函数来交换数组的两个元素。

下面有一个演示程序，展示了如何改进函数 QuickSortPartition 的代码。

#include <stdio.h>

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

size_t QuickSortPartition( int *array, size_t begin, size_t end )
{
    const int pivot = array[end];

    size_t i = begin;

    for ( size_t j = begin; j < end; j++ ) 
    {
        if ( array[j] <= pivot ) 
        {
            if ( i != j ) swap( &array[i], &array[j] );
            ++i;
        }
    }

    if ( i != end ) swap( &array[i], &array[end] );

    return i;
}

int main( void )
{
    int a[] = { 5, 4, 2, 1, 3 };
    const size_t N = sizeof( a ) / sizeof( *a );

    for ( size_t i = 0; i < N; i++ ) printf( "%d ", a[i] );
    putchar( '\n' );

    size_t partition = QuickSortPartition( a, 0, N - 1 );

    printf( "%zu: ", partition );
    for ( size_t i = 0; i < N; i++ ) printf( "%d ", a[i] );
    putchar( '\n' );
}

Answer 2

有两处错误：

您永远不会调用排序函数。
一旦你修复了（1），你会发现你的分区函数完全坏了。您正在尝试使用 Lomuto partition scheme，但它与应有的任何地方都不匹配。

无论您对 (2) 的算法执行何种翻译，都是错误的。始终在末尾选择固定枢轴的 Lomuto 分区的一般算法（一个糟糕的选择，但这超出了这个问题的范围）如下：

更新分区函数

// added to make the partition algorithm easier to understand.
void swap_int(int *a, int *b)
{
    int tmp = *a;
    *a  = *b;
    *b = tmp;
}

int QuickSortPartition(int *array, int begin, int end){

    int i=begin, j;

    for (j = begin; j <= end; j++)
    {
        if (array[j] < array[end])
            swap_int(array+j, array + i++);
    }
    swap_int(array+i, array+end);

    return i;
}

此处 i 表示枢轴值最终将驻留的活动槽。最初，枢轴存储在 array[end]。 for-loop 扫描完成后，i 位于最终交换将放置枢轴的位置。它也是函数的 return 值，调用者使用它来表示 而不是 包含在以后的递归中（因为它的值已经是 home）。

最终结果如下所示：

#include <stdio.h>

void printfArrays(int *array);
void receiveArray(int *array);
int QuickSortPartition(int *array, int begin, int end);
void QuickSortFunction(int *array, int begin, int end);

#define size 5

int main (int argc, const char * argv[]){

    int array[size];

    receiveArray(array);
    QuickSortFunction(array, 0, size-1);
    printfArrays(array);

    return 0;
}

void receiveArray(int* array){

    int i = 0;
    for (i = 0; i < size; i++) {
        printf("Insert value of [%d]: ", i);
        scanf("%d", array+i);
    }
}

void printfArrays(int *array){

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

static void swap_int(int *a, int *b)
{
    int tmp = *a;
    *a  = *b;
    *b = tmp;
}

int QuickSortPartition(int *array, int begin, int end){

    int i=begin, j;

    for (j = begin; j <= end; j++)
    {
        if (array[j] < array[end])
            swap_int(array+j, array + i++);
    }
    swap_int(array+i, array+end);

    return i;
}

void QuickSortFunction(int *array, int begin, int end){

    if (begin < end) {
        int pivot = QuickSortPartition(array, begin, end);
        QuickSortFunction(array, begin, pivot - 1);
        QuickSortFunction(array, pivot + 1, end);
    }
}

输入

 4 1 3 5 2

输出

Value sorted: 1
Value sorted: 2
Value sorted: 3
Value sorted: 4
Value sorted: 5

这段代码中有多个其他不相关的东西可以明智地解决（检查 IO，更好的枢轴选择方案，例如 median-of-three，等等.)，但基本问题已在上面解决。

Answer 3

谢谢大家！我修复了之前代码中的问题，最后我用 while 制作了另一个代码，我将两者都留在这里。

//
//  Quick sort V2 fixed.c
//  IFTM Exercises
//
//  Created by Lelre Ferreira on 7/11/19.
//  Copyright © 2019 Lelre Ferreira. All rights reserved.
//

#define size 5
#include <stdio.h>

void printArray(int *array);
void receiveArray(int *array);

void QuickSwap(int* a, int* b);
void QuickSort(int *array, int begin, int end);
int  QuickSortPartition(int *array, int begin, int end);

int main (int argc, const char * argv[]){

    int array[size];

    receiveArray(array);
    QuickSort(array, 0, size-1);
    printArray(array);

    return 0;
}

void printArray(int *array){

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

void receiveArray(int *array){

    int i = 0;
    for (i = 0; i < size; i++) {
        printf("Insert value of [%d]: ", i);
        scanf("%d", &array[i]);
    }
}

void QuickSwap(int* a, int* b){

    int x = *a;
    *a = *b;
    *b = x;
}

void QuickSort(int *array, int begin, int end){

    if (begin < end) {
        int pivot = QuickSortPartition(array, begin, end);
        QuickSort(array, begin, pivot - 1);
        QuickSort(array, pivot + 1, end);
    }
}

int QuickSortPartition(int *array, int begin, int end){

    int pivot = array[end];
    int i = begin - 1, j = 0;

    for (j = begin; j <= end - 1; j++) {
        if (array[j] <= pivot) {
            i++;
            QuickSwap(&array[i], &array[j]);
        }
    }
    QuickSwap(&array[i + 1], &array[j]);
    return (i + 1);
}

第二个版本：

//
//  Quick sort V1.c
//  IFTM Exercises
//
//  Created by Lelre Ferreira on 7/8/19.
//  Copyright © 2019 Lelre Ferreira. All rights reserved.
//

#define size 5
#include <stdio.h>

void printArray(int *array);
void QuickSortFunction(int *array, int begin, int end);
int QuickSortPartition(int *array, int begin, int end);

int main (int argc, const char * argv[]){

    int array[] = {2, 3, 1, 5, 4};

        QuickSortFunction (array, 0, size-1);
        printArray(array);

    return 0;
}

void printArray(int* array){

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

int QuickSortPartition(int *array, int begin, int end){

    int left, right;
    int pivot, aux;

    right = end;
    left = begin;
    pivot = array[begin];

    while (left < right) {
        while (array[left] <= pivot)
            left++;
        while (array[right] > pivot)
                right--;
                if (left < right) {
                    aux = array[left];
                    array[left] = array[right];
                    array[right] = aux;
                }
            }

            array[begin] = array[right];
            array[right] = pivot;
            return right;
}

void QuickSortFunction(int *array, int begin, int end){

    if (begin < end) {
        int pivot = QuickSortPartition(array, begin, end);
        QuickSortFunction(array, begin, pivot - 1);
        QuickSortFunction(array, pivot + 1, end);
    }
}

Quicksort 实现不在 C 中排序

Quicksort implementation not sorting in C

c

arrays

sorting

partitioning

quicksort