C ile hızlı sıralama algoritmasını quicksort nasıl yazardınız?
#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);
}
Söylemeyi unutmuşum. Hazır işlevler kulanmadan kendimiz nasıl yazardık.
Wikipedia'da güzel anlatmış. Animasyon falan da var.
http://en.wikipedia.org/wiki/Quicksort (http://en.wikipedia.org/wiki/Quicksort)
JFWI ;)
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.
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...
Alıntı yapılan: fatih6761 - 12 Eylül 2012, 16:56:44
#define xchange(a, b) a ^= b ^= a ^= b;
Burada derleyici şu şekilde bir uyarı verdi:
Alıntı Yap
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. (http://en.wikipedia.org/wiki/XOR_swap_algorithm#Code_example)
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. (http://en.wikipedia.org/wiki/XOR_swap_algorithm#Reasons_for_avoidance_in_practice)
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;
}
Alıntı Yap
#pragma omp parallel for
Burada da böyle bir uyarı aldım:
Alıntı YapUYARI: 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ı :
Alıntı Yap8 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.
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...
Alıntı yapılan: fatih6761 - 12 Eylül 2012, 20:06:24
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 (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.
Alıntı yapılan: fatih6761 - 12 Eylül 2012, 20:06:24
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.
Alıntı yapılan: fatih6761 - 12 Eylül 2012, 20:06:24
İ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.
(http://rosettacode.org/wiki/Sorting_algorithms/Bubble_sort#C)
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.
Önerileriniz için teşekkür ederim. Elbette öğreniyoruz, uyguluyoruz, öğretiyoruz. İyi çalışmalar, iyi kodlar :)
Teşekkürler! :)
Alıntı yapılan: Erdem link=topic=42374.msg306590#msg306590Amacımız öğrenmek. Yoksa ben de biliyorum internet üzerinde, wikipedia'da başka çözümler var. (http://rosettacode.org/wiki/Sorting_algorithms/Bubble_sort#C)
Bu arada o sayfadaki D ile hızlı sıralama (http://rosettacode.org/wiki/Sorting_algorithms/Quicksort#D) algoritmalarına bir tane daha ekledim bile (http://rosettacode.org/wiki/Special:Contributions/Erdem) :D
[
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 (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 (http://faculty.simpson.edu/lydia.sinapova/www/cmsc250/LN250_Tremblay/L06-QuickSort.htm)
Neden Değerleri Sıralama Gereği Duyuyorsunuz ?
@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...
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 (http://www.youtube.com/watch?v=JcRIvJY_0IQ#ws)
Benim tahminim bu helikopter şimdiye kadar hiç uçmamış :D Yani uçmayı öğreniyor.
Gene alttaki videoda robot şimdiye kadar böyle bir arazide hiç dolaşmamış.
learned_controller2.wmv (http://www.youtube.com/watch?v=Bj6frCcbqMA#)
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
Alıntı yapılan: Erdem - 13 Eylül 2012, 13:50:13
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 ..
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... "); :)
Daha bu gün bir arkadaşım bu konuda bir şeyler söylemişti:
Alıntı YapÖrneğin belirli bir dili bilmemin önemli olacağını düşünsem ama o dili sevmesem kesinlik kendi başıma öğrenmem. Bu tür kararlarda mantık da şart değil. Örneğin Java veya C# ne kadar değerli olsalar da ne kadar iyi diller olsalar da benim onlara karşı hiçbir ilgim olmadığı için hiçbir zaman öğreneceğimi sanmıyorum.
Aynen ben de böyle düşünüyorum.
C# ile XNA kullanarak basit bir Pacman oyunu yazmıştım. Ama C++, D, Python gibi dillerin yazım şekline alışınca C# biraz yavan geliyor. Ben zaten D'nin yazım şeklini çok beğeniyorum aslında. Hatta C++'nın bazen oldukça karmaşık olabilen yazım biçimini göre D'nin yazım biçimi daha basit diyebilirim. Benim burada beğenmediğim kısım D'nin isimsiz işlevler için kullandığı yazım biçimi.
Mesela D'de tek sayıları böyle gösterebiliriz:
immutable sayılar = [1, 2, 3, 4, 5, 6];
auto tekSayılar = sayılar.filter!(x => x % 2)();Ama Python'un kullandığı yazım şeklini daha zarif ve kodlaması kolay buluyorum:
sayilar = [1, 2, 3, 4, 5, 6]
tekSayilar = [x for x in sayilar if x % 2 == 1]Bir de sadece tek bir platforma bağlı kalmak bana göre değil :)
(http://ehobi.org/resim/resim/pythonekran.png)
İstediğim zaman Linux istediğim zaman Mac için de kod geliştirebilmeliyim. Sadece bir platforma bağlı kod geliştirdiğinizde dilden ziyade kütüphaneleri öğreniyorsunuz. O zaman başka işletim sistemlerine
[geçenlerde hatta VxWorks gibi gerçek zamanlı işletim sistemlerinden bahsedilmişti] geçtiğinizde sudan çıkmış balığa dönüyorsunuz
Bilmiyorum benim düşüncelerim bunlar ..
Soru Basit "Gerçek Dünyadaki Bilgileri yada Fonksiyonlar Tarafından Üretilmiş Değerleri Neden Sıralama gereği duyarız"
Okullardaki Yarı Piskopat Hocaların "Anlamsız Olarak, Hiç Kullanılmayacak Algoritmalar Yazmalarını İstemeleri" gibi bir durum mudur bu ?
Örnek:
"Sıfırdan, Girilen Sayı Aralığının Finobacchi Dizilimini Yapan Fonksiyonunu Yazınız"
Alıntı yapılan: muhittin_kaplan - 13 Eylül 2012, 20:28:04
Örnek:
"Sıfırdan, Girilen Sayı Aralığının Finobacchi Dizilimini Yapan Fonksiyonunu Yazınız"
Hocam işin felsefi boyutlarını fazla bilmiyorum ama D'nin Fibonacci için çözümü şu şekilde:
import std.stdio;
import std.range;
struct FibonacciSerisi
{
ulong baştaki = 0;
ulong sonraki = 1;
static immutable bool empty = false;
@property ulong front() const
{
return baştaki;
}
void popFront()
{
ulong ikiSonraki = baştaki + sonraki;
baştaki = sonraki;
sonraki = ikiSonraki;
}
}
void main()
{
writeln(take(FibonacciSerisi(), 10));
}
@muhittin sorduğunuz soru bana halâ anlamsız geliyor. Yani bu sorduğunuz soru sıra, düzen gibi kavramları yok sayıyor. Yani en basitinden komutan-asker ilişkisini düşün. Bunlar bir anlamda binary tree lere benzer, yetkilerine göre sıralanmış insan nesneleridir. Onbaşının on askeri vardır. Yetkisine 10 diyelim. Yüz başının bunları da kapsayan yüz askeri var. O halde yetkisi 100 olur. Bu iki asker nesnesini sıralamazsak sistem çalışmaz... gibi... Eğer gerçekten kasdettiğin algoritma neden var sorusu ise, biz neden varız?'a kadar gider...
Alıntı yapılan: muhittin_kaplan - 13 Eylül 2012, 20:28:04
Soru Basit "Gerçek Dünyadaki Bilgileri yada Fonksiyonlar Tarafından Üretilmiş Değerleri Neden Sıralama gereği duyarız"
Okullardaki Yarı Piskopat Hocaların "Anlamsız Olarak, Hiç Kullanılmayacak Algoritmalar Yazmalarını İstemeleri" gibi bir durum mudur bu ?
Örnek:
"Sıfırdan, Girilen Sayı Aralığının Finobacchi Dizilimini Yapan Fonksiyonunu Yazınız"
Verileri sıralama gereği duymamızın sebebi, onlara daha hızlı ulaşabilmektir. Kitapların raflara rasgele dizildiği bir kütüphane düşün, binlerce kitap var. Ve sen bir tanesini arıyorsun...
Hocaları öğrencilere anlamsız algoritmalar yazdırmalarının sebebi de, başlangıç seviyesindeki öğrencilerin anlamlı algoritmalar yazacak seviyeye ulaşmamış olmalarıdır. Öğrenmek için de birşeyler yazmaları gerekiyor sonuçta.
Alıntı yapılan: muhittin_kaplan - 13 Eylül 2012, 20:28:04
....Okullardaki Yarı Piskopat Hocaların "Anlamsız Olarak, Hiç Kullanılmayacak Algoritmalar Yazmalarını İstemeleri" gibi bir durum mudur bu ? ....
Örnek:
"Sıfırdan, Girilen Sayı Aralığının Finobacchi Dizilimini Yapan Fonksiyonunu Yazınız"
Matematikte öyle sorularla sorulur ki bu sorularla gerçek hayatta bugüne kadar hiç karşılaşılmamıştır belki de gelecekte de hiç karşılaşılmayacaktır.
Bu tip sorular problem çözmeyi öğretir. Piskopat olarak bahsettiğiniz hocaların sorduğu algoritma soruları, öğrencilerin algoritma oluşturma yeteneklerini artırmayı hedeflemektedir. Öte yandan bir algoritmanın hiç kullanılmayacağını söyleyebilmek için tüm bilim dallarına hakim olmak gerek.
Öte yandan algoritma oluşturmak, problemin bilgisayara çözümünü tarif etmenin daha ötesinde bir çalışmadır.
Hemen aklıma geldi bir kullanım alanı. Genetik algoritmada elitizm uygularken elimizdeki değerlerin sıralanıp değerlendirilmesi gerekiyor. Mesela alışveriş sitelerinde fiyata göre sıralama yaptırıyoruz. Yada bir sınav sonucundaki başarı listesini oluşturuyoruz. Düşündükçe pek çok örnek çıkıyor.
Konu Başka yerlere gidecek. Korkuyorum.
@Fatih hocam Böyle bir algoritma oluşturup sıralayacağıma 2 derinlikli bir değişkenle sıra ve yetki tanımlaması yaparım.kaldıki Uygulamada böyledir. uniq olan bir id ve yetki kodu verilir kullanıcılara.
@Tagli Hocam Sıra erişimli bellek te tutarsak bilgileri dediğiniz doğru ama Rastgele erişimşide adresi ver bilgiyi versin. neden sıralayıp tekrardan işlem yapayım ki ?
@Z hocam Algoritma geliştirmeyi öğretmek için "gerçektem kullanılır" sorular verilsin. Sonrasında gerçek hayatta gerçek algoritmalar oluştursunlar.
@muuzoo Hocam elektronikte değilde genelde bilgisayar ve hatta veritabanında SQL kullanılarak yapılır dediğiniz. oda gerekirse "büyükten küçüğe sıralayarak ilk on kaydı ver" gibi. burada esas amaç en büyüğü yada tersini küçüğü bulmaktır.
ama aklıma birşey geldi. sıkıştırma algoritmalarında bu büyükten küçüğe sıralama kullanılıyor olabilr mi ?
Ayrıca Teker Teker Gelin
Neden sıralama yaparız?
gerçek hayattan gerçek bir gerekçe:
10 tane motorun var. 1-2 tanesi asıl diğerleri yedek.
Eş yaşlandırma yapacaksın. Yani bir motor belirli bir süre çalıştıktan sonra, bir sonraki operasyonda ilk start alacak motor en az çalışmış olan yani en genç motor olacaktır. Aynı şekilde bir motor yetmediğinde 2., 3. ve sıra ile en genç olandan en yaşlı olana doğru motorları devreya alman gerekecek. Motorların çalışma saatlerine (workhour) bakarak motorları sıraya sokarsın.
Bunun için illa ki sıralama yapmak zorunda mıyız? hayır!
Ama öyle ya da böyle bu motorların saatleri karşılaştırılacak. Öyleyse her seferinde bunları karşılaştırmaktansa bir kez sıralar ve yoluma devam ederim.
Alıntı yapılan: muhittin_kaplan - 14 Eylül 2012, 16:00:45
@Z hocam Algoritma geliştirmeyi öğretmek için "gerçektem kullanılır" sorular verilsin. Sonrasında gerçek hayatta gerçek algoritmalar oluştursunlar.
Evet bence de mantıklı.
Örneğin bir arabanın üretim zincirinde mümkün olan işlemleri paralel yürüterek araba üretim süresinin minimuma indirilmesi çizit kuramının bir uygulamasıdır. Denilerek öğrenci teşvik edilebilir. Örneğin parçaların montajı ve direksiyonun bağlanmasından hemen sonra kablo ve elektrik işleri yapılacak vs..
Bu konu hocasının yeteneğine kalmış diye düşünüyorum. Örneğin burada daha ilk haftalardan Pacman'e nasıl arama yapacağını öğretmenizi istiyorlar:
http://www-inst.eecs.berkeley.edu/~cs188/fa11/projects/search/search.html (http://www-inst.eecs.berkeley.edu/~cs188/fa11/projects/search/search.html)