استفسار حول بعض خوارزميات الفرز بلغة C++

عبدالله العتيبي12 · 29 أكتوبر 2022

السلام عليكم ورحمة الله وبركاته ،، أسعد الله صباحكم بالرضا والنعيم ، يوجد لدي برنامج في لغة C++ حاولت بأن اصل لحل ولو كان بنسبة 90% ولكن كل محاولاتي أشعر بأنها غير صحيحة ودقيقة وتوجد محاولة بها حل الكود ولكن أغلبها خاطئة ، وقمت بأخذ صور من لقطات الشاشة من الكود والنتائج ، وأرجوا منكم مساعدتي لحل هذا البرنامج والمطلوب من البرنامج هو . . .

اكتب برنامج بلغة ++C يقوم بعملية الفرز بثلاث طرق مختلفة و هي الفقاعي و الاختيار و الاقحام باستخدام دالة لكل طريقة و بحيث يتم اختيار طريقة الفرز لمصفوفة تحتوي على رقم 5555 و يتم عرض خطوات الفرز على الشاشة ويوضح الفرق بين عمليات الفرز السابقة

وهذه بعض من محاولات حل هذا البرنامج : ..

#include <iostream>

using namespace std;

int main()

{

    int i, temp, j;

    int x[] = { 88, 1, 6, 1, 2 };

    cout << sizeof(x)<<endl;

    for (i = 1; i < 5; i++)

    {

        temp = x[i];

        cout << "\t temp = " << temp;

            cout << "\n";

        for (j = i; j>0 && x[j - 1]>temp; j--)

        {

            cout << "\t j-1 x[" << j - 1 << "] = " << x[j - 1];

            cout << "\t temp = " << temp;

            cout << "\t j x[" << j << "] = " << x[j]<<endl;

            x[j] = x[j - 1];

        } 

        cout << "\n ---------------------------- "<< endl ;

        x[j] = temp;

        cout << "\t temp = " << temp;

            cout << "\t j x[" << j << "] = " << x[j]<<endl;

    }   // to print 

    cout << "\n order numbers= " << endl;

    for (i = 0; i <= 4; i++)

        cout << x[i] << "\t";

    cout << "\ndone. " << endl;

}



#include <iostream>

#include <string>

using namespace std;

int main()

{

    int i, j,temp ;

    int x[5];

    //= { 88, 1, 6, 1, 2,55,16,22,15,16 };

    for (int t = 0; t <= 5; t++)

                cin>>x[t];// << "\t";

                

    

    int size =sizeof(x);

    size=size/4;

    //cout<<size/4<<endl;

    for (i = 0; i <(size-1); i++)

    {

        for (j = 0; j<(size - i - 1); j++)

        {

            for (int t = 0; t <= (size-1); t++)

                cout << x[t] << "\t";

                cout<<endl;

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

            {

                temp = x[j];

                x[j] = x[j + 1];

                x[j + 1] = temp;

            

                for (int t = 0; t <= size-1; t++)

                cout << x[t] << "\t";

                cout<<"\n---------------------------"<<endl;

                

            }

        }

    } // to print 

    cout << "\n order numbers= " << endl;

    for (i = 0; i <= size-1; i++)

        cout << x[i] << "\t";

    cout << "\ndone. " << endl;

}

/*

#include <iostream>

#include <string>

using namespace std;

void main()

{

int n, i, arr[50], j, temp;

cout << "Enter total number of elements :";

cin >> n;

for (i = 0; i<n; i++)

{

cout << "Enter " << i << " numbers :";

cin >> arr[i];

}

cout << "Sorting array using bubble sort technique...\n";

for (i = 0; i<(n - 1); i++)

{

for (j = 0; j<(n - i - 1); j++)

{

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

{

temp = arr[j];

arr[j] = arr[j + 1];

arr[j + 1] = temp;

}

}

}

cout << "Elements sorted successfully..!!\n";

cout << "Sorted list in ascending order :\n";

for (i = 0; i<n; i++)

{

cout << arr[i] << " ";

}

}*/

Ahmed Sadek Elamine Touahria · 29 أكتوبر 2022

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

// C++ program for implementation
// of Bubble sort
#include <bits/stdc++.h>
using namespace std;

// وظيفة لتنفيذ فرز الفقاعة
void bubbleSort(int arr[], int n)
{
	int i, j;
	for (i = 0; i < n - 1; i++)
		for (j = 0; j < n - i - 1; j++)
			if (arr[j] > arr[j + 1])
				swap(arr[j], arr[j + 1]);
}

// وظيفة لطباعة مجموعة
void printArray(int arr[], int size)
{
	int i;
	for (i = 0; i < size; i++)
		cout << arr[i] << " ";
	cout << endl;
}

// -------   main --------------
int main()
{
	int arr[] = { 5, 1, 4, 2, 8};
	int N = sizeof(arr) / sizeof(arr[0]);
	bubbleSort(arr, N);
	cout << "الفرز : \n";
	printArray(arr, N);
	return 0;
}

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

#include <bits/stdc++.h>
using namespace std;

// وظيفة المبادلة
void swap(int *xp, int *yp)
{
	int temp = *xp;
	*xp = *yp;
	*yp = temp;
}

void selectionSort(int arr[], int n)
{
	int i, j, min_idx;

// حد الانتقال واحدًا تلو الآخر لـ
// لم يتم فرزها subarray
	for (i = 0; i < n-1; i++)
	{
	
// ابحث عن الحد الأدنى للعنصر في
// مجموعة غير مرتبة
		min_idx = i;
		for (j = i+1; j < n; j++)
		if (arr[j] < arr[min_idx])
			min_idx = j;

// قم بتبديل الحد الأدنى الموجود للعنصر
// مع العنصر الأول
		if(min_idx!=i)
			swap(&arr[min_idx], &arr[i]);
	}
}

void printArray(int arr[], int size)
{
	int i;
	for (i=0; i < size; i++)
		cout << arr[i] << " ";
	cout << endl;
}

// برنامج التشغيل لاختبار الوظائف المذكورة أعلاه
int main()
{
	int arr[] = {64, 25, 12, 22, 11};
	int n = sizeof(arr)/sizeof(arr[0]);
	selectionSort(arr, n);
	cout << "العناصر المفروزة: \n";
	printArray(arr, n);
	return 0;
}

Kais Hasan · 29 أكتوبر 2022

سأقوم بشرح الآلية العامة لكل خوارزمية و سيصبح من السهل عليك كتابتها بعد ذلك، و في حال واجهت مشاكل بعدها يمكنك السؤال مجدداً.

في الشروحات التالية سأفرض أن الترتيب تصاعدي و ذلك لتجنب ذكر الحالتين في كل مرة، حيث أن نفس الآلية يمكن تطبيقها في التنازلي طبعاً.

بالإضافة أنني سأعتبر عدد العناصر n.

الفرز الفقاعي

في هذا النوع من الفرز نعتمد على عملية التبديل، حيث نقوم بالمرور على العناصر و مقارنة كل عنصر بالعنصر الذي يليه و في حال كان العنصر الحالي أكبر من الذي يليه نقوم بالتبديل بينهما.

الآن أهم فكرة في هذه الخوارزمية هو تحديد كم مرة نحتاج لتكرار العملية السابقة، إذا فكرنا في الأمر قليلاً، في أول تكرار يمكننا ضمان أن أكبر عنصر سيصل إلى النهاية، و ذلك ﻷنه دائماً سيكون أكبر من الذي يليه، و بالتالي في كل تكرار نحن متأكدون أن عنصر واحد على الأقل سيصل إلى وجهته.

بعد وصولنا إلى الاستنتاج السابق قد يخطر ببالنا أننا نحتاج إلى n تكرار و لكن ليس تماماً، حيث أنه في حال وضعنا n-1 عنصر في مكانه الصحيح فتلقائياً سيكون العنصر المتبقي في مكانه الصحيح، و بالتالي نحتاج n-1 تكرار لا أكثر.

الفرز بالاختيار

في هذا الفرز يتم في كل مرة البحث عن أصغر عنصر متبقي و وضعه في مكانه الصحيح مباشرة.

كيف يمكن ذلك؟ ببساطة في كل مرة نبحث عن أصغر عنصر متبقي و نضعه في المكان الذي يوافق رقم التكرار، أي في حال كنا في التكرار الأول نبحث في كافة العناصر و عندما نجد العنصر، نقوم بالتبديل بينه و بين العنصر الموجود في الموقع الأول.

في التكرار الثاني نقوم بالبحث بدءاً من العنصر الثاني و عندما نجد أصغر عنصر نقوم بالتبديل بينه و بين العنصر الثاني و هكذا من أجل جميع التكرارات.

الفرز بالإقحام

في هذا النوع من الفرز نقوم بتنفيذ عملية معينة من أجل عنصر و لمرة واحدة و هي القيام بإيجاد موقع العنصر بالنسبة لمجموعة العناصر حتى الآن.

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

//لنفرض لدي المصفوفة التالية
a = [4, 3, 5, 1]
//أول عنصر دائماً يبقى في مكانه
//الآن من أجل العنصر الثاني نريد وضعه في مكانه
//نقوم بالمقارنة بينه و بين الذي يسبقه فنرى أنه أصغر فنقوم بالتبديل
a = [3, 4, 5, 1]
//الآن لا يوجد عناصر تسبقه فنتوقف
//لاحظ هنا نحن في كل خطوة نضمن أن المصفوفة التي تسبقني مرتبة
//و هذا ما يسمح بالقيام بعملية البحث عن الموقع الصحيح عبر التبديل
//الآن من أجل الرقم 5 نرى أنه ليس أصغر من الذي يسبقه فنتركه مكانه
//ننتقل إلى الرقم الأخير، نرى أنه أصغر من 5 فنبدل
a = [3, 4, 1, 5]
//أيضاً هو أصغر من فنبدل
a = [3, 1, 4, 5]
//كما أنه أصغر من 3 فنبدل
a = [1, 3, 4, 5]
//لا يوجد عناصر متبقية فنتوقف

عبدالله العتيبي12 · 29 أكتوبر 2022

بتاريخ 14 ساعات قال Kais Hasan:
سأقوم بشرح الآلية العامة لكل خوارزمية و سيصبح من السهل عليك كتابتها بعد ذلك، و في حال واجهت مشاكل بعدها يمكنك السؤال مجدداً.

في الشروحات التالية سأفرض أن الترتيب تصاعدي و ذلك لتجنب ذكر الحالتين في كل مرة، حيث أن نفس الآلية يمكن تطبيقها في التنازلي طبعاً.

بالإضافة أنني سأعتبر عدد العناصر n.

الفرز الفقاعي

في هذا النوع من الفرز نعتمد على عملية التبديل، حيث نقوم بالمرور على العناصر و مقارنة كل عنصر بالعنصر الذي يليه و في حال كان العنصر الحالي أكبر من الذي يليه نقوم بالتبديل بينهما.

الآن أهم فكرة في هذه الخوارزمية هو تحديد كم مرة نحتاج لتكرار العملية السابقة، إذا فكرنا في الأمر قليلاً، في أول تكرار يمكننا ضمان أن أكبر عنصر سيصل إلى النهاية، و ذلك ﻷنه دائماً سيكون أكبر من الذي يليه، و بالتالي في كل تكرار نحن متأكدون أن عنصر واحد على الأقل سيصل إلى وجهته.

بعد وصولنا إلى الاستنتاج السابق قد يخطر ببالنا أننا نحتاج إلى n تكرار و لكن ليس تماماً، حيث أنه في حال وضعنا n-1 عنصر في مكانه الصحيح فتلقائياً سيكون العنصر المتبقي في مكانه الصحيح، و بالتالي نحتاج n-1 تكرار لا أكثر.

الفرز بالاختيار

في هذا الفرز يتم في كل مرة البحث عن أصغر عنصر متبقي و وضعه في مكانه الصحيح مباشرة.

كيف يمكن ذلك؟ ببساطة في كل مرة نبحث عن أصغر عنصر متبقي و نضعه في المكان الذي يوافق رقم التكرار، أي في حال كنا في التكرار الأول نبحث في كافة العناصر و عندما نجد العنصر، نقوم بالتبديل بينه و بين العنصر الموجود في الموقع الأول.

في التكرار الثاني نقوم بالبحث بدءاً من العنصر الثاني و عندما نجد أصغر عنصر نقوم بالتبديل بينه و بين العنصر الثاني و هكذا من أجل جميع التكرارات.

الفرز بالإقحام

في هذا النوع من الفرز نقوم بتنفيذ عملية معينة من أجل عنصر و لمرة واحدة و هي القيام بإيجاد موقع العنصر بالنسبة لمجموعة العناصر حتى الآن.

لشرح الفكرة السابقة بشكل تفصيلي، تخيل أن لديك مصفوفة ما، في البداية يكون لديك أول عنصر و بالتالي يمكنك تركه مكانه لأنه لا يوجد غيره، الآن بفرض أننا أصبحنا في العنصر i فإننا نعلم أن كافة العناصر التي تسبقنا مرتبة و بالتالي ببساطة يمكننا الرجوع و التبديل دائماً حتى الوصول إلى الموقع الصحيح، سأعطيك مثال على ذلك كون هذه الخوارزمية فكرتها أصعب بقليل.
//لنفرض لدي المصفوفة التالية
a = [4, 3, 5, 1]
//أول عنصر دائماً يبقى في مكانه
//الآن من أجل العنصر الثاني نريد وضعه في مكانه
//نقوم بالمقارنة بينه و بين الذي يسبقه فنرى أنه أصغر فنقوم بالتبديل
a = [3, 4, 5, 1]
//الآن لا يوجد عناصر تسبقه فنتوقف
//لاحظ هنا نحن في كل خطوة نضمن أن المصفوفة التي تسبقني مرتبة
//و هذا ما يسمح بالقيام بعملية البحث عن الموقع الصحيح عبر التبديل
//الآن من أجل الرقم 5 نرى أنه ليس أصغر من الذي يسبقه فنتركه مكانه
//ننتقل إلى الرقم الأخير، نرى أنه أصغر من 5 فنبدل
a = [3, 4, 1, 5]
//أيضاً هو أصغر من فنبدل
a = [3, 1, 4, 5]
//كما أنه أصغر من 3 فنبدل
a = [1, 3, 4, 5]
//لا يوجد عناصر متبقية فنتوقف

شكرا لكم

بتاريخ 14 ساعات قال Ahmed Sadek:

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


// C++ program for implementation
// of Bubble sort
#include <bits/stdc++.h>
using namespace std;

// وظيفة لتنفيذ فرز الفقاعة
void bubbleSort(int arr[], int n)
{
	int i, j;
	for (i = 0; i < n - 1; i++)
		for (j = 0; j < n - i - 1; j++)
			if (arr[j] > arr[j + 1])
				swap(arr[j], arr[j + 1]);
}

// وظيفة لطباعة مجموعة
void printArray(int arr[], int size)
{
	int i;
	for (i = 0; i < size; i++)
		cout << arr[i] << " ";
	cout << endl;
}

// -------   main --------------
int main()
{
	int arr[] = { 5, 1, 4, 2, 8};
	int N = sizeof(arr) / sizeof(arr[0]);
	bubbleSort(arr, N);
	cout << "الفرز : \n";
	printArray(arr, N);
	return 0;
}

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


#include <bits/stdc++.h>
using namespace std;

// وظيفة المبادلة
void swap(int *xp, int *yp)
{
	int temp = *xp;
	*xp = *yp;
	*yp = temp;
}

void selectionSort(int arr[], int n)
{
	int i, j, min_idx;

// حد الانتقال واحدًا تلو الآخر لـ
// لم يتم فرزها subarray
	for (i = 0; i < n-1; i++)
	{
	
// ابحث عن الحد الأدنى للعنصر في
// مجموعة غير مرتبة
		min_idx = i;
		for (j = i+1; j < n; j++)
		if (arr[j] < arr[min_idx])
			min_idx = j;

// قم بتبديل الحد الأدنى الموجود للعنصر
// مع العنصر الأول
		if(min_idx!=i)
			swap(&arr[min_idx], &arr[i]);
	}
}

void printArray(int arr[], int size)
{
	int i;
	for (i=0; i < size; i++)
		cout << arr[i] << " ";
	cout << endl;
}

// برنامج التشغيل لاختبار الوظائف المذكورة أعلاه
int main()
{
	int arr[] = {64, 25, 12, 22, 11};
	int n = sizeof(arr)/sizeof(arr[0]);
	selectionSort(arr, n);
	cout << "العناصر المفروزة: \n";
	printArray(arr, n);
	return 0;
}

بتاريخ 14 ساعات قال Ahmed Sadek:

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


// C++ program for implementation
// of Bubble sort
#include <bits/stdc++.h>
using namespace std;

// وظيفة لتنفيذ فرز الفقاعة
void bubbleSort(int arr[], int n)
{
	int i, j;
	for (i = 0; i < n - 1; i++)
		for (j = 0; j < n - i - 1; j++)
			if (arr[j] > arr[j + 1])
				swap(arr[j], arr[j + 1]);
}

// وظيفة لطباعة مجموعة
void printArray(int arr[], int size)
{
	int i;
	for (i = 0; i < size; i++)
		cout << arr[i] << " ";
	cout << endl;
}

// -------   main --------------
int main()
{
	int arr[] = { 5, 1, 4, 2, 8};
	int N = sizeof(arr) / sizeof(arr[0]);
	bubbleSort(arr, N);
	cout << "الفرز : \n";
	printArray(arr, N);
	return 0;
}

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


#include <bits/stdc++.h>
using namespace std;

// وظيفة المبادلة
void swap(int *xp, int *yp)
{
	int temp = *xp;
	*xp = *yp;
	*yp = temp;
}

void selectionSort(int arr[], int n)
{
	int i, j, min_idx;

// حد الانتقال واحدًا تلو الآخر لـ
// لم يتم فرزها subarray
	for (i = 0; i < n-1; i++)
	{
	
// ابحث عن الحد الأدنى للعنصر في
// مجموعة غير مرتبة
		min_idx = i;
		for (j = i+1; j < n; j++)
		if (arr[j] < arr[min_idx])
			min_idx = j;

// قم بتبديل الحد الأدنى الموجود للعنصر
// مع العنصر الأول
		if(min_idx!=i)
			swap(&arr[min_idx], &arr[i]);
	}
}

void printArray(int arr[], int size)
{
	int i;
	for (i=0; i < size; i++)
		cout << arr[i] << " ";
	cout << endl;
}

// برنامج التشغيل لاختبار الوظائف المذكورة أعلاه
int main()
{
	int arr[] = {64, 25, 12, 22, 11};
	int n = sizeof(arr)/sizeof(arr[0]);
	selectionSort(arr, n);
	cout << "العناصر المفروزة: \n";
	printArray(arr, n);
	return 0;
}

شكرا لكم 🌹🙏

استفسار حول بعض خوارزميات الفرز بلغة C++

السؤال

عبدالله العتيبي12

3 أجوبة على هذا السؤال

Recommended Posts

Ahmed Sadek Elamine Touahria

Kais Hasan

الفرز الفقاعي

الفرز بالاختيار

الفرز بالإقحام

عبدالله العتيبي12

الفرز الفقاعي

الفرز بالاختيار

الفرز بالإقحام

انضم إلى النقاش

إعلانات

تابعنا على

الرئيسية

تابعنا

دروس ومقالات

أسئلة وأجوبة

كتب

دورات

بطاقات هدية