Merhaba
http://www.algolist.net/Algorithms/Sorting/Quicksort adresinden aldığım kodu std::qsort() biçimine çevirmek istiyorum. Aslında tam aynısı olmayacaktır. Zaten amacım benzer parametrelere uyarlamaktı. std::qsort() struct'daki verileri işleyebildiği (void pointer parametre olarak kullanarak) ve compare fonksiyonunu parametre olarak aldığı için mesela std::strcmp() çalıştırabiliyoruz.
Aslında kod normal olarak bazen çalışıyor, ben array'ı void olarak alıp pointer aritmetik yaptığımda bazı array input'larından doğru sıralama yapmıyor. Bazı input'lar doğru sıralanıyor. Input olarak Rasgele numara üretip array'a diziyorum ve dediğim gibi. gdb kullandım fakat işin içinden çıkamadım. Örneğin rasgele ürettirdiğim int array'ı sıralamasını istedim.
myqsort.cpp
#include <iostream>
#include <cstdlib>
// original
void quickSort(int arr[], int left, int right) {
int i = left, j = right;
int tmp;
int pivot = arr[(left + right) / 2];
/* partition */
while (i <= j) {
while (arr[i] < pivot)
i++;
while (arr[j] > pivot)
j--;
if (i <= j) {
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
i++;
j--;
}
};
/* recursion */
if (left < j)
quickSort(arr, left, j);
if (i < right)
quickSort(arr, i, right);
}
int qsortCompare(const void *param1, const void *param2) {
int number1 = *(int *) param1;
int number2 = *(int *) param2;
return number1 - number2;
}
// Forward Declaration
static void myqsortpart(void *array, size_t size, int left, int right,
int (*compar)(const void *param1, const void *param2));
void myqsort(void *array, size_t nMembers, size_t size,
int (*compar)(const void *param1, const void *param2))
{
int left = 0;
int right = nMembers - 1;
myqsortpart(array, size, left, right, compar);
}
static void myqsortpart(void *array, size_t size, int left, int right,
int (*compar)(const void *param1, const void *param2))
{
int i = left, j = right;
int pivot = (right + left) / 2;
void *pivotptr = (void *) ((char *) array + pivot * size);
/* partition */
while (i <= j)
{
while ((*compar)((void *) ((char *) array + i * size), pivotptr) < 0)
i++;
while ((*compar)((void *) ((char *) array + j * size), pivotptr) > 0)
j--;
if (i <= j)
{
// swap operation
char *ptr1 = NULL, *ptr2 = NULL;
ptr1 = (char *) array + i * size;
ptr2 = (char *) array + j * size;
size_t size2;
size2 = size;
do
{
char tmp = *ptr1;
*ptr1 = *ptr2;
*ptr2 = tmp;
ptr2++;
ptr1++;
--size2;
}
while (size2 > 0);
i++;
j--;
}
}
if (left < j)
myqsortpart(array, size, left, j, compar);
if (i < right)
myqsortpart(array, size, i, right, compar);
}
void printArray(int *array, int nElems)
{
for (int i = 0; i < nElems; i++)
std::cout << array[i] << ' ';
std::cout << std::endl;
}
int main(void)
{
int array[] = { 18, 20, 7, 3, 9, 14, 4, 18, 11, 5, 16, 15, 14, 18, 18, 7, 20, 10, 4, 18 };
int arraySize = sizeof(array) / sizeof(array[0]);
int *arrayMyqsort = new int[arraySize];
int *arrayQsort = new int[arraySize];
int *arrayQuicksort = new int[arraySize];
for (int i = 0; i < arraySize; i++)
{
arrayMyqsort[i] = array[i];
arrayQsort[i] = array[i];
arrayQuicksort[i] = array[i];
}
std::qsort(arrayQsort, arraySize, sizeof(array[0]), qsortCompare);
quickSort(arrayQuicksort, 0, arraySize - 1);
myqsort(arrayMyqsort, arraySize, sizeof(array[0]), qsortCompare);
std::cout << "array : " << std::endl;
printArray(array, arraySize);
std::cout << "qsort() : " << std::endl;
printArray(arrayQsort, arraySize);
std::cout << "quicksort() : " << std::endl;
printArray(arrayQuicksort, arraySize);
std::cout << "myqsort() : " << std::endl;
printArray(arrayMyqsort, arraySize);
delete[] arrayMyqsort;
delete[] arrayQsort;
delete[] arrayQuicksort;
}
Alıntı:
>array :
18 20 7 3 9 14 4 18 11 5 16 15 14 18 18 7 20 10 4 18
qsort() :
3 4 4 5 7 7 9 10 11 14 14 15 16 18 18 18 18 18 20 20
quicksort() :
3 4 4 5 7 7 9 10 11 14 14 15 16 18 18 18 18 18 20 20
myqsort() :
3 4 4 5 7 9 11 14 18 7 10 14 15 16 18 18 18 18 20 20
Örneğin şunu da doğru sıralamıyor. 2, 20, 18, 11, 18, 9, 20, 14, 1, 7, 17, 19, 2, 6, 13, 5, 16, 8, 5, 14
Rasgele sayı üretip (20 elemanlı array için 1-20'ye kadar sayılar) int array oluşturuyorum. void pointer'ı char pointer'a cast'leyip hareket ettiriyorum(pointer aritmetik) olmuyor farklı sonuç üretiyor.
Tahmin ediyorum pointer aritmetik'de bir sorun var. Çünkü myqsort() quickSort() arasındaki fark pointer aritmetik kullanışım.quickSort() doğru sıralıyor ve fakat myqsort() sıralaması input array'a göre yanlış olabiliyor.
--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]