Я пытался реализовать трехстороннюю быструю сортировку в C, но безуспешно. Я пробовал это на бумаге, и, по логике, это работает, но на самом деле это не так. Это работает для некоторых входов (я предоставлю несколько из них ниже), но просто не с другими. Я пытался отследить проблему, но это становится трудным, как только ввод становится немного больше. Любая обратная связь приветствуется.
ПРИМЕЧАНИЕ: первая строка ввода - это размер массива. Остальные запрашиваемые числа являются элементами в массиве.
Код
#include <time.h>
#include <stdlib.h>
#include <stdio.h>
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
int partition(int a[], int left, int px, int right, int *pivotregionlen) {
int i = left-1;
int k = left-1;
//swap(&a[px], &a[right]);
int pivot = a[px];
for(size_t j = left; j < right; j++) {
if(a[j] == pivot) {
k++;
swap(&a[k], &a[j]);
}
if(a[j] < pivot) {
i++;
swap(&a[j], &a[i]);
k++;
//swap(&a[j], &a[k]); -- I FEEL like this should be here, but with this it gives even weirder outputs
}
}
swap(&a[k+1], &a[right]);
*pivotregionlen = k - i;
return i+1;
}
void quicksort( int a[], int left, int right, int size ) {
int pivot, pivotIdx;
if( left < right ) {
pivotIdx = right;//(rand() % (right-left+1)+left);
int pivreglen = 0;
pivot = partition(a, left, pivotIdx, right, &pivreglen);
quicksort(a, left, pivot-1, size);
quicksort(a, pivot+pivreglen+1, right, size);
}
}
int read(int **a, int *len) {
int i;
scanf("%d", len);
if(*len <= 0) return 1;
*a = (int *) malloc(*len * sizeof(int));
if(*a == NULL) return 1;
for( i = 0; i < *len; i++ )
scanf("%d", (*a)+i);
return 0;
}
int main() {
int i, n, *A;
if( read(&A, &n)) return 1;
srand(time(NULL));
quicksort(A, 0, n-1, n);
for( i = 0; i < n; i++ )
printf("%d ", A[i]);
return 0;
}
Входные данные, с которыми он работает
3 // number of elements
3
2
1
----
5
1
-1
3
2
1
----
10
10
9
8
1
2
3
4
5
6
7
Однако я должен проверить программу на этот вход: https://pastebin.com/Mxmz6Sae
Сведенные данные - 1001 число
1000 104 257 826 88 380 -168 295 -972 259 -72 -419 817 -35 886 -562 -102 -467
713 603 -107 694 122 537 47 149 -106 -632 383 464 221 1000 854 556 834 -31 989
-271 465 332 -753 -902 467 -458 -361 298 233 137 -972 -554 -486 871 -3 459 677
894 -879 43 453 -491 -906 941 -104 159 -746 333 838 334 772 719 -577 -685 -28
-985 41 897 139 166 349 492 454 101 -34 -544 734 -434 -95 -191 68 -993 828 86
581 -505 -177 -436 112 -524 -454 -277 -147 72 292 496 686 541 849 559 -686 597
-165 -234 136 -677 -377 -362 -745 -430 -80 779 -971 -78 -379 62 -887 -378 -364
-518 -911 -880 57 674 461 339 241 282 40 207 190 -400 572 500 -83 -811 -183 643
450 -449 258 -258 -464 360 77 -156 -816 -759 161 156 774 626 -550 -165 586 -172
211 804 381 -821 -504 26 -115 -253 -569 700 931 30 790 -117 369 -182 -201 232
876 -634 -902 -269 -708 -979 344 -456 -782 457 81 475 273 -183 190 893 627 -770
-531 -541 206 383 -269 471 -689 154 163 264 -695 -331 -361 -278 487 555 195 664
-686 -351 -106 644 728 12 5 -477 -529 -368 -464 86 -942 -45 -31 -117 291 52 333
567 -923 -910 -372 -5 -256 -422 65 -412 950 815 572 562 893 -34 -394 -10 578
-793 -598 940 555 -495 516 320 -214 785 -257 -433 -925 460 327 756 -181 -400 732
371 -228 380 -782 558 990 -141 -70 -594 -889 -333 290 -409 -207 661 -877 500
-790 284 109 901 -696 11 -79 -864 714 977 736 -147 -820 -266 636 364 628 903 933
-135 89 -587 362 964 174 47 735 -794 -113 -2 712 651 242 -690 82 -92 -640 216
155 -450 502 -363 722 258 -149 -599 394 -274 753 95 -942 914 -402 904 740 -998
-424 -743 153 -871 96 678 920 -153 -134 795 -425 108 310 216 -739 568 -698 645
293 981 -950 -568 -291 580 338 -348 293 -567 346 -353 -389 15 778 53 -856 -528
-883 -705 723 404 511 697 180 -643 983 -497 366 -280 467 371 -498 -820 512 -855
211 -483 374 -860 -487 135 753 -458 593 439 380 50 -854 -52 -657 -595 842 838
116 99 -486 -489 -959 -821 548 -219 -737 -139 160 195 972 408 -785 192 200 -372
-395 -127 -562 258 257 378 -204 471 391 155 -399 -169 -242 714 -68 -914 -689
-162 -156 -600 976 740 796 -168 34 78 -846 203 -1 419 -450 -189 -210 -698 338
921 532 -180 -573 -597 357 359 385 -520 232 -7 816 -879 -6 919 -196 -688 -444
266 429 178 -446 629 -741 -307 560 -236 -893 637 462 -966 311 307 -411 -636 -665
-454 731 777 -406 663 320 876 34 -79 -246 -939 254 -505 76 689 716 -32 -976 928
948 -214 891 -350 -454 437 509 300 -748 -469 -762 -566 417 468 856 -642 774 899
890 150 561 835 137 -794 -196 897 -161 457 816 -47 318 -634 -173 -804 744 -60
-914 548 -850 102 703 -764 819 1 77 -649 -310 74 -159 -762 -355 33 871 721 119
335 -796 274 -182 122 423 -436 -910 186 440 -988 -103 43 -462 -556 265 878 963
-718 -409 809 405 250 260 -310 332 -925 -366 -478 -752 324 687 -621 710 137 -711
798 188 417 -520 505 -254 -239 928 504 855 -640 -782 655 704 936 -366 87 844
-159 619 -938 -869 -540 275 235 577 -849 -82 -373 -68 -818 978 -863 643 309 -684
-145 -886 970 472 -899 177 -581 195 -290 -926 -443 -768 -222 -632 -327 -703 909
713 914 867 759 -356 851 564 -365 214 -765 700 803 -378 -271 -178 215 807 -769
998 -555 -614 -738 31 -271 321 -203 771 -743 156 922 -739 100 -129 -258 612 -502
936 -915 123 632 -521 690 -492 434 192 854 -182 543 962 772 -930 67 -850 -830
538 -538 888 -724 -874 -452 -235 -362 367 439 961 857 -868 14 939 -87 -570 429
-399 445 332 121 -933 -951 435 -193 -917 512 123 20 -526 697 -663 884 -961 786
565 49 -198 507 314 -55 -365 -923 -515 876 938 662 -271 -173 258 348 -884 375
-458 877 307 526 31 -370 -283 976 748 -211 -808 -149 965 964 127 -249 101 -909
102 641 -924 960 -316 3 315 -693 255 -471 -699 133 472 -403 908 591 -714 792 499
-369 -680 -186 -707 421 -167 -740 -612 -504 -475 960 394 588 -13 827 739 -902
714 -487 347 352 317 -458 -388 860 -188 53 381 -856 647 814 4 908 566 -274 -582
714 290 707 687 802 -464 -486 486 -920 -66 -128 -422 950 -955 -933 507 -805 -126
-912 463 851 -3 338 -475 -311 -216 -58 379 -195 20 -196 -41 -430 -279 644 496
221 890 -489 932 -712 573 -503 -207 140 -337 -286 -740 -980 619 -985 -621 135
479 351 -824 -424 -576 209 -250 187 458 -861 -664 -206 746 -962 -176 704 -334
523 203 822 653 -449 -938 286 -429 237 -635 163 -447 700 504 -615 938 767 865
862 -670 356 -974 -501 621 -580 -904 -279 -727 531 -340 5 -813 -685 370 932 1000
303 -726 -699 -182 1 -328 -10 -927 -541 -546 -642 -568 -998 739 -696 506 370 889
-668 -508 24 -34 -652 832 93 91 369 407 76 -734 -239 970 -783 -229 222 10 295
-581 -719 -452 460 686 832 -963
К которым он должен вывод: https://pastebin.com/hDdx8HaB
Но вместо этого выводит: https://pastebin.com/yRneMiDz
Я даже не знаю, как отследить проблему с помощью ввода это большое, и я не могу понять, как это работает с меньшими входами, но не с этим. Поверьте мне, я пытаюсь выследить проблему в течение нескольких часов.
Любая помощь высоко ценится.