誰能告訴我在這個偽代碼Quicksort & Partition之后的這個通用快速排序代碼中我做錯了什么，該演算法有效，因為我已經通過將int陣列傳遞給quicksortand函式來僅使用整數而不使用比較函式partition，但我有試圖讓它同時適用于int和 字串。在這段代碼中，我只測驗了int值，但代碼不起作用，輸出是陣列的初始值，對于字串來說，我得到與輸出相同的初始陣列。我評論了字串部分，因為它們的排序方式與整數相同。這是作業的整數代碼整數作業代碼：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//prototipi delle funzioni
typedef int (*compare_function)(const void *, const void *);
void generic_quicksort(void *v, int i, int f, size_t size, compare_function compare);
void generic_swap(void *a, void *b, size_t size);
int generic_partition(void *v, int i, int f, size_t size, compare_function compare);
void print_int_array(const int *array, size_t len) {
size_t i;
for (i = 0; i < len; i )
printf("%d | ", array[i]);
putchar('\n');
}
//funzione di confronto
int compare_int(const void *, const void *);
int compare_str(const void *a, const void *b) {
const char **ia = (const char **)a;
const char **ib = (const char **)b;
return strcmp(*ia, *ib);
/* strcmp functions works exactly as expected from
comparison function */
}
void print_cstring_array(char **array, size_t len) {
size_t i;
for (i = 0; i < len; i )
printf("%s | ", array[i]);
putchar('\n');
}
int main() {
int v[] = { 5, 4, 3, 2, 1 };
char *strings[] = { "Zorro", "Alex", "Celine", "Bill", "Forest", "Dexter" };
int n = sizeof(v) / sizeof(int);
print_int_array(v, n);
generic_quicksort((void *)v, 0, n - 1, sizeof(int), compare_int);
print_int_array(v, n);
/*
int s = sizeof(strings) / sizeof(*char);
print_cstring_array(strings, s);
generic_quicksort((void *)strings, 0, s - 1, sizeof(*char), compare_str);
print_cstring_array(strings, s);
*/
return 0;
}
int compare_int(const void *a, const void *b) {
return *((int*)a) - *((int*)b);
}
void generic_quicksort(void *v, int i, int f, size_t size, int (*comp)(const void *, const void *)) {
if (i >= f)
return;
int p = generic_partition(v, i, f, size, comp);
generic_quicksort(v, i, p - 1, size, comp);
generic_quicksort(v, p 1, f, size, comp);
}
void generic_swap(void *a, void *b, size_t size) {
void *tmp = malloc(size);
memcpy(tmp, a, size);
memcpy(a, b, size);
memcpy(b, tmp, size);
free(tmp);
}
int generic_partition(void *v, int i, int f, size_t size, int (*comp)(const void *, const void *)) {
void *x = malloc(size);
int k, j;
memcpy(x, v (i * size), size);
k = i - 1;
for (j = i; j <= f - 1; j ) {
if (comp(v (j * size), x) <= 0) {
k ;
generic_swap(v (k * size), v (j * size), size);
}
}
generic_swap(v ((k 1) * size), v (f * size), size);
free(x);
return (k 1);
}
uj5u.com熱心網友回復：
代碼中存在多個問題：
int n = sizeof(v) / sizeof(int);是有風險的：關于v. 你應該寫int n = sizeof(v) / sizeof(*v);傳遞切片的第一個和最后一個元素的索引的約定在 C 中是令人困惑的并且不是慣用的，您應該傳遞第一個元素的索引和最后一個元素之后的元素的索引。這允許無符號索引型別和空陣列。
v (j * size)使用void指標演算法，這是并非在所有系統上都可用的擴展。unsigned char為此使用指標。整數的比較函式對于較大的絕對值具有未定義的行為，因為減去它們可能會導致算術溢位。你應該改用這個：
int compare_int(const void *a, const void *b) { int ia = *(const int *)a; int ib = *(const int *)b; return (ia > ib) - (ia < ib); }generic_swap使用malloc和memcpy。這會導致小元素的開銷很大，您應該使用一個簡單的回圈：void generic_swap(void *a, void *b, size_t size) { unsigned char *pa = (unsigned char *)a; unsigned char *pb = (unsigned char *)b; while (size-- > 0) { unsigned char c = *pa; *pa = *pb; *pb = c; } }參考中的
generic_partition使用最后一個元素作為樞軸，但您x從第一個元素進行初始化。你應該寫memcpy(x, v (f * size), size);。這是導致失敗的原因。當前代碼可能會巧合地適用于該int版本。使用第一個或最后一個元素作為樞軸會導致排序陣列出現最壞情況。
這是修改后的版本：
#include <stdio.h>
#include <string.h>
//prototipi delle funzioni
typedef int (*compare_function)(const void *, const void *);
void generic_quicksort(void *v, int i, int f, size_t size, compare_function compare);
//funzione di confronto
int compare_int(const void *a, const void *b) {
int ia = *(const int *)a;
int ib = *(const int *)b;
return (ia > ib) - (ia < ib);
}
int compare_str(const void *a, const void *b) {
const char *sa = *(const char * const *)a;
const char *sb = *(const char * const *)b;
return strcmp(sa, sb);
}
void print_int_array(const int *array, size_t len) {
size_t i;
if (len > 0) {
printf("%d", array[0]);
for (i = 1; i < len; i )
printf("| %d", array[i]);
}
putchar('\n');
}
void print_cstring_array(const char * const *array, size_t len) {
size_t i;
if (len > 0) {
printf("%s", array[0]);
for (i = 1; i < len; i )
printf(" | %s", array[i]);
}
putchar('\n');
}
static void generic_swap(void *a, void *b, size_t size) {
unsigned char *pa = (unsigned char *)a;
unsigned char *pb = (unsigned char *)b;
while (size-- > 0) {
unsigned char c = *pa;
*pa = *pb;
*pb = c;
}
}
static int generic_partition(void *v, int i, int f, size_t size,
int (*comp)(const void *, const void *))
{
unsigned char *p = (unsigned char *)v;
int j, k = i;
// using first element as pivot
for (j = i 1; j < f; j ) {
if (comp(p j * size, p i * size) <= 0) {
k ;
generic_swap(p k * size, p j * size, size);
}
}
/* swap the pivot to the end of the left part */
generic_swap(p i * size, p k * size, size);
return k;
}
void generic_quicksort(void *v, int i, int f, size_t size,
int (*comp)(const void *, const void *))
{
if (f > i 1) {
int p = generic_partition(v, i, f, size, comp);
generic_quicksort(v, i, p, size, comp);
generic_quicksort(v, p 1, f, size, comp);
}
}
int main() {
int v[] = { 5, 4, 3, 2, 1 };
int n = sizeof(v) / sizeof(*v);
const char *strings[] = { "Zorro", "Alex", "Celine", "Bill", "Forest", "Dexter" };
int s = sizeof(strings) / sizeof(*strings);
print_int_array(v, n);
generic_quicksort((void *)v, 0, n, sizeof(*v), compare_int);
print_int_array(v, n);
print_cstring_array(strings, s);
generic_quicksort((void *)strings, 0, s, sizeof(*strings), compare_str);
print_cstring_array(strings, s);
return 0;
}
請注意，選擇第一個或最后一個元素作為樞軸會導致排序陣列的最壞情況復雜性。的遞回深度generic_quicksort將是陣列的長度，可能會導致堆疊溢位。
這是一個修改后的版本，可以防止這種情況，但在排序陣列上仍然具有二次時間復雜度：
void generic_quicksort(void *v, int i, int f, size_t size,
int (*comp)(const void *, const void *))
{
while (f > i 1) {
int p = generic_partition(v, i, f, size, comp);
if (p - i < f - p) {
generic_quicksort(v, i, p, size, comp);
i = p 1;
} else {
generic_quicksort(v, p 1, f, size, comp);
f = p;
}
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/463572.html