Çalıştırılabilir C++ Dokümanları: Sıralama

Q: C++'ta bir vektör nasıl sıralanır?

başlığını ekleyin ve sort(v.begin(), v.end()) çağrısını yapın. Bu, elemanları operator< kullanarak yerinde artan sırada sıralar. Bir diziyi sıralamak için arr ve arr + n (veya begin(arr) / end(arr)) geçin.

Q: C++'ta azalan sırada nasıl sıralama yapılır?

a > b döndüren bir karşılaştırıcı geçin: sort(v.begin(), v.end(), [](int a, int b){ return a > b; });. içinden gelen yerleşik sort(v.begin(), v.end(), greater ()); ifadesini de kullanabilirsiniz.

Q: C++'ta karşılaştırıcım neden std::sort'u çökertiyor?

Karşılaştırıcınız bir katı zayıf sıralama olmalıdır: iki argüman eşit olduğunda false döndürmesi gerekir. = kullanmak (eşit elemanlar için true döndürürler) bu kuralı bozar ve tanımsız davranıştır; std::sort sınır dışını okuyup çökebilir. Her zaman ile karşılaştırın.

Sıralama Sadece Başka Bir Algoritma

Önceki sayfada, standart kütüphanenin yineleyiciler aracılığıyla herhangi bir aralık üzerinde çalışan hazır algoritmalar sunduğunu gördünüz. Sıralama, en sık başvuracağınız algoritmadır ve kendi sayfasına sahip olmasının nedeni birkaç keskin köşesinin olmasıdır: özel sıralamalar, kararlılık ve bozduğunuzda size yanlış bir cevap yerine tanımsız davranış veren bir kural.

İş atı, <algorithm> içindeki std::sort'tur. Ona bir aralığın başını ve sonunu verirsiniz, o da elemanları yerinde artan sırada yeniden düzenler:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> nums = {5, 2, 8, 1, 9, 3};

    sort(nums.begin(), nums.end());   // artan, yerinde

    for (int n : nums) cout << n << " ";  // 1 2 3 5 8 9
    cout << "\n";
    return 0;
}

Hiçbir kopya oluşturulmaz; vektörün kendisi yeniden düzenlenir. Arka planda std::sort genellikle bir introsort'tur (heapsort'a geri düşen quicksort) ve ortalamada size O(n log n) verir. Bu, neredeyse her zaman kendi sıralamanızı yazmaktan daha hızlı ve çok daha az hataya açıktır.

Düz C dizilerinde de çalışır; aralığı yalnızca işaretçilerle tanımlarsınız:

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int arr[] = {40, 10, 30, 20};
    int n = 4;

    sort(arr, arr + n);               // veya sort(begin(arr), end(arr));

    for (int x : arr) cout << x << " ";  // 10 20 30 40
    return 0;
}

Karşılaştırıcı ile Özel Sıra

Varsayılan olarak std::sort, elemanları operator< ile sıralar. Farklı sıralamak için üçüncü bir argüman geçin: iki eleman alan ve birincisinin ikinciden önce gelmesi gerekiyorsa true döndüren bir karşılaştırıcı.

Lambda doğal bir uyum sağlar. Azalan sıra sadece a > b'dir:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> nums = {5, 2, 8, 1, 9, 3};

    sort(nums.begin(), nums.end(), [](int a, int b) {
        return a > b;   // a daha büyükse "a, b'den önce" -> azalan
    });

    for (int n : nums) cout << n << " ";  // 9 8 5 3 2 1
    cout << "\n";
    return 0;
}

Yerleşik tipler üzerinde düz azalan sıra gibi yaygın bir durum için kütüphane, <functional> içinden hazır bir karşılaştırıcı olan greater<T>()'yi bile sunar:

#include <functional>
sort(nums.begin(), nums.end(), greater<int>());  // a > b ile aynı

Karşılaştırıcı, değerin kendisi dışında bir şeye göre sıralama yapmanın da yoludur; örneğin, dizeleri alfabetik yerine uzunluğa göre sıralamak:

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int main() {
    vector<string> words = {"pear", "fig", "banana", "kiwi"};

    sort(words.begin(), words.end(), [](const string& a, const string& b) {
        return a.size() < b.size();   // önce kısa kelimeler
    });

    for (const string& w : words) cout << w << " ";  // fig kiwi pear banana
    cout << "\n";
    return 0;
}

Birkaç bayttan büyük her şey için (string gibi) karşılaştırıcı parametrelerini const& ile alın; her karşılaştırmada her elemanı kopyalamak tamamen israftır.

Struct'ları Bir Alana Göre Sıralama

Gerçek programlarda genellikle struct koleksiyonlarını alanlarından birine göre sıralarsınız. Karşılaştırıcı sadece önemsediğiniz alana erişir. Burada insanları yaşa göre, en gençten başlayarak sıralıyoruz:

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

struct Person {
    string name;
    int age;
};

int main() {
    vector<Person> people = {
        {"Ada", 36}, {"Linus", 25}, {"Grace", 41}, {"Dennis", 25}
    };

    sort(people.begin(), people.end(), [](const Person& a, const Person& b) {
        return a.age < b.age;
    });

    for (const Person& p : people)
        cout << p.name << " (" << p.age << ")\n";
    return 0;
}

Linus ile Dennis'in ikisinin de 25 yaşında olduğuna dikkat edin. Burada özgün göreli sıralarında çıktılar, ama std::sort bunu garanti etmez. Eşit elemanların göreli sırası önemliyse, bunu koruyan (küçük bir performans maliyetiyle) std::stable_sort kullanın:

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

struct Person { string name; int age; };

int main() {
    vector<Person> people = {
        {"Ada", 36}, {"Linus", 25}, {"Grace", 41}, {"Dennis", 25}
    };

    stable_sort(people.begin(), people.end(),
        [](const Person& a, const Person& b) { return a.age < b.age; });

    for (const Person& p : people)
        cout << p.name << " (" << p.age << ")\n";
    // Linus, Dennis'ten önce kalır - giriş sıraları korunur
    return 0;
}

Eşitlikleri kasıtlı olarak çözmek için (örneğin yaşa, sonra ada göre alfabetik sıralamak) ikincil anahtarı yalnızca birincil anahtarlar eşit olduğunda karşılaştırın. std::tie bunu temiz hale getirir:

#include <iostream>
#include <vector>
#include <string>
#include <tuple>
#include <algorithm>
using namespace std;

struct Person { string name; int age; };

int main() {
    vector<Person> people = {
        {"Ada", 36}, {"Linus", 25}, {"Grace", 41}, {"Dennis", 25}
    };

    sort(people.begin(), people.end(), [](const Person& a, const Person& b) {
        return tie(a.age, a.name) < tie(b.age, b.name);  // yaş, sonra ad
    });

    for (const Person& p : people)
        cout << p.name << " (" << p.age << ")\n";  // Dennis ve Linus 25, alfabetik
    return 0;
}

Katı Zayıf Sıralama Tuzağı

Bu, C++ sıralamasındaki en tehlikeli tek hatadır, çünkü size yanlış bir cevap vermez; çoğu zaman bir çökme veya sınır dışı okuma anlamına gelen tanımsız davranış verir.

std::sort, karşılaştırıcınızın bir katı zayıf sıralama tanımlamasını gerektirir. Pratik kural: herhangi bir x elemanı için comp(x, x) false olmalıdır. Başka bir deyişle, bir eleman asla kendisinden "önce" değildir. < ve > size tam olarak bunu verir, <= ve >= ise tam olarak bunu bozar:

// HATA: a == b olduğunda true döndürür ve katı zayıf sıralamayı ihlal eder.
sort(v.begin(), v.end(), [](int a, int b) {
    return a <= b;   // tanımsız davranış - bazı girdilerde çökebilir
});

<= ile karşılaştırıcı, 5'in başka bir 5'ten önce geldiğini iddia eder ki bu çelişkilidir. std::sort o zaman bir işaretçiyi aralığın sonunun ötesine yürütebilir. Küçük girdiler bazen çalışıyor gibi görünür ve bu da bu hatayı korkutucu yapar: testlerinizden geçip üretimde çökebilir. Çözüm sadece <:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3};

    sort(v.begin(), v.end(), [](int a, int b) {
        return a < b;   // doğru: eşit olduğunda false
    });

    for (int x : v) cout << x << " ";
    cout << "\n";
    return 0;
}

İkinci klasik tuzak: sıralama, aralığın içine işaret eden her şeyi geçersiz kılar. Sıralamadan önce kaydettiğiniz yineleyiciler, işaretçiler ve indeksler, elemanlar yer değiştirdiği için sonrasında artık aynı mantıksal elemanı göstermez. İhtiyaç duyduğunuz herhangi bir konumu sıralamadan sonra yeniden türetin, asla önce değil.

Bir Aralığın Bir Kısmını Sıralama

Bazen her şeyin sıralanmasına ihtiyacınız yoktur; sadece ilk birkaçını istersiniz. İlk üçü okumak için tüm vektörü sıralamak israftır. std::partial_sort, yalnızca istediğiniz elemanları düzenler ve geri kalanını belirsiz sırada bırakır; bu daha ucuzdur:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> v = {5, 2, 8, 1, 9, 3, 7};

    // En küçük 3'ü sırayla başa koy. Geri kalan belirsiz.
    partial_sort(v.begin(), v.begin() + 3, v.end());

    for (int i = 0; i < 3; i++) cout << v[i] << " ";  // 1 2 3
    cout << "\n";
    return 0;
}

Ve yalnızca belirli bir konumda bulunacak tek elemana ihtiyacınız varsa (örneğin medyan), std::nth_element daha da az iş yapar: doğru elemanı o indekse yerleştirir, daha küçük olan her şeyi önüne ve daha büyük olan her şeyi arkasına koyar; tümü ortalamada O(n)'de.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> v = {5, 2, 8, 1, 9, 3, 7};
    size_t mid = v.size() / 2;

    nth_element(v.begin(), v.begin() + mid, v.end());

    cout << "median is " << v[mid] << "\n";  // 5
    return 0;
}

"Tamamen sıralı", problemin gerçekten ihtiyaç duyduğundan fazlaysa bunlara başvurun; büyük verilerde gerçek zaman kazandırırlar.

Sıradaki: Şablonlar

Aynı std::sort'un int, string ve kendi Person struct'ınızı ele aldığını ve greater<int>()'nin aynı kolaylıkla greater<string>() olabileceğini fark ettiniz mi? Bu genellik sihir değildir; tek bir kod parçasının, çağıranın taktığı herhangi bir tip için çalışmasını sağlayan mekanizma olan şablonlardır. Sonraki sayfada kendi şablonlu fonksiyonlarınızı ve sınıflarınızı nasıl yazacağınızı göreceğiz; böylece kodunuz, kullandığınız algoritmalar kadar tipten bağımsız olabilir.

Sıkça Sorulan Sorular

C++'ta bir vektör nasıl sıralanır?

<algorithm> başlığını ekleyin ve sort(v.begin(), v.end()) çağrısını yapın. Bu, elemanları operator< kullanarak yerinde artan sırada sıralar. Bir diziyi sıralamak için arr ve arr + n (veya begin(arr) / end(arr)) geçin.

C++'ta azalan sırada nasıl sıralama yapılır?

a > b döndüren bir karşılaştırıcı geçin: sort(v.begin(), v.end(), [](int a, int b){ return a > b; });. <functional> içinden gelen yerleşik sort(v.begin(), v.end(), greater<int>()); ifadesini de kullanabilirsiniz.

C++'ta karşılaştırıcım neden std::sort'u çökertiyor?

Karşılaştırıcınız bir katı zayıf sıralama olmalıdır: iki argüman eşit olduğunda false döndürmesi gerekir. <= veya >= kullanmak (eşit elemanlar için true döndürürler) bu kuralı bozar ve tanımsız davranıştır; std::sort sınır dışını okuyup çökebilir. Her zaman < veya > ile karşılaştırın.

İlgili kavramlar