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ı:

Ö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. ]

Çok uğraştım ama hatayı bulamadım. :/

Ali

--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]

Pointer aritmetik'de bir yanlışlık yok. Problem şu ki pivotptr'daki değer while döngüsüne giriyor. i ve j index'leri bazen pivot'a rastlayıp pivotu değiştirebiliyor. Algoritmayı bozuyorlar. Anladığım kadarıyla while'da test edilirken pivot değerin değişmeyip bir yerde tutulması gerekli. Pivot'u bir yerlere kopyalamak sorunu çözüyor. Sadece fonksiyonun değişmiş halini buraya kopyalıyorum:

static void myqsortpart(void *array_base, size_t size, int left, int right,
   int (*compar)(const void *param1, const void *param2))
{
 void *array = (void *) array_base;
 int i = left, j = right;
 int tmp2;
 int pivot = (right + left) / 2;
 void *pivotval = new char[size];
 void *pivotptr = (void *) (((char *) array) + pivot * size);
 std::memcpy(pivotval, pivotptr, size); // nasılsa temporary value new ve memcpy() iş görüyor

 /* partition */
 while (i <= j)
 {
   while ((*compar)((void *) ((char *) array + i * size), pivotval) < 0)
     i++;
   while ((*compar)((void *) ((char *) array + j * size), pivotval) > 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_base, size, left, j, compar);
 if (i < right)
   myqsortpart(array_base, size, i, right, compar);
 delete[] static_cast<char *>(pivotval); // nedense g++ warning: deleting ‘void*’ is undefined diye bir mesaj yolladı. cast yaptım mesaj silindi.
}

pivotval'i new ile allocate ettim. Bu arada başka bir yerde de sordum aynı kodu. Ben bunu çözdükten sonra sorduğum soruyu cevaplayan bir kişi(ingilizce bir sitede) alloca() kullanabileceğimi belirtmiş. Bu da bir not olsun.

void pointer'ı delete yaparken cast yapmak neden onu anlayamadım. Zaten bir yerlerde allocate kayıdı tutuluyor bildiğim kadarıyla. Yoksa standard'da mı bu konu hakkında bir şey mi var. Fazladan cast mantıksız geldi. int * da castleyebilirdim değil mi? Oldukça saçma. D dilinde void pointer delete edildiğinde cast yapmak gerekiyor mu?

--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]

Alıntı (ota):

Mantıklı! :) Pivot elemanın bir yerden bir yere taşınması partition adımı açısından normal ama değeri kaybetmemek gerek.

Alıntı:

new (ve malloc vs.) yavaş işlemlerdir. alloca kullandığın zaman bellek, dinamik bellekten değil, çağrı yığıtından ayrılır. (Sanki doğrudan 'int pivotval;' yazmışsın gibi.) O yüzden de fazla büyük bellek için kullanılamaz.

Alıntı:

delete, iki iş yapar: sonlandırıcı işlevi çağırır ve belleği geri verir. Tür void* olunca, asıl türün ne olduğu bilinmediğinden sonlandırıcı işletilemez. (delete[] ise sonlandırıcıyı her eleman için işletir; kaç eleman olduğunu aşağıda söylediğin gibi, "bir yerlerde" tuttuğu bilgiden bilir.)

Ama C++ programlarında artık new ve delete kullanmıyoruz; onun yerine vector vs. gibi kendi kaynaklarını kendileri idare eden türler kullanıyoruz. Örneğin, bu programda new[] kullanmaya gerek yok. Ek olarak, şablon kullansan türün ne olduğu bilindiğinden değiş tokuş işlemlerini de 'swap(a, b)' diye yaparsın ve elemanların hızlı swap işlemleri varsa zaten o kullanılır. Ama biliyorum, burada amacın algoritmayı öğrenmek; bu konulara dikkat etmek değil.

Ali

--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]