C++ Module 09

Bu proje, **C++** dilinde **STL (Standard Template Library)** kullanarak ileri seviye veri yapıları ve algoritma mantığını pekiştirmeyi hedefleyen 3 egzersizten oluşur. Her egzersiz, farklı bir STL konteyneri kullanımını zorunlu kılar ve öğrencinin kapsayıcı (container) kullanımı, algoritmalar, zaman hesaplama ve hata yönetimi konularında pratik yapmasını sağlar.

---

İçindekiler 📚

• Ex00 - Bitcoin Exchange
  • Kapsayıcı Kullanımı
  • Map Nedir?
  • Hata Yönetimi
  • std::istringstream Nedir?
• Ex01 - Reverse Polish Notation
  • Kapsayıcı Kullanımı
  • Stack Nedir?
  • RPN Hesaplaması
• Ex02 - PmergeMe
  • Kapsayıcı Kullanımı
  • Ford-Johnson Algoritması
  • Ford-Johnson (Merge-Insertion Sort) Mantığı
  • Jacobsthal Sayıları
  • Zaman Ölçümü ve Performans

---

Ex00 - Bitcoin Exchange

Belirli bir tarih ve miktar için, Bitcoin fiyat veritabanına göre değer hesaplayan bir program.

Kullanıcıdan alınan tarih ve değer bilgilerinin bir CSV dosyasındaki fiyatlarla çarpılması sağlanır.

Kapsayıcı Kullanımı

• std::map kullanılır.
• Tarih-fiyat çiftleri sıralı olarak tutulur.
• Tarih bulunamazsa lower_bound() ile en yakın önceki tarih bulunur.

Map Nedir?

std::map, C++ STL'de anahtar-değer çiftlerini sıralı tutan bir konteynerdir.

Özellikleri:

• Anahtarlar benzersizdir.
• Otomatik küçükten büyüğe sıralama yapar.
• Arama, ekleme, silme gibi işlemler O(log n) zamanda gerçekleşir.
• lower_bound() fonksiyonuyla belirli bir anahtara en yakın büyük veya eşit anahtar bulunabilir.

Örnek Kullanım:

std::map<std::string, float> bitcoinRates;
bitcoinRates["2011-01-03"] = 0.3f;

std::istringstream Nedir?

std::istringstream, bir std::string üzerinden veri okumak için kullanılan bir giriş akışı (input stream) aracıdır.

• #include <sstream> kütüphanesi ile kullanılır.
• Dosya veya cin gibi davranarak string'den veri çeker.

Örnek Kullanım:

#include <sstream>
#include <iostream>

int main() {
    std::string data = "42 3.14 hello";
    std::istringstream stream(data);

    int i;
    double d;
    std::string s;

    stream >> i >> d >> s;

    std::cout << i << " " << d << " " << s << std::endl;
    return 0;
}

Çıktı:

42 3.14 hello

Avantajları:

• String verileri kolayca parçalayabilir ve uygun türlere dönüştürebilirsiniz.

Hata Yönetimi

• Geçersiz tarih formatları algılanır.
• Negatif değerler veya 1000'den büyük miktarlar hata olarak işlenip bildirimi yapılır.
• Bozuk satırlar için anlamlı hata mesajları basılır.

---

Ex01 - Reverse Polish Notation (RPN)

Ters Lehçe (RPN) formatında verilen matematiksel ifadeleri hesaplayan program.

Kapsayıcı Kullanımı

• std::stack kullanılır.
• Sayılar stack'e eklenir, operatör geldiğinde son iki eleman çekilerek işlem yapılır.

Stack Nedir?

• LIFO (Last-In-First-Out) mantığı ile çalışır.
• Son eklenen eleman ilk çıkar.
• push(), pop(), top() fonksiyonları bulunur.
• Iterator desteği yoktur.

RPN Hesaplaması

Yöntem:

• Sayılar geldikçe stack'e eklenir.
• Operatör geldiğinde, son iki sayı çekilip işlem yapılır.
• Sonuç tekrar stack'e atılır.

Geçerli operatörler: +, -, *, /

Hatalı girdi:

• "Error" mesajı basılır.
• Stack'te yeterli eleman yoksa veya bilinmeyen operatör kullanıldıysa hata verilir.

Örnek: Girdi:

5 1 2 + 4 * + 3 -

İşlem sırası:

• 1 + 2 = 3
• 3 * 4 = 12
• 5 + 12 = 17
• 17 - 3 = 14

Sonuç: 14

---

Ex02 - PmergeMe

Pozitif tamsayılardan oluşan bir diziyi Ford-Johnson (Merge-Insert) algoritması ile sıralayan program.

Aynı algoritmanın hem std::vector hem std::deque konteynerlerinde uygulanması istenir.

Kapsayıcı Kullanımı

• std::vector ve std::deque kullanılır.
• Aynı algoritma ikisine de ayrı ayrı uygulanır.

Ford-Johnson Algoritması

Ford-Johnson algoritması, en az sayıda karşılaştırma yaparak sıralama amacıyla tasarlanmıştır.

Ford-Johnson (Merge-Insertion Sort) Mantığı

Adımlar:

1. Veri çiftler haline getirilir.
2. Her çift kendi içinde sıralanır (küçük -> büyük).
3. Büyük elemanlar ana liste olarak alınır.
4. Ana liste sıralı hale getirilir.
5. Küçük elemanlar uygun yerlere binary search ile yerleştirilir.
6. Eğer tek kalan eleman varsa, doğru yere eklenir.

Örnek: Veri:

[7, 2, 5, 3, 9]

Adımlar:

• Çiftler: (2,7), (3,5), (9)
• Büyükler: [7,5]
• Sıralı büyükler: [5,7]
• Küçük 2 -> 5'in önüne
• Küçük 3 -> 5 ile 7 arasına
• Tek kalan 9 -> sona

Sonuç:

[2, 3, 5, 7, 9]

Avantajları:

• Teorik olarak minimum karşılaştırma sayısını hedefler.
• Merge Sort ve Insertion Sort'un birleşimidir.

Performansı:

• N * log2(N) - 1.44N civarında karşılaştırma yapar.

Jacobsthal Sayıları

Ford-Johnson algoritması, küçük elemanların ana listeye yerleştirilme sırasını belirlemek için Jacobsthal dizisini kullanır.

Jacobsthal dizisi tanımı:

J(0) = 0
J(1) = 1
J(n) = J(n-1) + 2 * J(n-2)

İlk birkaç Jacobsthal sayısı:

0, 1, 1, 3, 5, 11, 21, 43, 85, 171, ...

Ford-Johnson'da kullanımı:

• Küçük elemanlar, Jacobsthal dizisine göre ana listeye eklenir.
• Bu strateji, ekleme sırasını optimize ederek karşılaştırma sayısını daha da azaltır.
• Özellikle büyük veri setlerinde sıralama verimliliğini artırır.

Zaman Ölçümü ve Performans

• Her iki konteyner için sıralama zamanı mikro-saniye (µs) hassasiyetinde ölçülür.
• std::clock() fonksiyonu kullanılır.

std::vector:

• Dinamik dizi.
• Rastgele erişim O(1).
• Ortadan ekleme/silme maliyetlidir.

std::deque:

• Çift uçlu kuyruk.
• Baştan/sondan hızlı ekleme/silme O(1).
• Ortadan erişim O(n).

---

2025 | Created by Derya ACAR