sort: জিনিসপত্র সাজাও, আর বলে দাও কোন ক্রমে

Kenji-র বইয়ের দোকানের নতুন catalogue-এর জন্য 100,000টা দাম সাজাতে হবে। Kenji দ্রুত জিনিস ভালোবাসে, তাই নিজের হাতেই একটা sort লিখে ফেলল: একটা insertion sort, যেটা প্রতিটা দাম তুলে নিয়ে বাঁয়ে সরাতে থাকে, যতক্ষণ না ঠিক জায়গায় বসে। Compiler Explorer-এর GCC 12-এ নয়বার চালিয়ে এটা নিল 872 থেকে 2,432 ms। ওই একই 100,000টা সংখ্যা std::sort এক লাইনেই সাজিয়ে দিল 5.7 থেকে 7.5 ms-এ। Kenji মাপার আগেই optimise করে বসেছিল। এই lesson সেই এক লাইন নিয়ে, আর তুমি কোন ক্রম চাও, সেটা ওকে কীভাবে বলবে, তা নিয়ে।

sort(v.begin(), v.end()): প্রথম জিনিস থেকে end পর্যন্ত

sort থাকে <algorithm> header-এ। ও নেয় দুইটা iterator, মানে জায়গা চিনিয়ে দেওয়ার সেই চিহ্ন, যেটা Module 2-এ দেখেছ। prices.begin() দেখায় প্রথম দামটা। prices.end() দেখায় শেষ দামের ঠিক পরের জায়গাটা, তাই range চলে প্রথম জিনিস থেকে end()-এর ঠিক আগ পর্যন্ত, ওই জায়গাটা বাদ দিয়ে। এই range-এর প্রতিটা জিনিস sort ছোট থেকে বড় ক্রমে বসিয়ে দেয়, ওই vector-এর ভিতরেই।

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

int main() {
    vector<int> prices{40, 15, 55, 20, 35};
    sort(prices.begin(), prices.end());
    cout << "sorted:";
    for (int p : prices) {
        cout << ' ' << p;
    }
    cout << '\n';
    return 0;
}

sorted: 15 20 35 40 55

তাই sort(v.begin(), v.end()) পুরো vector-টাকে জায়গায় বসেই সাজায়, আর end() হলো শেষ জিনিসের এক ধাপ পরের জায়গা, নিজে কখনো কোনো জিনিস না।

sort শুধু একটা প্রশ্নই করে

sort কখনো পুরো vector একসাথে দেখে না। বারবার ও দুইটা জিনিস নেয়, a আর b, আর একটাই প্রশ্ন করে: a কি b-এর আগে আসবে? কোনো নিয়ম না দিলে প্রশ্নটা হলো a < b। যে function এই প্রশ্নের উত্তর দেয়, তাকে বলে comparator। Widget-টা পাঁচটা দামের উপর GCC 12-এর নিজের sort আবার চালিয়ে দেখায়। Compiler Explorer-এ একটা program প্রতিটা প্রশ্ন লিখে রেখেছিল, আর widget ঠিক সেই ক্রমেই প্রশ্নগুলো দেখায়।

এগারোটা প্রশ্নেই পাঁচটা দাম সাজানো হয়ে গেল। প্রতিটা "হ্যাঁ"-তে sort একটা জিনিস বাঁয়ে সরিয়েছে, আর প্রতিটা "না"-তে জিনিসটা যেখানে ছিল সেখানেই রেখেছে। 16টা বা তার কম জিনিসে GCC 12-এর sort আসলে একটা insertion sort, Kenji-র মতোই একই idea। বড় vector আগে একটা দ্রুত plan পায়, সেটা দেখাবে lesson 05। তাই "সাজানো" মানে কী, sort নিজে জানেই না: ও শুধু জিজ্ঞেস করে, আর উত্তর যা বলে শুধু সেটুকুই সরায়।

প্রথম দিনেই যে syntax লাগবে

#include <algorithm>      sort and stable_sort
#include <functional>     greater

sort(first, last);                     increasing order, decided by <
sort(first, last, comp);               the order comp decides
stable_sort(first, last);              increasing, and equal items keep their order
stable_sort(first, last, comp);        the same, with your rule

sort(v.begin(), v.end());              the whole vector
sort(v.begin() + i, v.begin() + j);    places i to j - 1 only
sort(a, a + n);                        the first n items of an array
sort(v.begin(), v.end(), greater<int>());    decreasing order
sort(v.rbegin(), v.rend());            decreasing order, by sorting it backwards

তাই প্রতিটা call বলে কোথা থেকে শুরু, কোথায় থামা, আর চাইলে নিয়মটা।

একটা array: sort(a, a + n)

Learn C-তে দেখেছ, array-এর নাম ওর প্রথম জিনিসের pointer-এর মতো কাজ করে। a + 5 দেখায় পাঁচ নম্বর জিনিসের ঠিক পরের জায়গা। একটা pointer iterator-এর কাজ করতে পারে, তাই sort(a, a + 5) প্রথম পাঁচটা জিনিস সাজায়।

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

int main() {
    int a[] = {9, 4, 7, 1, 8};
    sort(a, a + 5);
    cout << "array:";
    for (int x : a) {
        cout << ' ' << x;
    }
    cout << '\n';
    return 0;
}

array: 1 4 7 8 9

তাই pointer-ও iterator: a দেখায় জায়গা 0, আর a + 5 দেখায় শেষ জিনিসের পরের জায়গা।

String সাজে character code ধরে

দুইটা string-এ < ওদের তুলনা করে অভিধানের মতো, একটা একটা character করে। প্রথম যে character-টা আলাদা, সেটাই ফয়সালা করে, ASCII table-এ ওর code দিয়ে। অঙ্ক আসে বড় হাতের অক্ষরের আগে, আর বড় হাতের অক্ষর আসে ছোট হাতের আগে।

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

int main() {
    vector<string> names{"zara", "Bob", "amara", "Kenji", "alice", "10", "9"};
    sort(names.begin(), names.end());
    cout << "sorted:";
    for (const string& name : names) {
        cout << ' ' << name;
    }
    cout << '\n';
    return 0;
}

sorted: 10 9 Bob Kenji alice amara zara

"10" আসে "9"-এর আগে, কারণ '1' (49) ছোট '9' (57)-এর চেয়ে, আর দ্বিতীয় character পর্যন্ত প্রশ্ন যায়ই না। Bob আর Kenji আসে alice-এর আগে, কারণ 'B' হলো 66, 'K' 75, আর 'a' 97। alice আর amara-র ফয়সালা হয় দ্বিতীয় অক্ষরে, 'l' আসে 'm'-এর আগে। তাই সাজানো string থাকে character code-এর ক্রমে, আর সেটা বর্ণমালার ক্রম হয় শুধু তখনই, যখন সব শব্দ একই case-এ লেখা।

বড় থেকে ছোট: greater<int>() নয়তো reverse iterator

বড় থেকে ছোট সাজাতে প্রশ্নটাই বদলে দাও: "a কি b-এর চেয়ে বড়?" greater<int>() ঠিক এটাই জিজ্ঞেস করে। আরেকটা উপায় হলো vector-টাকে উল্টো দিক থেকে পড়ে সাজানো: rbegin() আর rend() হলো reverse iterator, যেগুলো শেষ জিনিস থেকে প্রথমটার দিকে হাঁটে।

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

void show(const char* label, const vector<int>& v) {
    cout << label;
    for (int x : v) {
        cout << ' ' << x;
    }
    cout << '\n';
}

int main() {
    vector<int> v{40, 15, 55, 20, 35};
    sort(v.begin(), v.end(), greater<int>());
    show("greater:", v);

    vector<int> w{40, 15, 55, 20, 35};
    sort(w.rbegin(), w.rend());
    show("rbegin: ", w);
    return 0;
}

greater: 55 40 35 20 15
rbegin:  55 40 35 20 15

দুই লাইন একই। দ্বিতীয় call উল্টো দিকের পড়াটাকে বাড়তির দিকে সাজিয়েছে, তাই সামনে থেকে পড়লে সেটা কমতে থাকে। তাই ছোট থেকে বড় সাজিয়ে তারপর উল্টো করে print করার দরকার কখনো নেই: "বড় থেকে ছোট" কথাটা sort-কেই বলে দাও।

vector-এর শুধু একটা অংশ

দুইটা iterator যেকোনো range দেখাতে পারে, পুরো vector-ই হতে হবে এমন না। p.begin() + 1 দেখায় জায়গা 1, আর p.begin() + 5 দেখায় জায়গা 5, যেটা বাদ যায়। তাই এই call জায়গা 1 থেকে 4 সাজায়, আর কিছুতে হাত দেয় না।

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

int main() {
    vector<int> p{5, 1, 4, 2, 3, 9, 0};
    sort(p.begin() + 1, p.begin() + 5);
    cout << "places 1 to 4 sorted:";
    for (int x : p) {
        cout << ' ' << x;
    }
    cout << '\n';
    return 0;
}

places 1 to 4 sorted: 5 1 2 3 4 9 0

1, 4, 2 আর 3 হয়ে গেল 1 2 3 4। সামনের 5, আর পেছনের 9 আর 0, যেখানে ছিল সেখানেই রইল। Bob তাড়াহুড়ো করে "জায়গা 4 পর্যন্ত" বোঝাতে লিখেছিল p.begin() + 4, আর জায়গা 4 সাজানোই হলো না। তাই দ্বিতীয় iterator সবসময় দেখায় প্রথম সেই জায়গা, যেটা সাজানো হবে না।

তোমার নিজের নিয়ম: প্রথম lambda

sort-এর তৃতীয় argument হলো নিয়মটা। এখানে নিয়ম হলো "a আগে আসবে, যদি a শূন্যের বেশি কাছে থাকে"। এটা লেখা হয়েছে একটা lambda দিয়ে, মানে নামহীন ছোট্ট একটা function, যেটা যেখানে লাগে ঠিক সেখানেই লেখা হয়।

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

int main() {
    vector<int> d{-7, 3, -1, 5, -4};
    sort(d.begin(), d.end(), [](int a, int b) { return abs(a) < abs(b); });
    cout << "closest to zero first:";
    for (int x : d) {
        cout << ' ' << x;
    }
    cout << '\n';
    return 0;
}

closest to zero first: -1 3 -4 5 -7

[](int a, int b) { return abs(a) < abs(b); }-কে পড়ো sort-এর সেই একটা প্রশ্নের উত্তর হিসেবে। sort যতবার জিজ্ঞেস করে "a কি b-এর আগে আসবে?", lambda ততবার শূন্য থেকে দুইটার দূরত্ব তুলনা করে। <cstdlib>-এর abs minus চিহ্নটা ফেলে দেয়। Lambda-কে টুকরো টুকরো করে খুলে দেখাবে lesson 02। তাই ক্রম ঠিক করে নিয়ম, আর sort নিজে কখনো বদলায় না।

সমান জিনিস, আর stable_sort বাড়তি কী দেয়

দুইটা জিনিস tie, মানে সমানে সমান, যখন নিয়ম বলে কেউই অন্যটার আগে আসে না। Amara-র তাকে ছয়টা বই, প্রতিটার একটা দাম আর তাকের একটা অক্ষর, A থেকে F। দাম ধরে সাজালে তিনটা বইয়ের দাম 30, আর দুইটার 20। stable_sort কথা দেয়, সমান জিনিসগুলো ওদের পুরোনো ক্রমেই থাকবে। সাধারণ sort ওদের নিয়ে কোনো কথাই দেয় না।

struct Book {
    int price;
    char shelf;
};

bool byPrice(const Book& a, const Book& b) {
    return a.price < b.price;
}

stable_sort(books.begin(), books.end(), byPrice);

byPrice হলো একটা সাধারণ, নাম-ওয়ালা function হিসেবে লেখা comparator। ও দাম তুলনা করে, অক্ষরের দিকে তাকায়ই না। নিচের Example 3 এটাকে পুরোটা চালায়, আর widget সেটাই GCC 12-এ আবার চালিয়ে দেখায়।

GCC 12 তিনটা করে বইয়ের প্রতিটা অর্ধেক আলাদা করে সাজিয়েছে, তারপর দুই অর্ধেক মিশিয়েছে, যাকে বলে merge। দুইটা দাম সমান হলে merge আগে বাঁ অর্ধেকের বইটা নিয়েছে। তাই B রইল E-এর আগে, আর A, C আর F রইল পরপর। তাই "stable" মানে ঠিক এটুকুই: সমান জিনিসগুলো যে ক্রমে ঢুকেছিল, সেই ক্রমেই বেরোয়।

sort সমান জিনিসের ক্রম রাখবে, এই ভরসা কোরো না

ছোট input-এ GCC 12-এর সাধারণ sort ঘটনাচক্রে সমান জিনিসের ক্রম রেখে দেয়। 16টা বা তার কম জিনিসে এটা একটা insertion sort, যেটা কোনো জিনিসকে ওর সমান কাউকে পার করায় না। 17টা থেকে আগে একটা ধাপ চলে, যেটা একটা মানের দুই পাশে জিনিসগুলো ভাগ করে, আর তখন সমান জিনিস জায়গা বদলাতে পারে। এই program record-গুলোকে 60, 70 আর 80 mark দেয়, আর input-এর ক্রমে অক্ষর দেয় a, b, c, এভাবে।

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

struct Rec {
    int mark;
    char tag;
};

bool byMark(const Rec& a, const Rec& b) {
    return a.mark < b.mark;
}

void show(int n, const char* label, const vector<Rec>& v) {
    cout << n << ' ' << label;
    for (const Rec& r : v) {
        cout << ' ' << r.mark << r.tag;
    }
    cout << '\n';
}

int main() {
    for (int n : {16, 17}) {
        vector<Rec> v;
        for (int i = 0; i < n; i++) {
            v.push_back({60 + ((i * 5 + 1) % 3) * 10, char('a' + i)});
        }
        vector<Rec> s = v;
        vector<Rec> t = v;
        sort(s.begin(), s.end(), byMark);
        stable_sort(t.begin(), t.end(), byMark);
        show(n, "sort:       ", s);
        show(n, "stable_sort:", t);
    }
    return 0;
}

16 sort:        60b 60e 60h 60k 60n 70a 70d 70g 70j 70m 70p 80c 80f 80i 80l 80o
16 stable_sort: 60b 60e 60h 60k 60n 70a 70d 70g 70j 70m 70p 80c 80f 80i 80l 80o
17 sort:        60b 60q 60n 60k 60h 60e 70g 70j 70d 70m 70p 70a 80f 80i 80l 80c 80o
17 stable_sort: 60b 60e 60h 60k 60n 60q 70a 70d 70g 70j 70m 70p 80c 80f 80i 80l 80o

16টা record-এ দুই লাইন মিলে যায়। 17টায় sort 60q-কে বসিয়েছে দ্বিতীয় জায়গায়, আর 70a-কে 70-গুলোর একদম শেষে, অথচ stable_sort প্রতিটা সমান জিনিস অক্ষরের ক্রমে রেখেছে। ঠিক এই কারণেই Zara সবার আগে 17টা বা তার বেশি সমান key দিয়ে test করে। তাই সমান জিনিসের ক্রম রাখতে হলে stable_sort দিয়ে সেটা বলে দাও: অল্প কয়টা জিনিসের test-এ পার্থক্যটা ধরা পড়বে না।

সাজানোর খরচ: O(n log n)

Kenji-র insertion sort প্রতিটা নতুন জিনিসকে ওর আগের প্রতিটা বড় জিনিস পার করে সরায়। এলোমেলো সংখ্যায় সেটা মোটামুটি n²/4 বার সরানো, তাই জিনিস দশগুণ হলে সময় লাগে মোটামুটি একশো গুণ। std::sort-এর লাগে মোটামুটি n log₂ n-টা তুলনা, যেখানে log₂ n হলো n-কে কতবার অর্ধেক করা যায়: 100,000-এর জন্য প্রায় 17। এটাকে লেখা হয় O(n log n)। C++11 থেকে standard এটা worst case-এও দাবি করে। Compiler Explorer-এর GCC 12-এ আটবার চালিয়ে Kenji-র সংখ্যাগুলো এমন এল:

100,000টা জিনিসে হাতে লেখা sort নিয়েছে 150 গুণেরও বেশি সময়। আরেকটা run, একদম প্রথমটা, হাতে লেখা sort-এ নিয়েছিল 2,432 ms, সেজন্যই মাপাটা বারবার করা হয়েছে। Buffer-এর জন্য memory ধার পেলে stable_sort-এর খরচও O(n log n), ওর সংখ্যাগুলো দেবে lesson 02। তাই বড় vector-এ machine-এর চেয়ে plan বেশি জরুরি: std::sort নাও, আর ওকে ওর প্রশ্নগুলো করতে দাও।

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

int main() {
    vector<int> prices{120, 45, 300, 45, 80};
    sort(prices.begin(), prices.end());
    cout << "low to high:";
    for (int p : prices) {
        cout << ' ' << p;
    }
    cout << '\n';

    sort(prices.begin(), prices.end(), greater<int>());
    cout << "high to low:";
    for (int p : prices) {
        cout << ' ' << p;
    }
    cout << '\n';
    return 0;
}

low to high: 45 45 80 120 300
high to low: 300 120 80 45 45

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

void show(const char* label, const vector<string>& names) {
    cout << label;
    for (const string& name : names) {
        cout << ' ' << name;
    }
    cout << '\n';
}

int main() {
    vector<string> names{"maria", "Zara", "bob", "Amara", "kenji"};
    sort(names.begin(), names.end());
    show("as typed:  ", names);

    for (string& name : names) {
        for (char& c : name) {
            c = tolower(c);
        }
    }
    sort(names.begin(), names.end());
    show("lowercase: ", names);
    return 0;
}

as typed:   Amara Zara bob kenji maria
lowercase:  amara bob kenji maria zara

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

struct Book {
    int price;
    char shelf;
};

bool byPrice(const Book& a, const Book& b) {
    return a.price < b.price;
}

int main() {
    vector<Book> books{{30, 'A'}, {20, 'B'}, {30, 'C'}, {10, 'D'}, {20, 'E'}, {30, 'F'}};
    stable_sort(books.begin(), books.end(), byPrice);
    for (const Book& b : books) {
        cout << b.price << ' ' << b.shelf << '\n';
    }
    return 0;
}

10 D
20 B
20 E
30 A
30 C
30 F

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

void topThree(vector<int> scores) {
    sort(scores.begin(), scores.end(), greater<int>());
    int shown = min(3, (int)scores.size());
    cout << "top " << shown << ':';
    for (int i = 0; i < shown; i++) {
        cout << ' ' << scores[i];
    }
    cout << '\n';
}

int main() {
    topThree({70, 95, 60, 95, 88, 40});
    topThree({50, 75});
    return 0;
}

top 3: 95 95 88
top 2: 75 50

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

int main() {
    vector<int> v{3, 1, 2};
    sort(v.begin(), v.end());
    return 0;
}

vector<int> v{3, 1, 2};
sort(v.begin(), v.end);

vector<int> v{3, 1, 2};
sort(v.begin(), v.end(), greater<int>);

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

struct Student {
    string name;
    int mark;
};

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n = 0;
    cin >> n;
    vector<Student> roll(n);   // in roll order, the order the papers were marked
    for (Student& s : roll) {
        cin >> s.name >> s.mark;
    }

    // Put roll in board order: the highest mark first, and students
    // with equal marks in roll order. Then print one student per line.

    return 0;
}

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

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> score(n);
    for (int& s : score) {
        cin >> s;
    }

    // Drop the k lowest and the k highest scores, and print the sum of
    // the scores that are left.

    return 0;
}

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

int main() {
    int n;
    cin >> n;
    vector<int> height(n);
    for (int& h : height) {
        cin >> h;
    }

    // Print sorted if the shelf is already in order. Otherwise find the
    // first and the last place that differ from the sorted order. Print
    // yes and those two places, counted from 1, if reversing that part
    // sorts the shelf, and no if it does not.

    return 0;
}

এরপর lesson 02 সাজানোর প্রতিটা call আর নিয়ম লেখার প্রতিটা উপায় একটা একটা করে দেখাবে, প্রতিটার খরচসহ।