Quick Sort

Quick Sort, eleman kümesi içerisinde seçilen pivot sayının diğer sayılarla karşılaştırılarak büyüklük ve küçüklük durumuna göre pivot sayının sağ ve sol tarafına yerleştirilmesi sonucu oluşan sıralama  algoritmasıdır. Quick sort algoritmasını Türkçe kaynaklarda ‘Hızlı Sıralama Algoritması’ olarak görebilirsiniz.

Quick sort algoritması, sürekli olarak aynı mantık ile eleman kümesinden pivot sayı seçip karşılaştırma yaptığı için recursive fonksiyon ile çözüme kavuşturulması daha uygundur.

En kötü durum performansı (worst case performance) O(n²)‘dir. En iyi durum performansı O(n log n)‘dir. Ortalama durum performansı ise yine O(n log n) kabul edilir.

Rastgele üretilmiş sayıları temsil eden çubukların quick sort algoritması ile nasıl sıralandığını aşağıda vermiş olduğum animasyonda görebilirsiniz.

Insertion sort(eklemeli sıralama)

Insertion sort, eleman kümesinin (array/dizi) 2. elemanından başlayarak kendinden önceki elemanlarla karşılaştırma yapar. Karşılaştırma yaptığı elemanlar kendinden büyükse bu elemanlar, küme içerisinde sağa doğru kaydırılır. Ve seçili eleman uygun yere yerleştirilir.

Insertion sort algoritmasında şüphesiz ki göze çarpan ilk olumsuz taraf, elemanların kaydırılması ile kaybedilen süre olacaktır. Daha açık biçimde özetlersek; eleman kümesinin son elemanı eğer en küçük değerse, kümenin en başına gelecek ve bütün elemanlar kaydırılacak.

En kötü durum performansı (worst-case performance) O(n²) ‘dir. En iyi durum performansı (best-case performance) O(n) ‘dir. En kötü durum performansından yola çıkarak algoritmayı değerlendirmek istersek, küçük değerler (N<1000) için sorun yaşamayacağımızı görüyoruz. Değerler büyüdükçe bizler için yükü de olumsuz yönde artıyor.

Insertion sort algoritmasının Türkçe karşılığı kaynaklarda ‘Eklemeli Sıralama Algoritması‘ olarak belirtilmiştir. Farklı kaynaklardan araştırma yapmak isteyen arkadaşlara kolaylık olsun.

C++ Notlarım

C++ Notlarım
Aşağıda C++  ile ilgili aldığım notlar var.

C++11
C++11 veya C++03 desteğini etkinleştirmek için -std=c++0x ve -std=c++1y seçeneklerini kullanmak gerekir.

array
çok boyutlu array aşağıdaki gibi ilklendirilebilir.

float y[3][3] = {
    { 1, 3, 5 },    
    { 2, 4, 6 },
    { 3, 5, 7 }
};

auto değişken
Değişkenin tipini belirtmeden derleyicinin belirlemesi sağlanır. Buradaki soruda auto * şeklinde kullanım da gösterilmiş.

Bence sadece auto şeklinde kullanma amaca daha iyi hizmet eder.

const değişken
Buradaki cevapta değişkenin adresi alınmadığı müddetçe const int veya #define ile bir değişken tanımlamanın modern derleyiciler için aynı şey olduğu belirtilmiş.

#define STD_VEC_HINT 6;
const int stdVecHint = 6;

constexpr
Eski C++ ile integral olmayan static const değişkenleri sınıfın özelliği gibi tanımlamak mümkün değildi. Bu yüzden aşağıdaki gibi yapmak gerekiyordu.

C++11 ile artık daha kolay. Örnek:

constructor
buit-in tiplerin constructor metodu yoktur
C++'ta built-in tiplerin constructor metodları yoktur.
int a = 42 ve
int a;
a = 42 aynı şeydir. a tipinin constructor metodu olmadığı için a tipini tanımlayan ilk cümle bir şey çalıştırmaz.

constructor'dan virtual metod çağrılamaz
Genel kural olarak bir sınıfın contructor veya destructor metodlarında virtual metodlar çağrılmaz. Örneğin parasoft şu uyarıyı verir.

"A class's virtual functions shall not be invoked from its destructor or any of its constructors (JSF-71.1-2)"
Örnekte pure virtual bir metod çağrıldığı için çöker.

struct Base
{
    Base() { method(); }

    virtual void method() = 0;
};
struct Derived : Base
{
    void method() {};
};
int main()
{
    Derived d;
}

Bu kural Java için, geçerli olmasa da hataya açık kapı bıraktığı için, yapılmaması bence daha iyi. Örnek de hatalı durum görülebilir.

STL Algoritmaları

Aşağıda kullandığım STL algoritmaları ile ilgili aldığım notlar var. C++ Notlarım başlıklı yazıda ise C++ ile ilgili konuları not aldım.

Algoritmalar
Tüm algoritmalar iterator ile çalışıyorlar. Şekilde bunu görmek mümkün. Iterator aynı zamanda bir GoF Davranışsal Örüntüsü (Behavioral Pattern) Açıklaması ile aşağıda:

"This pattern provides a way to access the elements of an aggregate object sequentially without exposing its underlying representation"

Kendi yazdığımız algoritmalara da iterator geçmek daha doğru, ancak bazen algoritma size() gibi container'a mahsus metodlara ihtiyaç duyabilir. Bu durumda mecburen container geçmek gerekiyor.

Algoritma denilince aşağıdaki gibi içine bir çok parametre alan ve bir çıktı veren metod değil, bir veri yapısı üzerinden yürümeyi gerektiren metodlar akla gelmeli. 

accumulate
accumulate ile bir aralığın ortalaması bulunabilir. Örnek:

adjacent_find
Yanyana elemanlara verilen metodu uygular. false dönen ilk elemanı döner. Bir dizinin sıralı (sorted) olup olmadığını anlamak dışında kullanıldığını görmedim. Örnek:

auto it = std::adjacent_find(begin(tab), end(tab),  std::greater<int>() );

advance
Advance verilen iterator parametresini belirtilen sayı kadar ileri veya geri oynatır. Verilen iterator'ün tipine göre pointer arithmetic veya döngü kullanabilir. Örnek:

auto it = my_vector.begin(); // std::vector has random access iterators
std::advance(it, 4);         // NOT a loop, will call it += 4;

veya

auto it = my_map.begin();    // std::map has bidirectional iterators
std::advance(it, 4);         // for (auto i = 0; i < 4; ++i) ++it;

(Project Euler) Problem 1 Çözüm - 3 ve 5'in katları

Project Euler'de sorulan soru aşağıda. 1'den 1000'e kadar 3'e ve/veya 5'e bölünen sayıları ve kaç tane olduklarını bulacağım.

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

İkinci else if'te k'yı azaltmamın sebebi 3'e ve 5'e bölünen sayıları 2 kere saymasını engellemek. Örneğin 15 hem 3'e hem 5'e bölünür. Bir kere sayması için if şartını koydum.

#include<stdio.h>
#include<conio.h>

main(){
    int i,k=0;
   
    for(i=1;i<=1000;i++)
    {
       if(i%3==0)
       {
          printf("%d  ",i);  
          k++;      
       }  
      
       else if(i%5==0)
       {
          printf("%d  ",i);    
          k++;
       }    
      
       else if((i%3==0)&&(i%5==0))   
       {
          k--;    
       }      
      
       else
       {
          continue;   
       }
    }
   
    printf("\n\n\n3 ve 5'in kati olan %d sayi var",k);
   
    getch();
}