• 0
مصطفى 36a2

تعرف على دالة الترتيب السريع qsort

سؤال

السلام عليكم ورحمة الله وبركاته
إنه لمن الممتع أن تكتب دوالك بنفسك .. ستتعلم الكثير وتكتسف الأخطاء وتتدرب على المفاهيم الأساسية ..
ولكن عليك ان تعتاد رغم ذلك على استخدام الدوال الجاهزة التي قام عشرات المبرمجين بتطويرها لتصل الى المستوى المطلوب  ..
وغالبا ستجدها أسرع وأفضل من أي دالة تكتبها بنفسك .. (إن كانت تحقق المطلوب )

سنتعامل اليوم مع دالة الترتيب السريع qsort وهي التي تعتبر أسرع طرق الترتيب ..
الترتيب QuickSort والذي يأخذ( n*log(n عملية في الحالة المتوسطة .. لترتيب مصفوفة من n عنصراً .. ( هذه القيمة تسمى بالتعقيد الزمني Time Complexity وهي ليست عدد العمليات تماما  )
يجدر بك الاطلاع على خوارزمية الترتيب السريع لمعرفة كيفية عملها ... ولكن هذا غير ضروري الآن ..

تحتاج إلى معرفة أولية بالمؤشرات والدوال لفهم جيد .. كما انه من المهم جدا المامك بعملية تحويل الانواع cast

لنتعرف الآن على الدالة qsort
تأخذ هذا الدالة أربع وسطاء هي بالترتيب :
1-  مؤشر من نوع void يشير الى أول عنصر في المصفوفة (أي إلى المصفوفة ) .
2- عدد صحيح يحدد عدد عناصر المصفوفة .
3- عدد صحيح يحدد حجم العنصر الواحد في المصفوفة .
4- مؤشر إلى دالة مقارنة عنصرين ... صفاتها :
          1- تعيد عدداً صحيحاً يدل على ناتج مقارنة العنصرين الممررين كوسطاء
          2- تأخذ وسيطين من نوع const void *  أي أنهما مؤشران ثابتان على العنصرين الذين ستتم مقارنتهما .

 

أهم ما عليك تحديده هو أن دالة المقارنة إذا أعادت 0 فهي تقول أن القيمتين متساويتين
أما إذا أعادت أي عدد موجب فهذا يعني أن الوسيط الأول أكبر من الثاني
وإن أعادت قيمة سالبة فالوسيط الثاني هو الأكبر


  هذا كل ما تحتاجه لمعرفة استعمال الدالة ..
 
توقيع الدالة معقد بعض الشيء ولكن يمكننا تعديله قليلا لنقرأه كما يلي :

void qsort(void * _Base,    int _NumOfElements, int _SizeOfElements,       int (* _FuncCompare)(const void *, const void *));

(قمت باستبدال بعض الاسماء مثل size_t إلى int وحذف بعض المعرفات مثل__cdecl للتسهيل )
_______________________

 

لاستعمال الدالة .. يكفي تعريف دالة المقارنة فقط لا غير ثم يمكننا استعمال الدالة فورا ..

مثال يوضح طريقة الاستعمال :

نبدأ دوما مع دالة المقارنة .. حافظ على تعريف الدالة كما هو ..

int compare(const void*a,const void*b){    int A=*((int*)a);    int B=*((int*)b);    if ( A < B )return -1;    else if(A==B)return 0;    else return 1;}

يمكننا ان نجعل الترتيب تصاعديا أو تنازليا بتغيير الشروط ..
 ويمكن جعل الدالة أعقد لتقوم بمقارنة عناصر من كائن مع عناصر كائن آخر بطريقة تحددها انت ..
ليس هناك حدود لاستخدام الدالة طالما أنك تخافظ على القيم المعادة وتعريف الدالة كما هو ..

وهذا برنامج يوضح استخدام الدالة .. بأبسط ما يمكن ..

#include<cstdio>int main(){    int a[10]={8,5,7,1,2,47,6,9,2,3};    qsort ((void *)a, 10, sizeof(int), compare);    for(int i=0;i<10;i++)        printf("%i\n",a[i]);}

لاحظ سهولة الاستخدام

كما أن وجود مؤشرات من نوع void*يعني أن الدالة عامة الاستخدام ولا تقتصر على نوع واحد من المصفوفات ..
المهم هنا هو الانتباه إلى القيام بتحويل الانواع المناسب عند تمرير الوسطاء وعند اختبار المقارنة ..


كيف يمكنك اغناء المشاركة ...
1- يمكنك كتابة برنامج يوضح ترتيب مصفوفة من struct ما .. يحوي اسماً ورقما ويقوم بالترتيب حسب الاسماء وعند تشابه الاسم يرتب حيب الرقم
2- يمكنك كتابة مثال آخر على استخدام الدالة ..
3- يمكنك تقديم روابط تشرح qsort من مصادر أخرى .. بشكل أفضل
4- يمكنك كتابة موضوع عن دوال أخرى للترتيب أو البحث مثل bsearch  مثلاً


كيف يمكنك الاساءة الى المشاركة ..
1-أن ترد بكلمة شكر فقط ..
2- أن تسأل عن أمر غير متعلق بالموضوع ..

 

أخيرا .. نسيت أن أذكر أن qsort موجودة في المكتبة cstdlib .. :)
والسلام عليكم ورحمة الله وبركاته

تم تعديل بواسطه مصطفى 36a2
3

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه

3 إجابة على هذا السؤال .

  • 0
typedef struct data_s data_s;struct data_s{	int age;	char nom[10];};int compare_par_nom(const void*a, const void*b){	char *A = (char *)a;	char *B = (char *)b;	int i;	for (i = 0; A[i] && B[i]; i++)	{		if (A[i]>B[i])			return 1;		if (A[i]<B[i])			return -1;	}	if (A[i])return 1;	if (B[i])return -1;	return 0;}int compare_par_age(const void*a, const void*b){	int A = *((int*)a);	int B = *((int*)b);	if (A < B)return -1;	else if (A == B)return 0;	else return 1;}int main(){	data_s personnes[6];	strcpy(personnes[0].nom, "Rachid");	strcpy(personnes[1].nom, "Samir");	strcpy(personnes[2].nom, "Ali");	strcpy(personnes[3].nom, "Mostafa");	strcpy(personnes[4].nom, "Khaled");	strcpy(personnes[5].nom, "Yasine");	personnes[0].age = 23;	personnes[1].age = 17;	personnes[2].age = 32;	personnes[3].age = 28;	personnes[4].age = 25;	personnes[5].age = 19;	qsort((void *)personnes, 6, sizeof(data_s), compare_par_age);	qsort((void *)&personnes[0].nom, 6, sizeof(data_s), compare_par_nom);	for (int i = 0; i<6; i++)		printf("persone num: %d nom:%s age:%d\n", i + 1, personnes[i].nom, personnes[i].age);	system("pause");}

لا أعلم لمادا لا يعمل ؟

+

 

ادا أردنا ترتيب مصفوفة من نوع بنية على حسب المتغيرات التي داخل البنية

ستحتاج qsort مؤشر لأول عنصر في البنية

ادا أردنا الترتيب على حسب أول نوع موجود في البنية سنعطي ل qsort مؤشر البنية ككل لأنه هو نفسه مؤشر أول نوع في البنية

لكن مادا لو أردنا الترتيب على حسب النوع التاني الموجود بالبنية كيف سنفعل دالك ؟؟

استعملت الكود فوق لكن لم يعمل بالشكل الجيد ؟؟

ممكن توضيح أكتر

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

السلام عليكم ورحمة الله وبركاته

كيف حالك أخي محسن ,

أولاً حتى أطمئنك , هذا الكود بعد التصحيح :

#include<cstdio>#include<cstdlib>#include<cstring>typedef struct data_s data_s;struct data_s{    int age;    char nom[10];};int compare_par_nom(const void*a, const void*b){    char *A = ((data_s *)a)->nom;    char *B = ((data_s *)b)->nom;    int i;    for (i = 0; A[i] && B[i]; i++)    {        if (A[i]>B[i])            return 1;        if (A[i]<B[i])            return -1;    }    if (A[i])return 1;    if (B[i])return -1;    return 0;}int compare_par_age(const void*a, const void*b){    int A = ((data_s*)a)->age;    int B = ((data_s*)b)->age;    if (A < B)return -1;    else if (A == B)return 0;    else return 1;}int main(){    data_s personnes[6];    strcpy(personnes[0].nom, "Rachid");    strcpy(personnes[1].nom, "Samir");    strcpy(personnes[2].nom, "Ali");    strcpy(personnes[3].nom, "Mostafa");    strcpy(personnes[4].nom, "Khaled");    strcpy(personnes[5].nom, "Yasine");    personnes[0].age = 23;    personnes[1].age = 17;    personnes[2].age = 32;    personnes[3].age = 28;    personnes[4].age = 25;    personnes[5].age = 19;    puts("Before SORTING :) :::\n");    for (int i = 0; i<6; i++)        printf("persone num: %d nom:%s age:%d\n", i + 1, personnes[i].nom, personnes[i].age);    qsort((void *)personnes, 6, sizeof(data_s), compare_par_age);    puts("\nAFTER AGE SORTING  :) :::\n");    for (int i = 0; i<6; i++)        printf("persone num: %d nom:%s age:%d\n", i + 1, personnes[i].nom, personnes[i].age);    qsort((void *)&personnes[0], 6, sizeof(data_s), compare_par_nom);    puts("\nAFTER NAME SORTING  :) :::\n");    for (int i = 0; i<6; i++)        printf("persone num: %d nom:%s age:%d\n", i + 1, personnes[i].nom, personnes[i].age);    system("pause");} 

والآن لننتقل إلى شرح بسيط , دوماً عليك تمرير مؤشر لبداية المصفوفة مهما كان نوعها , فأنت تريد ترتيب عناصر المصفوفة

data_s personnes[6];

ولكن داخل دالة الترتيب نتعامل فقط مع ما نريد الترتيب حسبه :)

مثلاً :

char *A = ((data_s *)a)->nom;    char *B = ((data_s *)b)->nom;

أو

int A = ((data_s*)a)->age;    int B = ((data_s*)b)->age;

 

والله ولي التوفيق

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

اخي محتاج مساعده في هذه الداله

الترتيب يتم بطريفة خاطئه

ماالعمل

int t,h=o no[50];

a=fopen(fopen("c:\\monam.txt","rb");

rewind(a);

if(a==0)

{

printf("error");

getch();

exit(1);

}

fscanf(a,"%d%s%d%d%d",&st.nu,&st.name,&st.arbic,&st.english,&st.c);

while(!feof(a)

{

st.nu==no[h];

h++

fscanf(a,"%d%s%d%d%d",&st.nu,&st.name,&st.arbic,&st.english,&st.c);

}

fclose(a);

for(int i=0;i<h;i++)

for(int j=0;j<h;j++)

if(no[j]>no[j+1])

int temp=no[j];

no[j]=no[j+1];

no[j+1]=temp;

}

for(int r=0;r<h;r++)

{

printf("\n%d",no[r]);

}

printf("\n \t to pack press 0");

scanf("%d",&t);

if(t==0)

getch();

goto w;

}

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه

من فضلك سجل دخول لتتمكن من التعليق

ستتمكن من اضافه تعليقات بعد التسجيل



سجل دخولك الان

  • يستعرض القسم حالياً   0 members

    لا يوجد أعضاء مسجلين يشاهدون هذه الصفحة .