STL kütüphanesi içindeki sıralama ve arama algoritmaları, verileri belirli bir düzene göre sıralamayı ve öğeleri bulmayı kolaylaştırır Sıralama işlemlerinde sort, stable_sort, partial_sort ve nth_element algoritmaları kullanılırken, arama işlemlerinde find, find_if, search, binary_search, lower_bound ve upper_bound algoritmaları kullanılır Binary search algoritması, sıralı bir dizide eleman aramak için kullanılır ve Olog n karmaşıklığına sahiptir Lower bound ve upper bound algoritmaları da belirli bir değer için alt ve üst sınırları bulmak için kullanılır
Bugün, STL kütüphanesinde bulunan sıralama ve arama algoritmaları hakkında genel bir bakış sunacağız. Sıralama algoritmaları, öğeleri belirli bir sıraya göre sıralamak için kullanılırken, arama algoritmaları bir öğenin varlığını veya konumunu bulmak için kullanılır.
STL sıralama algoritmaları, öğeleri belirli bir düzene göre sıralayarak öğe bulmayı ve arama algoritmaları, bir aralıkta bir öğeyi bulmayı kolaylaştırır. Bu algoritmalar, en uygun veri yapısına bağlı olarak kullanılabilir ve kullanımda oldukça verimlidirler. Ayrıca, özelleştirilmiş sıralama ve arama fonksiyonları da vardır. Bu fonksiyonlar bir karşılaştırma fonksiyonu kullanarak öğeleri karşılaştırır ve kullanıcının belirlediği düzenlemeye göre sıralar.
Sıralama Algoritmaları
STL'de bulunan sıralama algoritmaları, verileri belirli bir kritere göre sıralamak için kullanılır. Bu kriter, varsayılan olarak elemanların doğal sıralamasına göre belirlenir. Ancak, özelleştirilmiş sıralama fonksiyonları oluşturarak, elemanların istenilen formatta sıralanması sağlanabilir.
STL kütüphanesindeki sıralama algoritmaları şu şekildedir:
- sort: Sıralama işlemi için kullanılan temel algoritmadır. İki parametre alır: sıralanacak dizinin başlangıç ve son indeksleri.
- stable_sort: Neredeyse sort ile aynıdır ancak eşit elemanların sırası korunur.
- partial_sort: Listenin belli bir aralığını sıralar. İki parametre alır: sıralanacak dizinin başlangıç ve son indeksleri.
- nth_element: Listenin belirtilen direncindeki elemanı bulmak için kullanılır. İki parametre alır: direnç indeksi ve sıralanacak dizinin başlangıç ve son indeksleri.
Sıralama işlemleri, nesne dizgileri ve dizilimler için ayrı ayrı yapılabilir. Nesne dizgisi sıralama işlemleri, elemanların doğal sıralamasına göre gerçekleşir. Dizilimler ise atanan değere göre sıralanır.
Sıralama algoritmaları, veri yönetiminde sıklıkla kullanılan işlemlerdir. Çalışma zamanları incelendiğinde, sıralama işleminin kapsamı önemlidir. Sıralama işlemi, verilerin sayısına göre büyük bir performans etkisine sahip olabilir.
Arama Algoritmaları
STL kütüphanesi içerisinde bulunan arama algoritmaları da sıralama algoritmaları kadar önemlidir. Bu algoritmalar, nesne dizgileri ve dizilimlerde eleman aramada kullanılır.
Bu algoritmalardan biri olan find(), bir dizi içinde verilen bir elemanın varlığını kontrol ederek, varsa o elemanın konumunu döndürür. Find_if() işlevi ise bir fonksiyonu kullanarak belirli bir koşula uyan ilk elemanı döndürür.
Search() işlevi, bir dizi veya veri yapısı içinde belirtilen bir dizi ile arama yapmayı sağlar. Verilen dizinin ilk elemanının, arama yapılan veri yapısındaki bir dizinin herhangi bir yerinde bulunduğu yeri döndürür.
STL kütüphanesinin sahip olduğu en popüler arama algoritması ise binary search'tür. Bu algoritma, sıralanmış bir dizi içinde eleman aramayı hızlandırır. Binary search işlevi, orta elemanı bulma ve aranan öğenin ortaya göre sol veya sağ tarafa olan konumu hakkında karar vermeyle çalışır.
Bunların yanı sıra lower_bound() ve upper_bound() algoritmaları da önemlidir. Lower_bound(), belirli bir değeri veya değerin altındaki ilk öğeyi döndürürken, upper_bound() belirtilen bir değerin üstündeki ilk öğeyi döndürür. Bu algoritmalar sıralı bir dizi içinde elemanın konumunu bulmada oldukça yararlıdır.
Binary Search
Binary search algoritması, bir sıralı dizide belirli bir elemanın bulunup bulunmadığını, bulunuyorsa hangi indekste olduğunu bulmak için kullanılır. Temel olarak, dizinin ortasını seçerek aranan elemanın o orta noktanın solunda veya sağındaki yarı diziyi göz ardı ederek aramaya devam eder.
Binary search algoritması, O(log n) karmaşıklığına sahiptir ve bu sayede uzun dizilerde bile oldukça hızlı bir şekilde arama yapabilir. Bununla birlikte, sıralama işleminden önce dizinin sıralanması gerektiği için bunu yapmak için de başka bir algoritmayla uğraşmanız gerekebilir.
STL'de binary search algoritması için "binary_search" fonksiyonu kullanılır. Bu fonksiyon, bir dizide belirtilen bir öğenin olup olmadığını kontrol eder ve "true" veya "false" ile sonuçlanarak bulunduğu ya da bulunmadığı bilgisini döndürür.
Önemli İşlevler | Açıklama |
---|---|
binary_search(start, end, value) | Belirli bir değerin dizide bulunup bulunmadığını kontrol eder. |
Bununla birlikte, binary search algoritması yalnızca sıralı dizilerde işe yarayacaktır. Eğer diziniz sıralı değilse, sıralama işlemi yapmadan binary search algoritmasını kullanamazsınız.
STL'de binary search algoritmasının kullanımı oldukça basit ve etkilidir. Ancak sıralama gerekliliği nedeniyle bazen diğer arama yöntemlerini kullanmak daha uygun olabilir.
Lower Bound ve Upper Bound
STL kütüphanesi içindeki arama algoritmalarından biri lower bound olarak adlandırılıyor. Bu algoritma, bir değer için alt sınırı bulmak için kullanılıyor. Üst sınırı bulmak için ise upper bound algoritması kullanılıyor. Bu algoritma ile bir dizi içinde aranan değere en yakın büyük değeri bulmak mümkün.
Lower bound algoritması kullanılırken, belirli bir değerin dizideki ilk görünüm noktası aranır ve sonrasında bir döngü aracılığıyla aranan değer ile her bir elemanın karşılaştırması yapılır. Bu süreçte doğru değer bulunana kadar tekrar edilir.
Upper bound algoritması da benzer bir şekilde çalışır. Dizi içerisinde aranan değerden büyük en küçük değeri bulmak için kullanılır. Bu algoritma, dizi içerisindeki aranan değerin olup olmadığına bakmaz, sadece aranan değerden büyük en küçük değeri bulmaya odaklanır.
STL'de lower bound algoritması için 'lower_bound' adlı bir fonksiyon, upper bound algoritması için ise 'upper_bound' adlı bir fonksiyon bulunuyor. Bu fonksiyonlar, detaylı bir şekilde kullanımına dair örnekler bulabileceğiniz kaynaklar aracılığıyla rahatlıkla öğrenilebilir ve uygulanabilir.
Find, Find_if ve Search
STL'de bulunan find, find_if ve search algoritmaları, verilen bir dizide veya nesne dizgisinde belirli bir elemanın var olup olmadığını araştırmak için kullanılır. Daha spesifik olarak, find işlevi bir değer belirler ve bunun bulunup bulunmadığını kontrol eder. find_if işlevi ise bir ölçüt belirler ve dizideki tüm öğeleri belirtilen ölçüte göre karşılaştırır ve ölçüte eşit olan ilk öğeyi döndürür. Son olarak, search işlevi belirli bir alt dizgeyi arar ve eğer alt dizge bulunursa ilk alt dizi elemanını döndürür.
Bu algoritmaların kullanımı oldukça basittir. Başlangıç konumu, son konum ve aranması gereken elemanın değeri veya ölçütü belirtilir ve algoritma, belirtilen arama türüne göre dizide arama yapar. Aşağıdaki örnekte, bir nesne dizgisinde find, find_if ve search işlevlerinin nasıl kullanılabileceği gösterilir:
Örnek Kod: ```#include
int main() { vector
// find işlevi: auto it = find(v.begin(), v.end(), x); if (it != v.end()) { cout << "Eleman Bulundu: " << *it << endl; } else { cout << "Eleman Bulunamadı" << endl; }
// find_if işlevi: auto itr = find_if(v.begin(), v.end(), [](int n){ return n%2==0; }); if (itr != v.end()) { cout << "Çift Sayı Bulundu: " << *itr << endl; } else { cout << "Çift Sayı Bulunamadı" << endl; }
// search işlevi: vector
Bu kodda, bir vektör oluşturulur ve belirli bir değer veya ölçüte göre elemanlar aranır. Find işlevi, x değerini arar ve ilk bulduğu elemanın konumunu döndürür. Find_if işlevi ise vektördeki tüm elemanları belirli bir ölçüte göre karşılaştırır ve ilk ölçüte eşit olan elemanı döndürür. Son olarak, search işlevi belirli bir alt dizgeyi arar ve ilk alt dizi elemanını döndürür. Bu örnekler, bulunan elemanların konumunu gösterir ve bu sadece kullanıcıya bilgi sağlamak için kullanılır.
Sort
Sort işlevi, STL kütüphanesindeki en önemli sıralama algoritmalarından biridir. Bu işlev, bir nesne dizgisini sıralamak için kullanılır. Sıralama işlemi, önceden belirtilmiş bir sıralama kriterine göre gerçekleştirilir. Örneğin, bir nesne dizgisi alfabetik olarak sıralanabilir veya sayısal olarak sıralanabilir.
STL'nin sort işlevi, dizgileri, listedeki elemanları veya vektörlerdeki elemanları sıralayabilir. Bu işlev ayrıca, özel bir sıralama işlevi kullanarak da kullanılabilir. Bu özel işlev, sort işlevine verilen parametreler arasında yer alır ve kullanıcının belirlemesi gereken bir fonksiyondur.
Parametre | Açıklama |
---|---|
first | Sıralama yapılacak dizinin ilk elemanını gösteren bir işaretçi |
last | Sıralama yapılacak dizinin son elemanını gösteren bir işaretçi |
compare | İsteğe bağlı bir parametre. Özel bir sıralama işlevi belirtmek için kullanılır. Varsayılan olarak std::less kullanılır. |
- Sort işlevi, O(nlogn) karmaşıklığına sahiptir ve bu nedenle büyük boyutlu nesne dizgilerinde performans açısından başarılıdır.
- Sort işlevi, elemanları sıralamak için karşılaştırma işlemlerine ihtiyaç duyar. İsteğe bağlı compare parametresi ile bu karşılaştırma işlevi özelleştirilebilir.
- STL'nin sort işlevi, son derece hızlı ve etkili bir sıralama işlevi olduğu için sıklıkla kullanılır.
Custom sort fonksiyonları, sort işlevi ile kullanıldığında, kullanıcının belirlediği bir kritere göre elemanların sıralanmasına olanak tanır. Bu özelleştirilmiş sıralama işlevi, standart sort işlevinin tanımladığı kriterden farklı bir sıralama kriteri belirler. Özelleştirilmiş bir fonksiyon kullanarak, bir nesne dizgisindeki elemanların sıralanması, sağlanan kritere uygun olarak yapılabilir.
Özel bir sıralama işlevi kullanırken, karşılaştırma işlevinin geri dönüş türü bool'dur. Karşılaştırma işlevinde kriteri belirlemek ve sıralama işlemini gerçekleştirmek için if koşulları kullanılır.
Genel Örnekler
STL kütüphanesi ile sıralama ve arama algoritmaları hakkında genel bilgi edindikten sonra, birkaç örnek kullanarak daha iyi anlayabiliriz. Öncelikle, nesne dizgileri için örnek bir kod yazalım:
#include <iostream>#include <algorithm>#include <vector>using namespace std;int main() { vector<int> v = {4, 2, 6, 1, 9, 3}; // Sıralama sort(v.begin(), v.end()); // Eleman arama auto it = find(v.begin(), v.end(), 6); if (it != v.end()) cout << "Eleman bulundu: " << *it << endl; else cout << "Eleman bulunamadı" << endl; return 0;}
Bu örnekte, öncelikle bir vector
oluşturduk ve sıraladık. Daha sonra, find
fonksiyonu ile dizi içinde bir eleman aradık. Eğer bulduysak, onsola yazdırıyoruz. Bu örneği değiştirerek, farklı sıralama ve arama fonksiyonlarını kullanarak deneyebilirsiniz.
Bir de dizilimler için bir örnek yazalım:
#include <iostream>#include <algorithm>#include <array>using namespace std;int main() { array<int, 6> arr = {4, 2, 6, 1, 9, 3}; // Sıralama sort(arr.begin(), arr.end()); // Eleman arama auto it = lower_bound(arr.begin(), arr.end(), 6); if (it != arr.end()) cout << "Eleman bulundu: " << *it << endl; else cout << "Eleman bulunamadı" << endl; return 0;}
Bu örnekte, bir array
oluşturduk ve sıraladık. Daha sonra, lower_bound
fonksiyonu ile dizi içinde bir eleman aradık. Eğer bulduysak, onsola yazdırıyoruz. Bu örneği değiştirerek, farklı sıralama ve arama fonksiyonlarını kullanarak deneyebilirsiniz.
Nesne dizgisi için örnek
Nesne dizgileri, belirli tipte nesneleri bir araya getiren yeniden kullanılabilir kod bloklarıdır. Bu örnekte, bir nesne dizgisindeki elemanların nasıl sıralanacağı ve aranacağı ile ilgili kod örneği incelenecek. Bu işlemler için sırasıyla sort ve find algoritmaları kullanılabilir.
Bir nesne dizgisindeki elemanlar belirli bir sıraya göre düzenlenebilir. STL'deki sort algoritması bu işlem için kullanılabilir. Sort işleminin gerçekleştirilmesi için sıralama yapılacak dizgi varsayılan olarak "artan" sıralı olacak şekilde tanımlanmalıdır. Bu şekilde elemanları kendi içinde sıralamak mümkündür.
Kod Örneği | Açıklama |
---|---|
| Bu örnekte, bir int türündeki vektör örneği sort fonksiyonu kullanılarak sıralanmıştır. |
Bir nesne dizgisindeki elemanlar belirli bir kritere göre aranabilir. STL'deki find algoritması bu işlem için kullanılabilir. Belirli bir öğenin dizgi içinde bulunup bulunmadığını, varsa konumunu döndürür. Find algoritması kullanılacak dizgi ve aranacak eleman parametre olarak verilmelidir.
Kod Örneği | Açıklama |
---|---|
| Bu örnekte, bir int türündeki vektör örneği find fonksiyonu kullanılarak belirli bir eleman sorgulanmıştır. |
Bu örnek kodların kullanımının daha iyi anlaşılabilmesi için farklı parametrelerle örnekler incelenebilir. Bu sayede, algoritmalar ve nesne dizgilerinde daha iyi bir anlayış elde etmek mümkündür.
Dizilimler için örnek
Bu örnekte, bir dizilimdeki elemanların sıralanması ve aranması nasıl yapılır öğrenmeye odaklanacağız.
İlk olarak, bir dizi oluşturarak başlayalım:
Index | Value |
---|---|
0 | 13 |
1 | 7 |
2 | 22 |
3 | 3 |
Bu diziyi sıralamak için sort() fonksiyonunu kullanabiliriz.
std::sort(arr, arr + 4);
Şimdi, find() veya binary_search() fonksiyonlarını kullanarak bir elemanı dizide arayabiliriz.
int x = 7;bool result = std::binary_search(arr, arr + 4, x);
Burada, 'result' değişkenimiz 'true' olacaktır, çünkü 7, dizimizin bir elemanıdır.
Daha spesifik bir arama yapmak isterseniz, lower_bound() ve upper_bound() fonksiyonlarını kullanabilirsiniz.
int y = 11;auto lower = std::lower_bound(arr, arr + 4, y);auto upper = std::upper_bound(arr, arr + 4, y);
Bu durumda, 'lower' değişkenimiz, 'y' değeri için ilk kez karşılaşılan elemanı tutar. 'upper' değişkenimiz ise, 'y' değerinden büyük olan ilk elemanı tutar.
Yukarıdaki örnekler, bir dizideki elemanları sıralamanın ve aramanın nasıl yapılacağına dair sadece bir fikir vermektedir. STL kütüphanesinde bir dizi alternatif fonksiyon vardır, bu nedenle işiniz için en uygun olanı bulmak ve kullanmak isteyeceksiniz.