YOUR C LEARNING COMPANION

Kahan se padhein?

Learning path
Program bananaChapter 48 of 73

Comparison rule se searching aur sorting

qsort aur bsearch ko arrays, element sizes, callbacks, ordering aur duplicate values se jodein.

5 min readDevelopingC17 baseline
Offline reading
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

Complete C17 program
#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.

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.

Sochkar dekhein

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

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.
Apne words mein samjhaayein

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.

Arbitrary int values ke liye return a - b; bad comparison rule kyun ho sakta hai?
Har choice ki explanation padhein
  1. Comparator ko hamesha exactly 1 return karna chahiye.

    Comparison rule ko required signs se less, equal aur greater distinguish karna hota hai.

  2. Saare subtraction results automatically Boolean hain.

    Ordinary integer subtraction zero aur one tak restricted nahi.

  3. 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.

CHAPTER 48 / 73

Is chapter mein

Comparison rule se searching aur sorting

Search all 73 chapters in both languages.EN + HG

Try “pointer”, “why int”, or “undefined behavior”.

Concepts connect. Follow your curiosity.↑ ↓ to explore · Enter to open
MAKE YOURSELF COMFORTABLE

Your reading space

Appearance

A clear canvas with balanced contrast.

Text size

100%
AA

Reading tools

Your data stays in this browser

Export a backup before changing browsers or replacing an older version of the reader.

YOUR PERSONAL MARGINS

My notebook

Saved on this device
A LITTLE CLARITY

The glossary

A starting meaning, then a chapter to go deeper.

A QUICK DEFINITION

A little clarity

Read the full explanation →

A thought worth keeping