C ile hızlı sıralama algoritması

[Erdem]

C ile hızlı sıralama algoritmasını quicksort nasıl yazardınız?

[mufitsozen]

#include <stdlib.h>
void qsort( void *buf, size_t num, size_t size, int (*compare)(const void *, const void *) );


yada

/*
 *
 *  This file is part of
 *	MakeIndex - A formatter and format independent index processor
 *
 *  This file is public domain software donated by
 *  Nelson Beebe (beebe@science.utah.edu).
 *
 */

/*
 * qsort.c: Our own version of the system qsort routine which is faster by an
 * average of 25%, with lows and highs of 10% and 50%. The THRESHold below is
 * the insertion sort threshold, and has been adjusted for records of size 48
 * bytes. The MTHREShold is where we stop finding a better median.
 */

/* #include <stdio.h> -- mkind.h includes this */
#include    "mkind.h"		       /* only for type declarations */

#define THRESH  4		       /* threshold for insertion */
#define MTHRESH 6		       /* threshold for median */

static int qsz;			       /* size of each record */
static int thresh;		       /* THRESHold in chars */
static int mthresh;		       /* MTHRESHold in chars */

static int	(*qcmp) ARGS((char*,char*)); /* the comparison routine */
static void	qst ARGS((char *base, char *max));
/*
 * qqsort: First, set up some global parameters for qst to share.  Then,
 * quicksort with qst(), and then a cleanup insertion sort ourselves.  Sound
 * simple? It's not...
 */

void
#if STDC
qqsort(char *base, int n, int size, int (*compar) ARGS((char*,char*)))
#else
qqsort(base, n, size, compar)
char   *base;
int     n;
int     size;
int     (*compar) ARGS((char*,char*));
#endif
{
    register char *i;
    register char *j;
    register char *lo;
    register char *hi;
    register char *min;
    register char c;
    char   *max;

    if (n <= 1)
	return;
    qsz = size;
    qcmp = compar;
    thresh = qsz * THRESH;
    mthresh = qsz * MTHRESH;
    max = base + n * qsz;
    if (n >= THRESH) {
	qst(base, max);
	hi = base + thresh;
    } else {
	hi = max;
    }
    /*
     * First put smallest element, which must be in the first THRESH, in the
     * first position as a sentinel.  This is done just by searching the
     * first THRESH elements (or the first n if n < THRESH), finding the min,
     * and swapping it into the first position.
     */
    for (j = lo = base; (lo += qsz) < hi;) {
	if ((*qcmp) (j, lo) > 0)
	    j = lo;
    }
    if (j != base) {		       /* swap j into place */
	for (i = base, hi = base + qsz; i < hi;) {
	    c = *j;
	    *j++ = *i;
	    *i++ = c;
	}
    }
    /*
     * With our sentinel in place, we now run the following hyper-fast
     * insertion sort. For each remaining element, min, from [1] to [n-1],
     * set hi to the index of the element AFTER which this one goes. Then, do
     * the standard insertion sort shift on a character at a time basis for
     * each element in the frob.
     */
    for (min = base; (hi = min += qsz) < max;) {
	while ((*qcmp) (hi -= qsz, min) > 0);
	if ((hi += qsz) != min) {
	    for (lo = min + qsz; --lo >= min;) {
		c = *lo;
		for (i = j = lo; (j -= qsz) >= hi; i = j)
		    *i = *j;
		*i = c;
	    }
	}
    }
}



/*
 * qst: Do a quicksort.  First, find the median element, and put that one in
 * the first place as the discriminator.  (This "median" is just the median
 * of the first, last and middle elements).  (Using this median instead of
 * the first element is a big win). Then, the usual partitioning/swapping,
 * followed by moving the discriminator into the right place.  Then, figure
 * out the sizes of the two partions, do the smaller one recursively and the
 * larger one via a repeat of this code.  Stopping when there are less than
 * THRESH elements in a partition and cleaning up with an insertion sort (in
 * our caller) is a huge win. All data swaps are done in-line, which is
 * space-losing but time-saving. (And there are only three places where this
 * is done).
 */

static void
#if STDC
qst(char *base, char *max)
#else
qst(base, max)
char   *base;
char   *max;
#endif
{
    register char *i;
    register char *j;
    register char *jj;
    register char *mid;
    register int ii;
    register char c;
    char   *tmp;
    int     lo;
    int     hi;

    lo = (int)(max - base);		/* number of elements as chars */
    do {
	/*
	 * At the top here, lo is the number of characters of elements in the
	 * current partition.  (Which should be max - base). Find the median
	 * of the first, last, and middle element and make that the middle
	 * element.  Set j to largest of first and middle.  If max is larger
	 * than that guy, then it's that guy, else compare max with loser of
	 * first and take larger.  Things are set up to prefer the middle,
	 * then the first in case of ties.
	 */
	mid = i = base + qsz * ((unsigned) (lo / qsz) >> 1);
	if (lo >= mthresh) {
	    j = ((*qcmp) ((jj = base), i) > 0 ? jj : i);
	    if ((*qcmp) (j, (tmp = max - qsz)) > 0) {
		/* switch to first loser */
		j = (j == jj ? i : jj);
		if ((*qcmp) (j, tmp) < 0)
		    j = tmp;
	    }
	    if (j != i) {
		ii = qsz;
		do {
		    c = *i;
		    *i++ = *j;
		    *j++ = c;
		} while (--ii);
	    }
	}
	/* Semi-standard quicksort partitioning/swapping */
	for (i = base, j = max - qsz;;) {
	    while (i < mid && (*qcmp) (i, mid) <= 0)
		i += qsz;
	    while (j > mid) {
		if ((*qcmp) (mid, j) <= 0) {
		    j -= qsz;
		    continue;
		}
		tmp = i + qsz;	       /* value of i after swap */
		if (i == mid) {	       /* j <-> mid, new mid is j */
		    mid = jj = j;
		} else {	       /* i <-> j */
		    jj = j;
		    j -= qsz;
		}
		goto swap;
	    }
	    if (i == mid) {
		break;
	    } else {		       /* i <-> mid, new mid is i */
		jj = mid;
		tmp = mid = i;	       /* value of i after swap */
		j -= qsz;
	    }
    swap:
	    ii = qsz;
	    do {
		c = *i;
		*i++ = *jj;
		*jj++ = c;
	    } while (--ii);
	    i = tmp;
	}
	/*
	 * Look at sizes of the two partitions, do the smaller one first by
	 * recursion, then do the larger one by making sure lo is its size,
	 * base and max are update correctly, and branching back. But only
	 * repeat (recursively or by branching) if the partition is of at
	 * least size THRESH.
	 */
	i = (j = mid) + qsz;
	if ((lo = (int)(j - base)) <= (hi = (int)(max - i))) {
	    if (lo >= thresh)
		qst(base, j);
	    base = i;
	    lo = hi;
	} else {
	    if (hi >= thresh)
		qst(i, max);
	    max = j;
	}
    } while (lo >= thresh);
}

[Erdem]

Söylemeyi unutmuşum. Hazır işlevler kulanmadan kendimiz nasıl yazardık.

[Tagli]

Wikipedia'da güzel anlatmış. Animasyon falan da var.
http://en.wikipedia.org/wiki/Quicksort

JFWI 

[Erdem]

Buradaki amacım yorumlamalı dillerin olanakları ile C olanaklarını ve yazım şeklini karşılaştırmak. O yüzden başkalarının çözümlerini merak ediyorum.

Lütfen kendi yazdığınız çözümleri paylaşın arkadaşlar, başka bir yerden alınmış kod olmasın.

Hızlı sıralama algoritmasının nasıl çalıştığını bilmeyen arkadaşlar varsa anlatabilirim.

[fatih6761]

Bir uygulamada gerekti şöyle bir şey yazmıştım:

#define xchange(a, b) a ^= b ^= a ^= b;

void bsort(int *a, int count)
{
	#pragma omp parallel for
	for(int i = 0; i < count; i++)
	{
		for(int j = 0; j < count - 1; j++)
		{
			if(a[j] > a[j+1])
				xchange(a[j], a[j+1]);
		}
	}
}

Tabi bu bubble sort sıralama. Ve sadece tamsayılaır sıralıyor. Şu şekilde geliştirebiliriz:

#define xchange(a, b) a ^= b ^= a ^= b;

void bsort(int *a, int count, int (*compare)(const void *, const void *))
{
	#pragma omp parallel for
	for(int i = 0; i < count; i++)
	{
		for(int j = 0; j < count - 1; j++)
		{
			if(compare(a[j], a[j+1]))
				xchange(a[j], a[j+1]);
		}
	}
}

Burada da compare fonksiyonu biraz daha farklı oluyor. Qsort takinden farklı. Ama şimdi onu uygulamaya üşendim açıkçası Burada bsort bubble sort anlamında. Ayrıca Vikipedi de programlama konusunda güzel örnekler ve animasyonlar var. Bütün sıralama algoritmalarını araştırdım, animasyonlar çok yardımcı oldu...

[Erdem]

#define xchange(a, b) a ^= b ^= a ^= b;

Burada derleyici şu şekilde bir uyarı verdi:

UYARI: '*(a + (unsigned int)((unsigned int)j * 4u))' ifadesinde işlem tanımsız olabilir [-Wsequence-point]

Bazı derleyici uyarılarını hata olarak yorumlayabiliriz.

Fatih C++ için makrolardan uzak durun, göstergeleri kullanmayın diye yararlı öğütler var. C için de böyle mi bilmiyorum ama.

if (x != y) *x^=*y^=*x^=*y

şeklindeki kullanım C için tanımsız davranış çünkü soldaki x değerini 2 kere değiştiriyor.

Aslında bu yerdeğiştirme işlevinin XOR kullanan versiyonu şu şekilde:

void yerDegistir(int * a, int * b)
{
    *a ^= *b;
    *b ^= *a;
    *a ^= *b;
}

Ama burada a ve b aynı adresi gösteriyorsa gene de bu işlev hatalı çalışır. İlk XOR her iki değişken tarafından işaret edilen bitleri  temizler.

Ayrıca bu yöntem bu işlemi yapmanın akıllı yolu olarak bilinir. Ama tam tersine modern işlemcilerde derleyici en iyileştirme yapamadığı için daha yavaş çalışır.

Geçici değişken kullanan ve derleyicinin en iyileştirme yapabildiği yöntem ise şu şekilde:

void yerDegistir(int * a, int * b)
{
    int gecici = *a;
    *a = *b;
    *b = gecici;
}

   #pragma omp parallel for

Burada da böyle bir uyarı aldım:

UYARI: ignoring #pragma omp parallel [-Wunknown-pragmas]

Programı derlerken for döngüsünün C99 standartlarına uyması için  -std=c99 seçeneği ile derledim.

#include <stdio.h>

#define xchange(a, b) a ^= b ^= a ^= b;

void bsort(int *a, int count)
{
    #pragma omp parallel for
    for(int i = 0; i < count; i++)
    {
        for(int j = 0; j < count - 1; j++)
        {
            if(a[j] > a[j+1])
                xchange(a[j], a[j+1]);
        }
    }
}

int main()
{
    int sayilar[] = {8, 3, 25, 6, 10, 17, 1, 2, 18, 5};
    const int uzunluk = sizeof(sayilar) / sizeof(int);

    for (int i = 0; i < uzunluk; ++i) {
        printf("%d ", sayilar[i]);
    }

    printf("\n");

    bsort(sayilar, uzunluk);

    for (int i = 0; i < uzunluk; ++i) {
        printf("%d ", sayilar[i]);
    }
}

Programın çıktısı :

8 3 25 6 10 17 1 2 18 5
0 0 0 0 0 0 0 0 8 25

Çıktıdan görüleceği üzere program derlenirken hata vermese de XOR satırı yüzünden körlemesine değişiklik yapıyor ve hatalı çalışıyor.

[fatih6761]

Ben sadece programın bir kesitini verdim. xchange 'in hem fonksiyon halinde, hem makro halinde 2-3 tane daha farklı uygulanması var. Bu kodu bubble sort uygulamasını göstereyim diye yazdım. Elbette kodu alıp iyileştirme ile kullanırsanız hatalar çıkar. Bu kodu qsort a alternatif olsun diye yazmadım. Sadece ürettiğim rastgele sayı dizisini sıralamak için kullandım. VC++ derleyicisiyle kodun tamamı gayet güzel çalışıyor. Hiç bir hatası yok... Tek sorunu aynı değere sahip elemanların yerlerini korumaması ancak bu da Bubble Sort algoritmasının eksiği. Bu algoritmayı Language Spesific özellikleri dikkate almadan yazdım. Yani oradaki xchange makrosunu kaldırıp xchange kullanılan satıra if döngüsünün içinde dönüşüm yapabilirsiniz. ancak burada satır içinde yer değiştirmek fonksiyon çağrısına göre iyileştirmeler olmadan çok daha hızlı olacaktır. İsterseniz sizde doğrusunu yazın, ayrı bir öneri olarak bulunsun... İyi çalışmalar...

[Erdem]

Elbette kodu alıp iyileştirme ile kullanırsanız hatalar çıkar.

Burada kodu derlerken iyileştirme yapmadım. Anlatmak istediğim XOR kullanan yöntem, ilk planda akıllıca yazılmış gibi görünse de tek satır olarak kullanımda eğer a ve b aynı bellek adresini gösteriyorsa doğru çalışmaz.

http://stackoverflow.com/a/36942/762630

Özellikle de makro kullanımının getirdiği tuzaklara dikkat çekmek istedim. Makrolar körlemesine değişiklik yaparlar.

Bu kodu qsort a alternatif olsun diye yazmadım.

Size katılıyorum öğrenme amaçlı olmadığı zamanda en iyisi kütüphanenin kendi olanaklarını kullanmak.

İsterseniz sizde doğrusunu yazın, ayrı bir öneri olarak bulunsun... İyi çalışmalar...

Beraber öğreniyoruz. Benim yazdığım programlarda da bir sürü hatalar, eksiklikler var..Ayrıca yazdığınız kod olmasaydı bu yerdeğiştirme işlemini öğrenemezdim.

Bu durumda geçici değişken kullanan yöntemi kullanmak daha mantıklı görünüyor. İşlevi çağırırken de yerdegistir(&a[j], &a[j+1]); şeklinde çağırabiliriz. Bunun da en iyi, en doğru çözüm olduğunu söyleyemeyiz ama beraber bir algoritma konusunda sohbet ediyoruz. Amacımız öğrenmek. Yoksa ben de biliyorum internet üzerinde, wikipedia'da başka çözümler var.

Zaten amacım Python gibi dillerin olanakları ile diğer dillerin olanaklarını C, C++, D vs karşılaştırmaktı. Tabi yazım kolaylığı, basitliği vs.. de dahil. Bir dilde bir algoritmayı öğrenince diğer dillerde de aynı çözümler aklıma geliyor. O yüzden başka arkadaşların çözümlerini merak ediyorum.

[fatih6761]

Önerileriniz için teşekkür ederim. Elbette öğreniyoruz, uyguluyoruz, öğretiyoruz. İyi çalışmalar, iyi kodlar 

[Erdem]

Teşekkürler!

Amacımız öğrenmek. Yoksa ben de biliyorum internet üzerinde, wikipedia'da başka çözümler var.

Bu arada o sayfadaki D ile hızlı sıralama algoritmalarına bir tane daha ekledim bile 
[An in-place version - Yerinde sıralayan sürüm]

Ama bu çözümü bir arkadaşım yazdı. Ben de bir tane yazıyorum ama henüz bitmedi.

Algoritmanın kendisini bilmeyen arkadaşlar için Türkçe bir kaynak buldum:

http://www.baskent.edu.tr/~tkaracay/etudio/ders/prg/dataStructures/sorting/QuickSort/QuickSort.pdf

Bu arada benim okuduğum da buydu. Gerçekten güzel anlatmışlar.

http://faculty.simpson.edu/lydia.sinapova/www/cmsc250/LN250_Tremblay/L06-QuickSort.htm

[muhittin_kaplan]

Neden Değerleri Sıralama Gereği Duyuyorsunuz ?

[fatih6761]

@muhittin_kaplan sorunuz pek anlamlı gelmedi. Pek çok şey için değerleri sıralayabiliriz. Mesela İskambil kağıtlarını sıralarken genellikle Insertion sort kullanırız vs...

[Erdem]

Soru eğer algoritmalara neden ihtiyaç duyarız? Ya da bunlar nerede kullanıyor ise şöyle bir örnek verebilirim.

Örneğin kullandığınız elektronik devre analizi programları çizit (graph) veri yapısını kullanıyor. Kirchoff kurallarını uygularken bu veri yapılarını ve algoritmaları kullanıyor. Bu uygulamalar çok geniş bir alana yayılıyor. Facebook sizin arkadaşlarınızla olan ilişkilerinizi kaydetmek için gene çizit veri yapısını kullanıyor.

Geçenlerde bir video paylaşmıştım. Burada Berkeley Üniversitesi Elektrik Mühendisliği ve Bilgisayar Bölümü hocalarından Pieter Abbeel'in öğrencileri yapay zeka kullanarak bir helikopteri kontrol ediyorlardı. Bu uygulamada da tahmin ediyorum aynı anda yüzlerce farklı algoritma işlem yapıyor. Zaten ders için A*, BFS, DFS gibi yön bulma algoritmaları ve çizit, yığıt, liste vs.. gibi veri yapıları hakkında yeterli bilgi sahibi olmak gerekiyor.

Hatta videoyu da şimdi buldum 

learn2fly.wmv

Benim tahminim bu helikopter şimdiye kadar hiç uçmamış  Yani uçmayı öğreniyor.

Gene alttaki videoda robot şimdiye kadar böyle bir arazide hiç dolaşmamış.

learned_controller2.wmv

Kısacası algoritmalar gerçek dünya problemlerine çözüm bulmak isteyen bilim adamları tarafından geliştirilmiştir. Hatta hızlı sıralamanın insan can güvenliğinin önemli olduğu elektronik ve uzay bilimleri uygulamalarında kullanılmaması gerektiğine dair bir yazı okumuştum. Ama nerede okuduğumu hatırlayamadım şimdi.
mesaj birleştirme:: 13 Eylül 2012, 19:33:57

Ama bu çözümü bir arkadaşım yazdı. Ben de bir tane yazıyorum ama henüz bitmedi.

Benim yazdığım çözüm de bu şekilde:

import std.stdio;
import std.algorithm;
import std.array;

T[] hızlıSırala(T)(T[] dizi)
{
    if (dizi.length > 2) {
        auto küçük = dizi[1..$].filter!(x => x < dizi[0])();
        auto büyük = dizi[1..$].filter!(x => x >= dizi[0])();
        return (hızlıSırala(array(küçük)) ~ dizi[0] ~ hızlıSırala(array(büyük)));
    }
    return dizi;
}

void main()
{
    auto sayılar = [5, 3, 25, 6, 10, 17, 1, 2, 18, 8];
    writeln(hızlıSırala(sayılar));
}

Burada D ile Scheme gibi işlevsel dillerde bulunan lambda (isimsiz işlev) olanağını kullanabiliyorsunuz.

Ancak Python'un yazım biçimi lambda işlevleri konusunda çok harikayken D'yi bu konuda çok başarılı bulduğumu söyleyemeyeceğim.

C konusunda örnek gelmediğine göre Python örneğini de yazayım ve noktayı koyuyorum.

def hızlıSırala(liste):
    if len(liste) <= 1:
        return liste
    küçük = [x for x in liste[1:] if x < liste[0]]
    büyük = [x for x in liste[1:] if x >= liste[0]]
    return hızlıSırala(küçük) + [liste[0]] + hızlıSırala(büyük)

#  ana program
if __name__ == '__main__':
    liste = [8, 3, 25, 6, 10, 17, 1, 2, 18, 5]
    print(hızlıSırala(liste))

Python örneğinde sadece 9 satır kod var  Ve Python'un lambda işlevler için yazım biçimi ve genel olarak yazım şekli çok güzel ..

[fatih6761]

SendMessageToMember((person_t*)Erdem, L"Örnekler ve anlatımın güzel olmuş. Sözü geçmişken .Net 4.5 da Lambda Expressionlar ve LINQ teknolojisi ile C# çok gelişti. Bu konuyada bir göz atmanızı öneririm... ");