الخوارزمية عبارة عن مجموعة من القواعد المحددة جيدًا المستخدمة لحل مشكلة ما في عدد محدود من الخطوات. بكل بساطة، إنها عملية حل المشكلات بواسطة الكمبيوتر. في هذه العملية، سواء كنت تقوم بتكوين فكرة لحل مشكلة أو كتابة برنامج، فإنك تقوم بتنفيذ خوارزمية معينة. الأول عبارة عن خوارزمية يتم تنفيذها عن طريق التفكير، والأخيرة عبارة عن خوارزمية يتم تنفيذها عن طريق العملية.
يجب أن تتمتع الخوارزمية بالخصائص الخمس المهمة التالية:
1. النهاية: يجب أن تتأكد الخوارزمية من أنها تنتهي بعد تنفيذ عدد محدود من الخطوات؛
2. الدقة: يجب أن تكون كل خطوة من خطوات الخوارزمية محددة بوضوح؛
3. الإدخال: تحتوي الخوارزمية على 0 مدخلات أو أكثر لوصف الوضع الأولي للمعامل؛
4. المخرجات: تحتوي الخوارزمية على مخرج واحد أو أكثر لتعكس نتائج معالجة البيانات المدخلة. الخوارزمية بدون مخرجات لا معنى لها؛
5. الجدوى: من حيث المبدأ، يمكن تشغيل الخوارزمية بدقة، ويمكن إكمالها بواسطة أشخاص يستخدمون القلم والورقة لإجراء عدد محدود من العمليات.
فرز الدمج (MERGE SORT) هو نوع آخر من طرق الفرز المختلفة. معنى الدمج هو دمج تسلسلين أو أكثر من البيانات المرتبة في تسلسل بيانات مرتبة جديد، لذلك يطلق عليه أيضًا خوارزمية الدمج. فكرتها الأساسية هي افتراض أن المصفوفة A تحتوي على N من العناصر، ثم يمكن اعتبار المصفوفة A مكونة من N تسلسلات فرعية مرتبة، ويبلغ طول كل تسلسل فرعي 1، ثم يتم دمج اثنين في اثنين للحصول على N/2 تسلسل فرعي مرتب من يتم بعد ذلك دمج الطول 2 أو 1 اثنين في اثنين، ويتكرر هذا حتى يتم الحصول على تسلسل بيانات مرتب بطول N وتسمى طريقة الفرز هذه بالفرز المدمج ثنائي الاتجاه.
على سبيل المثال، يحتوي المصفوفة A على 7 بيانات، وهي: 49 38 65 97 76 13 27. ثم تظهر عملية استخدام خوارزمية الفرز المدمج في الشكل 7:
القيمة الأولية[49] [38] [65] [97] [76] [13] [27]
ينظر إليها على أنها تتكون من 7 متتابعات طولها 1. بعد الدمج الأول [38 49] [65 97] [13 76] [27]
ينظر إليها على أنها تتكون من 4 متتابعات بطول 1 أو 2. بعد الدمج الثاني [38 49 65 97] [13 27 76]
يُنظر إليه على أنه يتكون من تسلسلين فرعيين بطول 4 أو 3. بعد الدمج الثالث [13 27 38 49 65 76 97]
الشكل 6: مخطط عملية خوارزمية فرز الدمج تتمثل العملية الأساسية لخوارزمية الدمج في دمج تسلسلين مرتبين متجاورين في صفيف أحادي البعد في تسلسل واحد مرتب. يمكن أيضًا تنفيذ خوارزمية الدمج باستخدام خوارزمية متكررة، وهي بسيطة نسبيًا في الشكل، ولكنها ذات تطبيق عملي ضعيف.
يعد عدد عمليات الدمج في خوارزمية الدمج كمية مهمة جدًا وفقًا للحسابات، عندما يكون هناك 3 إلى 4 عناصر في المصفوفة، يكون عدد عمليات الدمج 2، وعندما يكون هناك 5 إلى 8 عناصر، يكون عدد عمليات الدمج 3. ، وعندما يكون هناك 9 إلى عندما يكون هناك 16 عنصرًا، يكون عدد عمليات الدمج 4. ووفقًا لهذه القاعدة، عندما يكون هناك N تسلسلات فرعية، يمكن استنتاج أن عدد عمليات الدمج هو
X (2>=N، أصغر X يستوفي الشرط الفرعي).
وصف خوارزمية الفقاعة:
قبل شرح خوارزمية فرز الفقاعات، دعنا نقدم أولاً خوارزمية تضع الرقم الأكبر بين 10 أرقام (في المصفوفة A) في الموضع الأخير. يتم وصف الخوارزمية على النحو التالي:
(1) من المصفوفة A[1] إلى A[10]، قارن بين رقمين متجاورين في أزواج. أي أن A[1] يقارن بـ A[2]، وبعد المقارنة يقارن A[2] بـ A[3]،... وأخيرًا يقارن A[9] بـ A[10].
(2) خلال كل مقارنة، إذا كان الرقم السابق أكبر من الرقم الأخير، فسيتم تبديل الرقمين، أي سيتم نقل الرقم الأكبر إلى الخلف ونقل الرقم الأصغر إلى الأمام. على سبيل المثال، في المقارنة الأولى، إذا كانت A[1] أكبر من A[2]، يتم تبادل قيم A[1] وA[2]. يستخدم الشكل أدناه 6 بيانات لتوضيح الخوارزمية المذكورة أعلاه.
افترض أن البيانات الستة هي: A[]=5 7 4 3 8 6
أ[1] أ[2] أ[3] أ[4] أ[5] أ[6]
5 7 4 3 8 6 في المرة الأولى، تتم مقارنة A[1]=5 وA[2]=7، 7>5، ولم يتم إجراء أي مبادلة.
5 7 4 3 8 6 في المرة الثانية، تتم مقارنة A[2]=7 وA[3]=4، وتبديل 4<7.
ثم البيانات بعد المقارنة الثانية هي 5 4 7 3 8 6
5 4 7 3 8 6 في المرة الثالثة، تتم مقارنة A[3]=7 وA[4]=3، وتبديل 3<7.
ثم البيانات بعد المقارنة الثالثة هي 5 4 3 7 8 6
5 4 3 7 8 6 في المرة الرابعة، تتم مقارنة A[4]=7 وA[5]=8، 8>7، ولم يتم إجراء أي مبادلة.
5 4 3 7 8 6 في المرة الخامسة، تتم مقارنة A[6]=6 وA[5]=8، وتبديل 6<8.
ثم النتيجة الخامسة والأخيرة هي
5 4 3 7 6 8
****************************************************************************************************************************************************************************** * *****
وصف خوارزمية فرز التحديد:
قبل تقديم طريقة الفرز بالاختيار، دعنا نقدم خوارزمية تضع الرقم الأصغر في الموضع الأول. بالطبع، يمكنك أيضًا استخدام طريقة الفرز الفقاعية المذكورة أعلاه. الآن نستخدم خوارزمية جديدة: أيديولوجيتها التوجيهية ليست هناك عجلة من أمرها قم بتغيير المواضع أولاً، تحقق من كل رقم بدءًا من A[1]. لمعرفة الرقم الأصغر، اكتب الموضع P للرقم، بعد اكتمال المسح، قم بتبديل A[P] وA[1]. ، ثم يتم نقل أصغر البيانات في A[1] إلى A[10] إلى الموضع الأمامي. خطوات الخوارزمية هي كما يلي:
1) أولاً، افترض أن الرقم الموجود في A[1] هو الأصغر، ولاحظ الموضع P=1 في هذا الوقت؛
2) قارن A[P] وA[I] بالتسلسل (أتغير من 2 إلى 10 خلال كل مقارنة، إذا كان الرقم في A[I] أصغر من الرقم الموجود في A[P]، فأنا القيمة). يتم تعيينه إلى P، بحيث يشير P دائمًا إلى موضع أصغر رقم تم مسحه ضوئيًا حاليًا، أي أن A[P] يساوي دائمًا أصغر عدد من جميع الأرقام الممسوحة ضوئيًا. بعد المقارنة واحدًا تلو الآخر، يشير P إلى موضع أصغر رقم بين الأرقام العشرة، أي أن A[P] هو أصغر رقم بين الأرقام العشرة؛
3) اعكس أرقام A[P] و A[1] فيكون العدد الأصغر في A[1] أي في المقدمة.
إذا قمت الآن بتكرار هذه الخوارزمية، ولكن في كل مرة يتم تكرارها، فسيتم نقل نطاق السلسلة التي تتم مقارنتها إلى الخلف بمقدار موضع واحد. أي أنه في المقارنة الثانية، يكون النطاق من الرقم الثاني إلى الرقم N. ابحث عن الموضع P لأصغر رقم ضمن هذا النطاق، ثم قم بتبديل A[P] و A[2]، بحيث يكون من الرقم الثاني. أصغر رقم من البداية إلى الرقم ن هو في A[2]. المرة الثالثة هي العثور على أصغر رقم من الرقم الثالث إلى الرقم ن، ثم ضع A[P] و A[ 3] مبادلة.. بعد تكرار هذه العملية N-1 مرات، يتم ترتيب الأرقام N في المصفوفة A بالترتيب من الصغير إلى الكبير. طريقة الفرز هذه هي الفرز بالاختيار.
****************************************************************************************************************************************************************************** * ***************
وصف خوارزمية فرز الإدراج:
من خلال تعلم الطريقتين المذكورتين أعلاه، يمكنك فهم الفكرة الأساسية للفرز، ويمكنك أيضًا ترتيب أي مصفوفة غير مرتبة من الأكبر إلى الأصغر (ترتيب تنازلي) أو من الصغير إلى الكبير (ترتيب تصاعدي). لنفترض الآن أن هناك تسلسل بيانات تم ترتيبه بالفعل، ومن الضروري إدراج رقم في تسلسل البيانات المرتب بالفعل، ولكن من الضروري أن يظل تسلسل البيانات مرتبًا بعد الإدراج، وفي هذا الوقت، سيتم استخدام طريقة فرز جديدة يمكن استخدامها - طريقة فرز الإدراج، العملية الأساسية لفرز الإدراج هي إدراج البيانات في البيانات المرتبة التي تم فرزها، وذلك للحصول على بيانات مرتبة جديدة برقم زائد واحد.
سؤال: هناك N قطعة من البيانات في المصفوفة A، مرتبة بالترتيب من الصغير إلى الكبير. أدخل رقم X، وأدخل قيمة X في المصفوفة A، بحيث تظل المصفوفة المدرجة A مرتبة من الصغير إلى الكبير. .
ثم الخوارزمية لحل هذه المشكلة هي:
1) ابحث عن الموضع الذي يجب إدخال X فيه من خلال مقارنة الحجم، إذا كان يجب وضعه في الموضع I؛
2) انقل جميع عناصر المصفوفة بدءًا من I (بما في ذلك I) موضعًا واحدًا للخلف، أي A[I+1]:=A[I];
يعد الفرز السريع تحسينًا لفرز الفقاعات. فكرته الأساسية هي تقسيم البيانات المراد فرزها إلى جزأين مستقلين من خلال الفرز أحادي الاتجاه، وتكون جميع البيانات في جزء واحد أصغر من جميع البيانات الموجودة في الجزء الآخر، ومن ثم يتم فرز جزأين البيانات بشكل تسلسلي. للفرز السريع، يمكن إجراء عملية الفرز بأكملها بشكل متكرر، بحيث تصبح البيانات بأكملها تسلسلًا مرتبًا.
افترض أن المصفوفة المراد فرزها هي A[1]...A[N]. أولاً، حدد البيانات بشكل عشوائي (عادةً البيانات الأولى) باعتبارها البيانات الرئيسية، ثم ضع جميع الأرقام الأكبر منها أمامها، وكل الأرقام الأكبر منها توضع خلفها أرقام كبيرة وتسمى هذه العملية بالفرز السريع. خوارزمية الفرز السريع هي:
1) قم بتعيين متغيرين I وJ. عند بدء الفرز، I:=1, J:=N;
2) استخدم عنصر الصفيف الأول كبيانات رئيسية وقم بتعيينه إلى X، أي X:=A[1]؛
3) ابحث للأمام من J، أي ابحث للأمام من الخلف (J:=J-1)، وابحث عن القيمة الأولى الأقل من X، واستبدل الاثنين؛
4) البحث للخلف من I، أي البحث من الأمام إلى الخلف (I:=I+1)، والعثور على القيمة الأولى الأكبر من X، وتبادل الاثنين؛
5) كرر الخطوتين 3 و4 حتى I=J؛
على سبيل المثال: قيم المصفوفة A المراد فرزها هي: (بيانات المفتاح الأولية X:=49)
أ[1] أ[2] أ[3] أ[4] أ[5] أ[6] أ[7]:
49 38 65 97 76 13 27
بعد التبادل الأول: 27 38 65 97 76 13 49
(بعد البحث من الخلف حسب الخطوة الثالثة من خوارزمية التبادل الثاني: 27 38 49 97 76 13 65
(اتبع الخطوة الرابعة من الخوارزمية وابدأ من الأمام للعثور على القيمة >
بعد التبادل الثالث: 27 38 13 97 76 49 65
(حسب الخطوة الخامسة من الخوارزمية سيتم تنفيذ الخطوة الثالثة من الخوارزمية مرة أخرى من النهاية للعثور على التبادل الرابع: 27 38 13 49 76 97 65
(اتبع الخطوة الرابعة من الخوارزمية وابدأ من الأمام للعثور على قيمة أكبر من X، 97>49، استبدل الاثنين، في هذا الوقت J:=4)
في هذا الوقت، عند تنفيذ الخطوة الثالثة، وجد أن I=J، وبذلك تنتهي عملية الفرز السريع، وتكون النتيجة بعد الفرز السريع: 27 38 13 49 76 97 65، أي أن جميع الأرقام الأكبر من 49 موجودة في 49. ، إذن الأعداد الأقل من 49 كلها أمام 49.
الفرز السريع هو استدعاء هذه العملية بشكل متكرر - قم بتقسيم تسلسل البيانات إلى 49 كنقطة وسط، وإجراء فرز سريع مماثل على الجزء الأمامي والجزء الخلفي على التوالي، وبالتالي إكمال الفرز السريع لتسلسل البيانات بالكامل، وأخيرًا قم بتشغيل تسلسل البيانات في تسلسل مرتب وفقًا لهذه الفكرة، تظهر عملية الفرز السريع للمصفوفة أعلاه A في الشكل 6:
الحالة الأولية {49 38 65 97 76 13 27}
وبعد الفرز السريع يتم تقسيمها إلى {27 38 13} 49 {76 97 65}
فرز الأجزاء الأمامية والخلفية بسرعة على التوالي {13} 27 {38}
النهاية النهاية {49 65} 76 {97} 49 {65} النهاية النهاية
****************************************************************************************************************************************************************************** *************************
الشكل 6: وصف الخوارزمية للفرز السريع خلال عملية الفرز السريع
1). لنفترض أن الأرقام N (بافتراض أن N = 10) مخزنة في المصفوفة S؛
2)، في ق[1. . خذ أي عنصر في N] كأساس للمقارنة، على سبيل المثال، خذ T=S[1] والغرض الأولي هو تحديد الموضع K حيث يجب أن يكون T في نتيجة الفرز. . . K-1]<=S[K]<=S[K+1..N]، أي أن الأرقام قبل S[K] كلها أصغر من S[K]، والأرقام بعد S[K] هي كلها أكبر من S[K]؛
3) استخدام فكرة فرق تسد (أي استراتيجية جعل الكبير والصغير صغيرًا) يمكن أن يزيد من تحسين S[1. . K-1] وS[K+1. . N] يتم بعد ذلك فرز مجموعتي البيانات بسرعة حتى تكون هناك بيانات واحدة فقط في كائن التجميع.
إذا كانت البيانات المحددة كما يلي، فإن أول عملية فرز سريعة هي:
مصفوفة منخفضة: 1 2 3 4 5 6 7 8 9 10
45 36 18 53 72 30 48 93 15 36
أنا
(1) 36 36 18 53 72 30 48 93 15 45
(2) 36 36 18 45 72 30 48 93 15 53
(3) 36 36 18 15 72 30 48 93 45 53
(4) 36 36 18 15 45 30 48 93 72 53
(5) 36 36 18 15 30 45 48 93 72 53