Sorting Algorithms

Sorting क्या है?

Sorting का मतलब array को क्रम में लगाना है — आमतौर पर छोटे से बड़े। यह programming के सबसे आम कामों में से एक है, और हाथ से sort लिखना loops, comparisons और swapping एक साथ सिखाता है। यहाँ तीन classic beginner algorithms हैं, हर एक वही काम अलग तरीके से करता है।

तीनों array को जगह पर sort करते हैं और वही helper साझा करते हैं — दो elements का swap।

Bubble sort

हर पड़ोसी जोड़े की तुलना करें और गलत क्रम में होने पर swap करें। हर pass में सबसे बड़ी value अंत में "bubble" हो जाती है।

void bubbleSort(int a[], int n) {
    for (int i = 0; i < n - 1; i++)
        for (int j = 0; j < n - 1 - i; j++)
            if (a[j] > a[j + 1]) {
                int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t;
            }
}

Dry run {5, 2, 4} पर — पहला pass: 5 और 2 तुलना → swap → {2,5,4}; 5 और 4 तुलना → swap → {2,4,5}। Sorted।

Selection sort

Unsorted हिस्से में सबसे छोटा element ढूँढें और उसे अगली स्थिति पर रखें। दोहराएँ।

void selectionSort(int a[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int min = i;
        for (int j = i + 1; j < n; j++)
            if (a[j] < a[min]) min = j;   // sabse chhota dhoondhein
        int t = a[i]; a[i] = a[min]; a[min] = t;  // use rakhein
    }
}

हर दौर बचे हुए में से न्यूनतम चुनकर उसे जगह पर swap करता है — तो यह हर दौर में अधिकतम एक swap करता है।

Insertion sort

हर element को लेकर पहले से sorted elements में उसकी सही जगह पर सरका दें, जैसे हाथ में ताश के पत्ते क्रम में लगाना।

void insertionSort(int a[], int n) {
    for (int i = 1; i < n; i++) {
        int key = a[i], j = i - 1;
        while (j >= 0 && a[j] > key) {   // bade ko daayein shift karein
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = key;                 // key ko jagah par rakhein
    }
}

तीनों की तुलना

तीनों O(n²) हैं, छोटे arrays के लिए ठीक। बड़े data के लिए quicksort जैसे तेज़ O(n log n) तरीके इस्तेमाल होते हैं। Sorted array में item ढूँढने को इन्हें binary search से जोड़ें।

आम गलतियाँ

• बहुत आगे loop करके array के पार पढ़ना (n - 1 सीमाओं का ध्यान रखें)।
• बिना temporary variable के swap करना, एक value खो देना।
• Insertion sort में while loop के बाद key रखना भूलना।
• < बनाम > गलत तरीके से तुलना करना, गलत दिशा में sort।

सारांश

• Sorting array को क्रम में लगाता है; C में आपके लिए स्वतः sort नहीं।
• Bubble sort पड़ोसियों को तब तक swap करता है जब तक कोई swap न बचे।
• Selection sort बार-बार सबसे छोटा बचा element रखता है।
• Insertion sort हर element को sorted हिस्से में सरकाता है; लगभग-sorted पर बढ़िया।
• तीनों O(n²) हैं — छोटे arrays के लिए अच्छे; बड़े data के लिए O(n log n) तरीके इस्तेमाल करें।