Comparison rule se searching aur sorting
qsort aur bsearch ko arrays, element sizes, callbacks, ordering aur duplicate values se jodein.
Is chapter mein8 sections
Values sort karne ke liye library function ko pehle aane wali value ka rule chahiye. Efficient search ke liye data agreed rule se arranged hona chahiye. C ke qsort aur bsearch storage information ke saath callback se rule lete hain.
1. Comparator relationship batata hai
First argument pehle aaye toh comparator negative, equal compare ho toh zero aur baad mein aaye toh positive return karta hai. Sign matter karta hai. qsort do element pointers deta hai. bsearch key pointer pehle aur element pointer second deta hai. Integer example mein dono ka type same hai; general interface mein key ka type different ho sakta hai.
Ints ke liye (a > b) - (a < b) overflow ke bina required sign deta hai. a - b distant signed values par overflow kar sakta hai. Example INT_MIN aur INT_MAX se boundaries bhi check karta hai.
2. Actual array describe karein
#include <assert.h>
#include <limits.h>
#include <stddef.h>
#include <stdlib.h>
static int compare_ints(const void *left, const void *right)
{
int a = *(const int *)left;
int b = *(const int *)right;
return (a > b) - (a < b);
}
int main(void)
{
int values[] = {INT_MAX, -1, 0, INT_MIN, -1};
size_t count = sizeof values / sizeof values[0];
qsort(values, count, sizeof values[0], compare_ints);
assert(values[0] == INT_MIN && values[count - 1] == INT_MAX);
for (size_t i = 1; i < count; ++i) assert(values[i - 1] <= values[i]);
int key = -1;
int *found = bsearch(&key, values, count, sizeof values[0], compare_ints);
assert(found != NULL && *found == -1);
key = 7;
assert(bsearch(&key, values, count, sizeof values[0], compare_ints) == NULL);
assert(bsearch(&key, values, 0, sizeof values[0], compare_ints) == NULL);
qsort(values, 0, sizeof values[0], compare_ints);
return 0;
}
Call first element, count, element size aur comparator deti hai. Storage mein stated elements hone chahiye aur qsort ko unhein modify karna hota hai. Pointer automatically original array count nahi batata. Complete array visible ho wahan count compute karein, ya separately validated count pass karein.
3. Equal keys stable order promise nahi karte
Comparison rule consistent honi chahiye aur used values ki ordering define karni chahiye. Current element address ya unrelated random choice se answer na badlein. Records ek field se equal compare hon toh qsort unhein reorder kar sakta hai. Deterministic order chahiye toh deliberate tie-breaker add karein.
qsort naam quicksort algorithm, particular complexity bound ya stable sorting guarantee nahi karta. Yeh implementation ya algorithm-selection questions hain. Portable interface apne contract ke under ordering behavior promise karta hai.
4. Compatible arrangement par search karein
Example same comparator se search karne se pehle array fully sort karta hai. bsearch ke liye yeh clear sufficient arrangement hai. Precise rule key ke relative smaller, equal aur larger elements ka partition require karta hai. Comparator ko key pehle aur element second milta hai; complex key types mein interface dhyaan rakhein.
Successful result original array ke andar point karta hai. Allocated copy nahi hai, isliye free na karein. Array lifetime aur later storage changes pointer validity govern karte hain. Kai elements equal compare hon toh bsearch koi bhi matching element de sakta hai; first ki guarantee nahi.
5. Result use karne se pehle absence check karein
Missing key par null pointer milta hai. Zero-element search bhi null deti hai, lekin pointer arguments valid hone chahiye. Example zero count par bhi real key aur real array pass karta hai. Empty range ko arbitrary invalid addresses justify karne ke liye use na karein.
Do records ke keys equal hon toh kya qsort original relative order rakhega?
Explanation padhein
Nahi. qsort stable ordering promise nahi karta. Later rule ko woh order chahiye toh suitable stable algorithm ya explicit tie-breaker choose karein.
Primary references aur aage padhne ke links
- WG14 N1570 — public C11 draft: 7.22.5: stable C17 searching/sorting contracts.
- WG14 N3096 — public C23 draft: 7.24.5.1: C23 bsearch qualification-sensitive interface.
Aage badhne se pehle
- Comparator result ke sign se consistent ordering deta hai.
- qsort equal elements reorder kar sakta hai aur particular algorithm promise nahi karta.
- bsearch ko required key-relative arrangement chahiye aur koi bhi equal match mil sakta hai.
In ideas ko alag rakhein
- Comparator subtraction / Safe sign comparison
- Distant signed keys subtract karne par overflow ho sakta hai; relational comparisons us subtraction ke bina required sign de sakti hain.
Array sort karne aur comparison callback se search karne ke beech kya consistent rehna chahiye?
Optional: bolkar samjhein ya note rakhein. Tayyar hon toh aage badh sakte hain.Apni understanding check karein
Optional hai. Answers save ya send nahi hote; chapter kabhi lock nahi hota.
Har choice ki explanation padhein
- Comparator ko hamesha exactly 1 return karna chahiye.
Comparison rule ko required signs se less, equal aur greater distinguish karna hota hai.
- Saare subtraction results automatically Boolean hain.
Ordinary integer subtraction zero aur one tak restricted nahi.
- Signed subtraction overflow karke valid ordering express karne mein fail ho sakti hai.
✓ Sahi reasoning. Potentially overflowing difference ke bajay safe comparisons aur consistent ordering contract use karein.
C17
Agla idea padhne ke liye tayyar?
Mark this chapter as read whenever you feel ready.