1. qsort function को सारांश
C भाषा को मानक पुस्तकालयमा उपलब्ध qsort function एरेभित्रका तत्वहरूलाई क्रमबद्ध गर्नको लागि एक शक्तिशाली उपकरण हो।qsort तेज डेटा क्रमबद्ध गर्न क्विकसोर्ट एल्गोरिदम प्रयोग गर्दछ, र अत्यन्त प्रभावकारी छ। यस खण्डमा, qsort को मूलभूत कार्यविधि व्याख्या गरिनेछ, र किन यो function महत्त्वपूर्ण छ भन्ने कुरा स्पष्ट गरिनेछ।
qsort भनेको के हो?
qsort एरे वा सूची जस्ता डेटा लाई प्रयोगकर्ता-परिभाषित तुलना function को आधारमा क्रमबद्ध गर्ने सामान्य function हो। यो C भाषा को मानक function हो, र धेरै विकास वातावरणहरूमा व्यापक रूपमा प्रयोग गरिन्छ। उदाहरणका लागि, पूर्णांक एरे, स्ट्रिङ एरे, र यहाँसम्म कि संरचना (struct) समावेश गर्ने डेटा पनि प्रभावकारी रूपमा क्रमबद्ध गर्न सकिन्छ।
#include <stdio.h>
#include <stdlib.h>
int compare(const void *a, const void *b) {
return (*(int*)a - *(int*)b);
}
int main() {
int values[] = {40, 10, 100, 90, 20, 25};
size_t values_len = sizeof(values)/sizeof(values[0]);
qsort(values, values_len, sizeof(int), compare);
for(int i = 0; i < values_len; i++) {
printf("%d ", values[i]);
}
return 0;
}उपरोक्त कोड पूर्णांक एरेलाई qsort प्रयोग गरेर क्रमबद्ध गर्ने आधारभूत उदाहरण हो। यहाँ, तुलना function प्रयोग गरेर सानो-ठूलो सम्बन्ध निर्धारण गरी एरेको क्रमबद्धता गरिन्छ।
2. qsort को आर्गुमेन्टहरू र प्रयोग
qsortको प्रोटोटाइप तलको जस्तै छ:
void qsort(void *base, size_t num, size_t size, int (*compar)(const void *, const void *));आर्गुमेन्टको विवरण
- base: सजावट गरिने एरेको सुरुको पोइन्टर।
- num: एरेको तत्वहरूको संख्या।
- size: प्रत्येक तत्वको आकार (बाइटमा)।
- compar: तुलना कार्यको पोइन्टर।
यो कार्यले तुलना कार्यको आधारमा तत्वहरूलाई क्रमबद्ध गर्दछ।compar दुवै तत्वलाई आर्गुमेन्टको रूपमा लिन्छ र कुन ठूलो छ भन्ने मान फिर्ता गर्ने कार्य हो। यो लचकता विभिन्न डेटा प्रकारहरूलाई क्रमबद्ध गर्न सम्भव बनाउँछ।
तुलना कार्यको निर्माण
तुलना कार्य qsort को कार्यको मुख्य कुञ्जी हो। तलको जस्तै, तत्वहरू बीच तुलना गर्ने कार्यलाई परिभाषित गर्नुहोस्।
int compare(const void *a, const void *b) {
return (*(int*)a - *(int*)b);
}यो कार्यले a र b को मान तुलना गरी, a सानो भए नकारात्मक मान, बराबर भए 0, ठूलो भए सकारात्मक मान फिर्ता गर्दछ। यसले qsort लाई एरेलाई आरोही क्रममा क्रमबद्ध बनाउँछ।
3. qsort को आन्तरिक कार्य: क्विकसोर्ट एल्गोरिदम
qsort ले क्विकसोर्ट नामक एल्गोरिदमलाई आन्तरिक रूपमा प्रयोग गर्दछ। क्विकसोर्ट विभाजन-शासक विधि प्रयोग गर्ने एल्गोरिदम हो, र तलको चरणहरूमा कार्य गर्दछ:
- पिभट चयन: एरेको मध्य भाग वा अन्तिम तत्वलाई पिभट (आधार) को रूपमा चयन गरिन्छ।
- विभाजन: पिभट भन्दा साना तत्वहरूलाई बायाँपट्टि, ठूलो तत्वहरूलाई दायाँपट्टि सारिन्छ।
- पुनरावर्ती क्रमबद्धता: प्रत्येक उप-एरेमा पुनरावर्ती रूपमा समान कार्य दोहोर्याइन्छ।
यो विभाजन र एकीकरणको दोहोर्याइले एरेलाई प्रभावकारी रूपमा क्रमबद्ध गर्दछ। क्विकसोर्टको औसत गणनात्मक जटिलता O(n log n) हो, र अन्य क्रमबद्ध एल्गोरिदमहरूसँग तुलना गर्दा अत्यन्त तेज छ। तर, सबैभन्दा खराब केस (पहिले नै क्रमबद्ध एरे आदि) मा O(n^2) हुन सक्छ, त्यसैले सावधानी आवश्यक छ।
4. तुलना कार्य बनाउने तरिका
qsort को शक्ति यो हो कि विभिन्न डेटा प्रकारहरूका लागि कस्टम तुलना कार्यहरू बनाउन सकिन्छ। तल, विभिन्न डेटा प्रकारहरूका लागि तुलना कार्यका उदाहरणहरू देखाइन्छ।
इन्टिजर तुलना कार्य
int compare_int(const void *a, const void *b) {
return (*(int*)a - *(int*)b);
}स्ट्रिङ तुलना कार्य
int compare_str(const void *a, const void *b) {
return strcmp(*(const char**)a, *(const char**)b);
}स्ट्रक्चर तुलना कार्य
struct Person {
int id;
const char* name;
};
int compare_person(const void *a, const void *b) {
return ((struct Person*)a)->id - ((struct Person*)b)->id;
}यसरी,qsort ले तुलना कार्यलाई अनुकूलन गरेर, एरेको सामग्री अनुसार लचिलो सॉर्ट सम्भव हुन्छ।
5. qsort प्रयोग गरेर संरचना एरेको सॉर्ट
संरचना समावेश गर्ने एरेलाई सॉर्ट गर्दा पनि、qsort धेरै प्रभावकारी छ। उदाहरणका लागि, तलको जस्तैPerson संरचना एरेलाईid फिल्डद्वारा सॉर्ट गर्ने केसलाई विचार गरौं।
struct Person people[] = {
{1, "Alice"},
{3, "Charlie"},
{2, "Bob"}
};
qsort(people, 3, sizeof(struct Person), compare_person);compare_person फंक्शन प्रयोग गरेरid लाई आधार बनाएर सॉर्ट गर्दा、Alice, Bob, Charlie को क्रममा पुन: क्रमबद्ध गर्न सकिन्छ।
6. प्रदर्शन अनुकूलन र अन्य एल्गोरिदमहरूसँग तुलना
Quick sort को प्रदर्शन
Quick sort यादृच्छिक डेटा संग काम गर्दा अत्यन्त प्रभावकारी हुन्छ, औसत O(n log n) गणनात्मक जटिलता हुन्छ। तर, यदि क्रमबद्ध गर्नुपर्ने डेटा पहिले नै क्रमबद्ध छ भने, सबैभन्दा खराब अवस्थामा O(n^2) गणनात्मक जटिलता हुन सक्छ। यस कारणले, यादृच्छिक डेटा सेटहरूमा Quick sort प्रभावकारी हुन्छ, तर विशेष शर्तहरूमा अन्य एल्गोरिदमहरू विचार गर्नु महत्त्वपूर्ण छ।
Heap sort सँग तुलना
Heap sort सबैभन्दा खराब अवस्थामा पनि O(n log n) गणनात्मक जटिलता कायम राख्दछ, जसले Quick sort भन्दा स्थिर प्रदर्शन प्रदान गर्दछ। तर, सामान्यतया Quick sort औसतमा तेज हुन्छ, त्यसैले यादृच्छिक डेटा सेटहरूमा Quick sort सिफारिस गरिन्छ।
Merge sort सँग तुलना
Merge sort पनि O(n log n) गणनात्मक जटिलता राख्छ, र स्थिर क्रमबद्ध एल्गोरिदम हो। Merge sort स्थिरता (समान मानहरू मूल क्रमलाई कायम राख्ने) लाई महत्व दिने अवस्थामा उपयुक्त हुन्छ। Quick sort अस्थिर क्रमबद्ध एल्गोरिदम हो, जसले समान मानहरूको क्रम कायम राख्दैन, तर सामान्य प्रयोगमा यो भिन्नता प्रायः समस्या बन्दैन।
7. सारांश
qsort C भाषामा उपलब्ध शक्तिशाली सॉर्ट फङ्क्शन हो, र यसको लचिलोपन र उच्च गति धेरै प्रोग्रामहरूमा प्रयोग गरिन्छ। कस्टम तुलना फङ्क्शन प्रयोग गरेर, विभिन्न डेटा प्रकारहरू वा स्ट्रक्चरको एरेलाई सॉर्ट गर्न सकिन्छ, जसले यसको व्यावहारिक उपयोगिता अत्यन्त उच्च बनाउँछ।
अझै, क्विकसोर्ट एल्गोरिद्मलाई बुझेर, qsort लाई अधिकतम रूपमा प्रयोग गर्न सकिन्छ। विशेष डेटा सेट वा शर्तहरू अनुसार, हीपसोर्ट वा मर्जसोर्ट जस्ता अन्य एल्गोरिद्महरूसँग तुलना गरी उपयुक्त चयन गर्नु प्रदर्शनलाई अधिकतम बनाउन महत्त्वपूर्ण हुन्छ।
आगामी विकास परियोजनाहरूमा, qsort लाई उपयुक्त रूपमा प्रयोग गरी, अझ प्रभावकारी प्रोग्राम निर्माणमा चुनौती दिनुहोस्।
