خوارزمية الفرز

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

بصورة رسمية، يجب أن تستوفي مخرجات أي خوارزمية فرز شرطين:

1. يكون الناتج بترتيب رتيب (كل عنصر ليس أصغر/أكبر من العنصر السابق، وفقًا للترتيب المطلوب).
2. الناتج هو تبديل (إعادة ترتيب مع الاحتفاظ بجميع العناصر الأصلية) للمدخلات.

على الرغم من أن بعض الخوارزميات مصممة للوصول التسلسلي ، إلا أن الخوارزميات ذات الأداء الأعلى تفترض أن البيانات مخزنة في بنية بيانات تسمح بالوصول العشوائي .

منذ بدايات الحوسبة، حظيت مسألة الفرز باهتمام بحثي واسع، ربما لصعوبة حلها بكفاءة رغم بساطتها ووضوحها. من بين مؤلفي خوارزميات الفرز الأولى حوالي عام 1951، كانت بيتي هولبرتون ، التي عملت على حاسوبي ENIAC و UNIVAC . ^{[ 1 ] [ 2 ]} وتم تحليل فرز الفقاعات في وقت مبكر من عام 1956. ^{[ 3 ]} وقد عُرفت الخوارزميات المثلى تقاربياً منذ منتصف القرن العشرين ، ولا تزال تُبتكر خوارزميات جديدة، حيث يعود تاريخ خوارزمية Timsort واسعة الانتشار إلى عام 2002، ونُشرت خوارزمية فرز المكتبة لأول مرة عام 2006. 

تتطلب خوارزميات فرز المقارنة شرطًا أساسيًا هو${\displaystyle n\log {n}-1.4427n+O(\log {n})}$المقارنات. يمكن أن يكون للخوارزميات التي لا تعتمد على المقارنات، مثل فرز العد ، أداء أفضل.

تنتشر خوارزميات الفرز في فصول علوم الحاسوب التمهيدية ، حيث يوفر وفرة الخوارزميات للمشكلة مقدمة سلسة لمجموعة متنوعة من مفاهيم الخوارزميات الأساسية، مثل ترميز Big O ، وخوارزميات فرق تسد ، وهياكل البيانات مثل الأكوام والأشجار الثنائية ، والخوارزميات العشوائية ، وتحليل أفضل وأسوأ ومتوسط ​​الحالات ، والمفاضلات بين الوقت والمساحة ، والحدود العليا والسفلى .

لا يزال فرز المصفوفات الصغيرة على النحو الأمثل (بأقل عدد من المقارنات والتبديلات) أو بسرعة (أي مع مراعاة خصائص الجهاز) يمثل مشكلة بحثية مفتوحة، ولا تتوفر حلول معروفة إلا للمصفوفات الصغيرة جدًا (أقل من 20 عنصرًا). وبالمثل، يُعد الفرز الأمثل (وفقًا لتعريفات مختلفة) على جهاز متوازٍ موضوعًا بحثيًا مفتوحًا.

يمكن تصنيف خوارزميات الفرز حسب:

• التعقيد الحسابي
  • أفضل وأسوأ ومتوسط ​​أداء الخوارزمية من حيث حجم القائمة. بالنسبة لخوارزميات الفرز التسلسلي التقليدية، يكون الأداء الجيد O(n log  n ) ، بينما يكون الفرز المتوازي O(log₂n ⁾ ، أما الأداء السيئ فهو O( n² ) . يُعدّ الأداء الأمثل للفرز التسلسلي O( n )، لكن هذا غير ممكن في الحالة المتوسطة. أما الفرز المتوازي الأمثل فهو O(log ⁿ ) .   
  • استبدال الخوارزميات "الموجودة في مكانها".
• استخدام الذاكرة (واستخدام موارد الحاسوب الأخرى). على وجه الخصوص، بعض خوارزميات الفرز " موضعية ". من الناحية الدقيقة، لا يحتاج الفرز الموضعي إلا إلى ذاكرة O(1) بعد العناصر المراد فرزها؛ وفي بعض الأحيان تُعتبر ذاكرة إضافية O(log n ) "موضعية". 
• الاستدعاء الذاتي: بعض الخوارزميات إما أن تكون عادةً استدعاء ذاتي أو عادةً غير استدعاء ذاتي، في حين أن البعض الآخر قد يكون عادةً كليهما (على سبيل المثال، فرز الدمج).
• الاستقرار: تحافظ خوارزميات الفرز المستقرة على الترتيب النسبي للسجلات ذات المفاتيح المتساوية (أي القيم).
• سواء كانت عملية فرز مقارنة أم لا ، فإن فرز المقارنة يفحص البيانات فقط من خلال مقارنة عنصرين باستخدام عامل المقارنة.
• الطرق العامة: الإضافة، والتبادل، والاختيار، والدمج، إلخ. تشمل خوارزميات فرز التبادل فرز الفقاعات والفرز السريع. وتشمل خوارزميات فرز الاختيار فرز الدورة وفرز الكومة.
• سواء كانت الخوارزمية تسلسلية أم متوازية. ويركز الجزء المتبقي من هذا النقاش بشكل شبه حصري على الخوارزميات التسلسلية ويفترض التشغيل التسلسلي.
• القدرة على التكيف: ما إذا كان ترتيب المدخلات مسبقًا يؤثر على وقت التشغيل أم لا. ومن المعروف أن الخوارزميات التي تأخذ هذا في الاعتبار تتميز بقدرتها على التكيف .
• عبر الإنترنت: يمكن لخوارزمية مثل فرز الإدراج التي تعمل عبر الإنترنت فرز تدفق مستمر من المدخلات.

استقرار

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

يُعدّ الاستقرار مهمًا للحفاظ على الترتيب عند إجراء عمليات فرز متعددة على نفس مجموعة البيانات . على سبيل المثال، لنفترض أن سجلات الطلاب التي تتكون من الاسم والشعبة الدراسية تُفرز ديناميكيًا، أولًا حسب الاسم، ثم حسب الشعبة الدراسية. إذا استُخدمت خوارزمية فرز مستقرة في كلتا الحالتين، فلن تُغيّر عملية الفرز حسب الشعبة الدراسية ترتيب الأسماء؛ أما مع خوارزمية فرز غير مستقرة، فقد يؤدي الفرز حسب الشعبة الدراسية إلى تغيير ترتيب الأسماء، مما ينتج عنه قائمة طلاب غير مرتبة أبجديًا.

بصورة أدق، يمكن تمثيل البيانات المراد فرزها كسجل أو مجموعة من القيم، ويُسمى الجزء من البيانات المستخدم في الفرز بالمفتاح . في مثال البطاقات، تُمثل البطاقات كسجل (الرتبة، النوع)، والمفتاح هو الرتبة. تكون خوارزمية الفرز مستقرة إذا كان هناك سجلان R و S لهما نفس المفتاح، وكان R يظهر قبل S في القائمة الأصلية، فإن R سيظهر دائمًا قبل S في القائمة المُفرزة.

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

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

من تطبيقات خوارزميات الفرز المستقر فرز قائمة باستخدام مفتاح أساسي ومفتاح ثانوي. على سبيل المثال، لنفترض أننا نريد فرز مجموعة من أوراق اللعب بحيث تكون أنواعها بالترتيب التالي: النوادي (♣)، والماس ( ♦ )، والقلوب ( ♥ )، والبستوني (♠)، وضمن كل نوع، يتم فرز الأوراق حسب رتبتها. يمكن القيام بذلك عن طريق فرز الأوراق أولاً حسب رتبتها (باستخدام أي خوارزمية فرز)، ثم إجراء فرز مستقر حسب النوع.

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

يفترض هذا التحليل أن طول كل مفتاح ثابت وأن جميع المقارنات والتبديلات والعمليات الأخرى يمكن أن تتم في وقت ثابت.

أسطورة:

• يمثل n عدد السجلات المراد فرزها.
• يحتوي عمود المقارنة على تصنيفات الترتيب التالية: "الأفضل" و"المتوسط" و"الأسوأ" إذا تم تحديد التعقيد الزمني لكل حالة.
• تشير كلمة "الذاكرة" إلى مقدار مساحة التخزين الإضافية التي تتطلبها الخوارزمية.
• أوقات التشغيل ومتطلبات الذاكرة المدرجة موجودة داخل ترميز Big O ، وبالتالي فإن أساس اللوغاريتمات لا يهم.
• الرمز log ² n يعني (log n ) ² .

أنواع المقارنة

فيما يلي جدول لأنواع خوارزميات المقارنة . يُظهر التحليل الرياضي أن خوارزمية المقارنة لا يمكنها أن تحقق أداءً أفضل من O ( n log n ) في المتوسط. ^{[ 4 ]}

أنواع المقارنة

اسم	أفضل	متوسط	أسوأ	ذاكرة	مستقر	في مكانه	طريقة	ملاحظات أخرى
فرز الكومة	${\displaystyle n\log n}$	${\displaystyle n\log n}$	${\displaystyle n\log n}$	1	لا	نعم	اختيار	نسخة محسّنة من خوارزمية فرز الاختيار. تقوم هذه الخوارزمية بفرز الاختيار عن طريق إنشاء كومة قصوى والحفاظ عليها لإيجاد القيمة القصوى في${\displaystyle O(\log n)}$وقت.
إنتروسورت	${\displaystyle n\log n}$	${\displaystyle n\log n}$	${\displaystyle n\log n}$	${\displaystyle \log n}$	لا	نعم	التقسيم والاختيار	يُستخدم في العديد من تطبيقات مكتبة STL . يقوم بتنفيذ مزيج من خوارزميات الفرز السريع، وفرز الكومة، وفرز الإدراج.
فرز الدمج	${\displaystyle n\log n}$	${\displaystyle n\log n}$	${\displaystyle n\log n}$	ن	نعم	لا	الاندماج	قابل للتوازي بدرجة عالية (حتى O (log n ) باستخدام خوارزمية المجريين الثلاثة). [ 5 ]
فرز الدمج في مكانه	${\displaystyle n}$	${\displaystyle n\log ^{2}n}$	${\displaystyle n\log ^{2}n}$	${\displaystyle \log n}$	نعم	نعم	الاندماج	نوع من أنواع فرز الدمج يستخدم${\displaystyle O(n\log n)}$خوارزمية دمج مستقرة في مكانها، مثل دمج الدوران أو الدمج المتناظر.
فرز البطولة	${\displaystyle n\log n}$	${\displaystyle n\log n}$	${\displaystyle n\log n}$	ن	نعم	لا	اختيار	تحسين لخوارزمية فرز الاختيار، والتي تستخدم شجرة البطولة لاختيار الحد الأدنى/الأقصى.
فرز الشجرة	${\displaystyle n\log n}$	${\displaystyle n\log n}$	${\displaystyle n\log n}$(متوازن)	ن	نعم	لا	الإدخال	عند استخدام شجرة بحث ثنائية متوازنة ذاتيًا .
فرز الكتل	ن	${\displaystyle n\log n}$	${\displaystyle n\log n}$	1	نعم	نعم	الإضافة والدمج	دمج نظام قائم على الكتل${\displaystyle O(n)}$خوارزمية الدمج في مكانها [ 6 ] مع فرز الدمج من الأسفل إلى الأعلى .
سموث سورت	ن	${\displaystyle n\log n}$	${\displaystyle n\log n}$	1	لا	نعم	اختيار	نسخة تكيفية من خوارزمية فرز الكومة تعتمد على متتالية ليوناردو بدلاً من الكومة الثنائية .
تيمسورت	ن	${\displaystyle n\log n}$	${\displaystyle n\log n}$	ن	نعم	لا	الإضافة والدمج	يصنع${\displaystyle n-1}$المقارنات عندما تكون البيانات مرتبة بالفعل أو مرتبة بشكل عكسي.
فرز الصبر	ن	${\displaystyle n\log n}$	${\displaystyle n\log n}$	ن	لا	لا	الإدخال والاختيار	يجد جميع أطول المتتاليات الفرعية المتزايدة في O ( n log n ) .
فرز المكعبات	ن	${\displaystyle n\log n}$	${\displaystyle n\log n}$	ن	نعم	لا	الإدخال	يصنع${\displaystyle n-1}$المقارنات عندما تكون البيانات مرتبة بالفعل أو مرتبة بشكل عكسي.
فرز سريع	${\displaystyle n\log n}$	${\displaystyle n\log n}$	${\displaystyle n^{2}}$	${\displaystyle \log n}$	لا	نعم	التقسيم	يمكن تنفيذ خوارزمية الفرز السريع في مكانها باستخدام مساحة مكدس تبلغ O (log n ) . [ 7 ] [ 8 ]
فلوكسورت	ن	${\displaystyle n\log n}$	${\displaystyle n\log n}$	ن	نعم	لا	التقسيم والدمج	نوع مستقر قابل للتكيف وغير متفرع.
فرز الكرم	ن	${\displaystyle n\log n}$	${\displaystyle n\log n}$	${\displaystyle \log n}$	لا	نعم	التقسيم والدمج	نسخة غير مستقرة من خوارزمية Fluxsort، ولكنها موجودة في مكانها.
فرز المكتبة	${\displaystyle n\log n}$	${\displaystyle n\log n}$	${\displaystyle n^{2}}$	ن	لا	لا	الإدخال	يشبه فرز الإدراج المتقطع.
شلسورت	${\displaystyle n\log n}$	${\displaystyle \Omega (n\log n)}$	${\displaystyle O(n^{1+1/k})}$(هندسي)${\displaystyle n\log ^{2}n}$(برات)	1	لا	نعم	الإدخال	حجم الكود صغير. يتأثر التعقيد بتسلسل الفجوات المستخدم. تسلسل برات هو أسوأ الحالات.${\displaystyle \Theta (n\log ^{2}n)}$وهو الأكثر شهرة. ولا تزال الحدود الدقيقة للحالة المتوسطة والأسوأ من المسائل المفتوحة.
فرز المشط	${\displaystyle n\log n}$	${\displaystyle n^{2}}$	${\displaystyle n^{2}}$	1	لا	نعم	التبادل	أسرع من فرز الفقاعات في المتوسط.
فرز الإدراج	ن	${\displaystyle n^{2}}$	${\displaystyle n^{2}}$	1	نعم	نعم	الإدخال	O ( n + d ) ، في أسوأ الحالات على التسلسلات التي تحتوي على d انعكاسات .
فرز الفقاعات	ن	${\displaystyle n^{2}}$	${\displaystyle n^{2}}$	1	نعم	نعم	التبادل	حجم الكود صغير جدًا.
نوع من أنواع خلاطات الكوكتيل	ن	${\displaystyle n^{2}}$	${\displaystyle n^{2}}$	1	نعم	نعم	التبادل	نسخة ثنائية الاتجاه من خوارزمية فرز الفقاعات.
فرز الأقزام	ن	${\displaystyle n^{2}}$	${\displaystyle n^{2}}$	1	نعم	نعم	التبادل	حجم الكود صغير جدًا.
فرز فردي-زوجي	ن	${\displaystyle n^{2}}$	${\displaystyle n^{2}}$	1	نعم	نعم	التبادل	يمكن تشغيله بسهولة على المعالجات المتوازية.
فرز الخيوط	ن	${\displaystyle n^{2}}$	${\displaystyle n^{2}}$	ن	نعم	لا	اختيار
فرز التحديد	${\displaystyle n^{2}}$	${\displaystyle n^{2}}$	${\displaystyle n^{2}}$	1	لا	نعم	اختيار	حجم الكود صغير جدًا. يتميز ببساطته وقلة عدد عمليات نقل العناصر. يقوم بالضبط${\displaystyle n-1}$عمليات تبادل.
فرز الدورة	${\displaystyle n^{2}}$	${\displaystyle n^{2}}$	${\displaystyle n^{2}}$	1	لا	نعم	اختيار	في مكانها مع العدد الأمثل نظرياً من عمليات الكتابة.

أنواع غير مقارنة

يصف الجدول التالي خوارزميات فرز الأعداد الصحيحة وخوارزميات الفرز الأخرى التي لا تُعدّ فرزًا مقارنًا . ولا تقتصر هذه الخوارزميات على Ω ( n log n ) إلا إذا استوفت نموذج آلة الوصول العشوائي ذات التكلفة الموحدة كما هو موضح أدناه. ^{[ 9 ]}

• تفترض التعقيدات أدناه أن يتم فرز n عنصرًا، مع مفاتيح بحجم k ، وحجم رقم d ، و r نطاق الأرقام المراد فرزها.
• يعتمد الكثير منها على افتراض أن حجم المفتاح كبير بما يكفي بحيث يكون لجميع المدخلات قيم مفتاح فريدة، وبالتالي فإن n ≪ 2 ^k ، حيث ≪ تعني "أقل بكثير من".
• في نموذج آلة الوصول العشوائي ذات التكلفة الموحدة ، الخوارزميات ذات وقت التشغيل${\displaystyle n\cdot {\frac {k}{d}}}$لا تزال عمليات مثل فرز الجذر تستغرق وقتًا يتناسب مع Θ( n log n ) ، لأن n محدودة بحيث لا تتجاوز${\displaystyle 2^{\frac {k}{d}}}$ويتطلب فرز عدد أكبر من العناصر قيمة k أكبر لتخزينها في الذاكرة. ^{[ 10 ]}

أنواع غير مقارنة

اسم	أفضل	متوسط	أسوأ	ذاكرة	مستقر	ن ≪ 2 ك	ملحوظات
تصنيف الحمام	—	${\displaystyle n+2^{k}}$	${\displaystyle n+2^{k}}$	${\displaystyle 2^{k}}$	نعم	نعم	لا يمكن فرز الأعداد غير الصحيحة.
فرز الدلو (المفاتيح الموحدة)	—	${\displaystyle n+k}$	${\displaystyle n^{2}\cdot k}$	${\displaystyle n\cdot k}$	نعم	لا	يفترض التوزيع المنتظم للعناصر من المجال في المصفوفة. [ 11 ] كما لا يمكن فرز الأعداد غير الصحيحة.
فرز الدلو (مفاتيح عددية صحيحة)	—	${\displaystyle n+r}$	${\displaystyle n+r}$	${\displaystyle n+r}$	نعم	نعم	إذا كان r هو${\displaystyle O(n)}$إذن ، متوسط ​​التعقيد الزمني هو${\displaystyle O(n)}$[ 12 ]​​
فرز العد	—	${\displaystyle n+r}$	${\displaystyle n+r}$	${\displaystyle n+r}$	نعم	نعم	إذا كان r هو${\displaystyle O(n)}$إذن ، متوسط ​​التعقيد الزمني هو${\displaystyle O(n)}$[ 11 ]​​
فرز جذور LSD	${\displaystyle n\cdot {\frac {k}{d}}}$	${\displaystyle n\cdot {\frac {k}{d}}}$	${\displaystyle n\cdot {\frac {k}{d}}}$	${\displaystyle n+2^{d}}$	نعم	لا	${\displaystyle {\frac {k}{d}}}$مستويات التكرار، 2 د لمصفوفة العد. [ 11 ] [ 12 ] على عكس معظم أنواع فرز التوزيع، يمكن لهذا النوع فرز الأعداد غير الصحيحة.
فرز جذور MSD	${\displaystyle n}$	${\displaystyle n\cdot {\frac {k}{d}}}$	${\displaystyle n\cdot {\frac {k}{d}}}$	${\displaystyle n+2^{d}}$	نعم	لا	يستخدم الإصدار المستقر مصفوفة خارجية بحجم n لتخزين جميع الخانات. كما هو الحال مع نوع LSD، يمكنه فرز الأعداد غير الصحيحة.
فرز الجذر MSD (في مكانه)	${\displaystyle n}$	${\displaystyle n\cdot {\frac {k}{1}}}$	${\displaystyle n\cdot {\frac {k}{1}}}$	${\displaystyle 2^{1}}$	لا	لا	d=1 للتثبيت في المكان،${\displaystyle k/1}$مستويات التكرار، بدون مصفوفة عد.
فرز التباعد	ن	${\displaystyle n\cdot {\frac {k}{d}}}$	${\displaystyle n\cdot \left({{\frac {k}{s}}+d}\right)}$	${\displaystyle {\frac {k}{d}}\cdot 2^{d}}$	لا	لا	تعتمد الحسابات التقاربية على افتراض أن n ≪ 2 k ، لكن الخوارزمية لا تتطلب ذلك.
فاصل الانفجار	—	${\displaystyle n\cdot {\frac {k}{d}}}$	${\displaystyle n\cdot {\frac {k}{d}}}$	${\displaystyle n\cdot {\frac {k}{d}}}$	لا	لا	يتميز بمعامل ثابت أفضل من خوارزمية فرز الجذر لفرز السلاسل النصية، مع أنه يعتمد إلى حد ما على خصائص السلاسل النصية الشائعة.
فرز سريع	ن	${\displaystyle n+r}$	${\displaystyle n^{2}}$	ن	لا	لا	يتطلب تشغيل الخوارزمية في زمن خطي توزيعًا منتظمًا للعناصر من نطاق المصفوفة. أما إذا كان التوزيع منحرفًا بشدة، فقد يصبح الزمن تربيعيًا إذا كانت عملية الفرز الأساسية تربيعية (عادةً ما تكون فرز إدراج). النسخة المطبقة في مكانها غير مستقرة.

يمكن استخدام Samplesort لموازاة أي من عمليات الفرز غير المقارنة، من خلال توزيع البيانات بكفاءة في عدة مجموعات ثم تمرير الفرز إلى عدة معالجات، دون الحاجة إلى الدمج لأن المجموعات مرتبة بالفعل فيما بينها.

آحرون

بعض الخوارزميات بطيئة مقارنةً بتلك المذكورة أعلاه، مثل خوارزمية بوغوسورت ذات زمن التشغيل غير المحدود، وخوارزمية ستوج سورت ^التي يبلغ زمن تشغيلها O ( n².⁷ ). عادةً ما تُشرح هذه الخوارزميات لأغراض تعليمية لتوضيح كيفية تقدير زمن تشغيل الخوارزميات. يوضح الجدول التالي بعض خوارزميات الفرز غير العملية للاستخدام في تطبيقات البرمجيات التقليدية نظرًا لأدائها الضعيف للغاية أو متطلباتها الخاصة من الأجهزة.

اسم	أفضل	متوسط	أسوأ	ذاكرة	مستقر	مقارنة	ملاحظات أخرى
فرز الخرز	ن	S	S	${\displaystyle n^{2}}$	— غير متوفر	لا	يعمل فقط مع الأعداد الصحيحة الموجبة. يتطلب أجهزة متخصصة لضمان تشغيله بشكل صحيح .${\displaystyle O(n)}$الوقت . هناك إمكانية لتنفيذ البرنامج، لكن وقت التشغيل سيكون ...${\displaystyle O(S)}$، حيث S هو مجموع جميع الأعداد الصحيحة المراد فرزها؛ في حالة الأعداد الصحيحة الصغيرة، يمكن اعتبارها خطية.
فرز الدمج والإدراج	${\displaystyle n\log n}$المقارنات	${\displaystyle n\log n}$المقارنات	${\displaystyle n\log n}$المقارنات	يختلف	لا	نعم	يقوم بإجراء عدد قليل جدًا من المقارنات في أسوأ الحالات مقارنة بخوارزميات الفرز الأخرى. ذات أهمية نظرية في الغالب بسبب تعقيد التنفيذ وعمليات نقل البيانات غير المثلى.
فرز السباغيتي (استطلاع الرأي)	ن	ن	ن	${\displaystyle n^{2}}$	نعم	استطلاعات الرأي	هذه خوارزمية تناظرية خطية الزمن لفرز سلسلة من العناصر، تتطلب مساحة تخزين O ( n ) في الذاكرة، والفرز مستقر. يتطلب ذلك n معالجًا متوازيًا. انظر فرز السباغيتي §  التحليل .
شبكة الفرز	يختلف	يختلف	يختلف	يختلف	يختلف (تتطلب شبكات الفرز المستقرة المزيد من المقارنات)	نعم	يتم تحديد ترتيب المقارنات مسبقاً بناءً على حجم شبكة ثابت.
فرز Bitonic	${\displaystyle \log ^{2}n}$موازي	${\displaystyle \log ^{2}n}$موازي	${\displaystyle n\log ^{2}n}$غير متوازٍ	1	لا	نعم	شكل فعال من أشكال شبكات الفرز.
بوغوسورت	ن	${\displaystyle (n\times n!)}$	غير محدود	1	لا	نعم	خلط عشوائي. يُستخدم لأغراض التوضيح فقط، حيث أن وقت التشغيل المتوقع في أفضل الحالات سيء للغاية. [ 13 ] تكون أسوأ الحالات غير محدودة عند استخدام العشوائية، لكن النسخة الحتمية تضمن${\displaystyle O(n\times n!)}$أسوأ الاحتمالات.
نوع من الأتباع	${\displaystyle n^{\log 3/\log 1.5}}$	${\displaystyle n^{\log 3/\log 1.5}}$	${\displaystyle n^{\log 3/\log 1.5}}$	${\displaystyle \log n}$	لا	نعم	أبطأ من معظم خوارزميات الفرز (حتى البسيطة منها) مع تعقيد زمني قدره O ( n log 3 / log 1.5 ) = O ( n 2.7095... ) يمكن جعلها مستقرة، وهي أيضًا شبكة فرز .
فرز بطيء	${\displaystyle o\left(n^{\log _{2}(n)/2}\right)}$	${\displaystyle o\left(n^{\log _{2}(n)/2}\right)}$	${\displaystyle o\left(n^{\log _{2}(n)/2}\right)}$	ن	لا	نعم	خوارزمية الضرب والاستسلام، وهي نقيض خوارزمية فرق تسد .

ابتكر علماء الحاسوب النظريون خوارزميات فرز أخرى توفر تعقيدًا زمنيًا أفضل من O ( n log n ) بافتراض قيود معينة، بما في ذلك:

• خوارزمية ثورب، ^{[ 14 ]} هي خوارزمية فرز أعداد صحيحة عشوائية ، تستغرق وقتًا قدره O ( n log log n ) ومساحة قدرها O ( n ). ^{[ 14 ]}
• خوارزمية AHNR، ^{[ 15 ]} خوارزمية فرز الأعداد الصحيحة التي تعمل في${\displaystyle O(n\log \log n)}$يتم تشغيلها بشكل حتمي، كما يوجد إصدار عشوائي يعمل في وقت خطي عندما تكون الكلمات كبيرة بما يكفي، على وجه التحديد${\displaystyle w\geq (\log n)^{2+\varepsilon }}$(حيث w هو حجم الكلمة).
• خوارزمية فرز الأعداد الصحيحة العشوائية تأخذ${\displaystyle O\left(n{\sqrt {\log \log n}}\right)}$الوقت المتوقع ومساحة O ( n ) . ^{[ 16 ]}

على الرغم من وجود عدد كبير من خوارزميات الفرز، إلا أن عددًا محدودًا منها هو السائد في التطبيقات العملية. يُستخدم فرز الإدراج على نطاق واسع مع مجموعات البيانات الصغيرة، بينما تُستخدم خوارزميات فرز فعّالة تقاربياً مع مجموعات البيانات الكبيرة، مثل فرز الكومة، وفرز الدمج، والفرز السريع. تستخدم التطبيقات الفعّالة عمومًا خوارزمية هجينة ، تجمع بين خوارزمية فعّالة تقاربياً للفرز الكلي وفرز الإدراج للقوائم الصغيرة في نهاية الاستدعاء الذاتي. أما التطبيقات عالية الأداء فتستخدم متغيرات أكثر تطورًا، مثل Timsort (فرز الدمج، وفرز الإدراج، ومنطق إضافي)، المستخدمة في Android و Java و Python ، و introsort (الفرز السريع وفرز الكومة)، المستخدمة (بأشكال مختلفة) في بعض تطبيقات الفرز في C++ وفي .NET .

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

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

أنواع فعالة

تعتمد خوارزميات الفرز العامة العملية في الغالب على خوارزمية ذات تعقيد زمني متوسط ​​(وتعقيد زمني في أسوأ الحالات عمومًا) قدره O( n log n )، ومن أكثرها شيوعًا فرز الكومة، وفرز الدمج، والفرز السريع. لكل منها مزايا وعيوب، أبرزها أن التنفيذ البسيط لفرز الدمج يتطلب مساحة إضافية قدرها O( n )، وأن التنفيذ البسيط للفرز السريع له تعقيد زمني في أسوأ الحالات ^قدره O( n² ). يمكن حل هذه المشكلات أو التخفيف منها باستخدام خوارزمية أكثر تعقيدًا.

على الرغم من أن هذه الخوارزميات فعّالة تقاربياً على البيانات العشوائية، إلا أنه لتحقيق الكفاءة العملية على بيانات العالم الحقيقي، تُستخدم تعديلات مختلفة. أولاً، يصبح العبء الإضافي لهذه الخوارزميات كبيراً على البيانات الصغيرة، لذا غالباً ما تُستخدم خوارزمية هجينة، حيث يتم التحول عادةً إلى فرز الإدراج بمجرد أن تصبح البيانات صغيرة بما يكفي. ثانياً، غالباً ما يكون أداء الخوارزميات ضعيفاً على البيانات المرتبة مسبقاً أو شبه المرتبة - وهي بيانات شائعة في العالم الحقيقي ويمكن فرزها في زمن O( n ) باستخدام خوارزميات مناسبة. أخيراً، قد تكون هذه الخوارزميات غير مستقرة ، والاستقرار غالباً ما يكون خاصية مرغوبة في عملية الفرز. لذلك، تُستخدم خوارزميات أكثر تطوراً، مثل Timsort (المبنية على فرز الدمج) أو introsort (المبنية على الفرز السريع، مع الرجوع إلى فرز الكومة).

فرز الدمج

تستفيد خوارزمية فرز الدمج من سهولة دمج القوائم المرتبة مسبقًا في قائمة مرتبة جديدة. تبدأ بمقارنة كل عنصرين (أي 1 مع 2، ثم 3 مع 4...) وتبديلهما إذا كان يجب أن يأتي الأول بعد الثاني. ثم تدمج كل قائمة من القوائم الثنائية الناتجة في قوائم رباعية، ثم تدمج تلك القوائم الرباعية، وهكذا؛ حتى يتم دمج قائمتين في القائمة المرتبة النهائية. ^{[ 19 ]} من بين الخوارزميات الموصوفة هنا، تُعد هذه الخوارزمية الأولى التي تتناسب جيدًا مع القوائم الكبيرة جدًا، لأن زمن تشغيلها في أسوأ الحالات هو O( n log n ). كما أنها سهلة التطبيق على القوائم، وليس المصفوفات فقط، لأنها لا تتطلب سوى الوصول التسلسلي، وليس الوصول العشوائي. عند فرز المصفوفات، يكون لها تعقيد مساحة إضافي قدره O( n )، وتتضمن عددًا كبيرًا من النسخ في التطبيقات البسيطة؛ ومع ذلك، يمكن فرز القوائم المتصلة باستخدام فرز الدمج مع مساحة إضافية ثابتة، ولذلك فهي الخوارزمية المُفضلة لفرز القوائم المتصلة.

شهدت خوارزمية فرز الدمج رواجًا متزايدًا في التطبيقات العملية مؤخرًا، نظرًا لاستخدامها في خوارزمية Timsort المتطورة ، والتي تُستخدم كخوارزمية فرز قياسية في لغتي البرمجة بايثون ^{[ 20 ]} وجافا (ابتداءً من JDK7 ^{[ 21 ]} ). وتُعدّ خوارزمية فرز الدمج نفسها الخوارزمية القياسية في لغة بيرل [ ^{22 ]} ، من بين لغات أخرى، وقد استُخدمت في جافا منذ عام 2000 على الأقل ^في JDK1.3 ^{[ 23 ]} .

فرز الكومة

يُعدّ فرز الكومة نسخةً أكثر كفاءةً من فرز التحديد . يعمل فرز الكومة أيضًا عن طريق تحديد أكبر (أو أصغر) عنصر في القائمة، ووضعه في نهاية (أو بداية) القائمة، ثم متابعة العملية مع باقي عناصر القائمة، ولكنه يُنجز هذه المهمة بكفاءة عالية باستخدام بنية بيانات تُسمى الكومة ، وهي نوع خاص من الأشجار الثنائية . ^{[ 24 ]} بمجرد تحويل قائمة البيانات إلى كومة، يُضمن أن تكون العقدة الجذرية هي أكبر (أو أصغر) عنصر. عند إزالتها ووضعها في نهاية القائمة، تُعاد ترتيب الكومة بحيث ينتقل أكبر عنصر متبقٍ إلى الجذر. باستخدام الكومة، يستغرق إيجاد العنصر الأكبر التالي وقتًا قدره O(log n )، بدلًا من O( n ) للمسح الخطي كما في فرز التحديد البسيط. هذا يسمح لفرز الكومة بالعمل في وقت قدره O( n log n )، وهو أيضًا أسوأ تعقيد في الحالة.

فرز سريع

خوارزمية الفرز السريع هي خوارزمية فرق تسد تعتمد على عملية تقسيم : لتقسيم مصفوفة، يتم اختيار عنصر يُسمى العنصر المحوري . ^{[ 25 ] [ 26 ]} تُنقل جميع العناصر الأصغر من العنصر المحوري قبله، وجميع العناصر الأكبر منه بعده. يمكن تنفيذ ذلك بكفاءة في وقت خطي وفي مكانها . ثم تُفرز القوائم الفرعية الأصغر والأكبر بشكل متكرر. ينتج عن ذلك تعقيد زمني متوسط ​​قدره O( n log n )، مع تكلفة إضافية منخفضة، ولذلك فهي خوارزمية شائعة. عادةً ما تكون التطبيقات الفعالة للفرز السريع (مع التقسيم في مكانه) خوارزميات فرز غير مستقرة ومعقدة نوعًا ما، ولكنها من بين أسرع خوارزميات الفرز عمليًا. إلى جانب استخدامها المتواضع للمساحة O(log n )، تُعد خوارزمية الفرز السريع واحدة من أكثر خوارزميات الفرز شيوعًا، وهي متوفرة في العديد من مكتبات البرمجة القياسية.

^يكمن التحذير المهم بشأن خوارزمية الفرز السريع في أن أسوأ أداء لها هو O( n² )؛ ورغم ندرة هذا، إلا أنه يحدث في التطبيقات البسيطة (باختيار العنصر الأول أو الأخير كعنصر محوري) للبيانات المرتبة، وهو أمر شائع. لذا، فإن أكثر المسائل تعقيدًا في خوارزمية الفرز السريع هي اختيار عنصر محوري مناسب، إذ أن الاختيارات السيئة باستمرار للعناصر المحورية قد تؤدي إلى أداء أبطأ بكثير O( n² ⁾ ، بينما يؤدي الاختيار الجيد للعناصر المحورية إلى أداء O( n log n )، وهو الأداء الأمثل تقاربًا. على سبيل المثال، إذا تم اختيار الوسيط كعنصر محوري في كل خطوة، فإن الخوارزمية تعمل في O( n log n ). مع ذلك، فإن إيجاد الوسيط، كما هو الحال في خوارزمية اختيار وسيط الوسائط، هو عملية O( n ) على القوائم غير المرتبة، وبالتالي يتطلب جهدًا إضافيًا كبيرًا مع عملية الفرز. عمليًا، من شبه المؤكد أن اختيار عنصر محوري عشوائي سيؤدي إلى أداء O( n log n ).    

إذا كان ضمان أداء من رتبة O( n log n ) مهمًا، فهناك تعديل بسيط لتحقيق ذلك. الفكرة، التي تعود إلى موسر، هي وضع حد أقصى لعمق الاستدعاء الذاتي. ^{[ 27 ]} إذا تم تجاوز هذا الحد، يستمر الفرز باستخدام خوارزمية فرز الكومة. اقترح موسر أن يكون الحد${\displaystyle 1+2\lfloor \log _{2}(n)\rfloor }$، وهو ما يعادل تقريبًا ضعف الحد الأقصى لعمق التكرار الذي يمكن للمرء أن يتوقعه في المتوسط ​​مع مصفوفة مرتبة عشوائيًا .

شلسورت

ابتكر دونالد شيل خوارزمية فرز شيل عام 1959. ^{[ 28 ]} وهي تُحسّن من فرز الإدراج عن طريق تحريك العناصر غير المرتبة أكثر من موضع واحد في كل مرة. ويكمن المفهوم وراء فرز شيل في أن فرز الإدراج يعمل في${\displaystyle O(kn)}$في زمن O (n²)، حيث k هي أكبر مسافة بين عنصرين غير مرتبين. هذا يعني أن أداء هذه الخوارزمية يكون عادةً O( n² ) ، ^ولكن بالنسبة للبيانات المرتبة في معظمها، والتي تحتوي على عدد قليل فقط من العناصر غير المرتبة، يكون الأداء أسرع. لذا، من خلال فرز العناصر البعيدة أولاً، ثم تقليص المسافة بينها تدريجياً، تتم عملية الفرز النهائية بسرعة أكبر بكثير. يمكن وصف إحدى طرق التنفيذ بترتيب تسلسل البيانات في مصفوفة ثنائية الأبعاد، ثم فرز أعمدة المصفوفة باستخدام فرز الإدراج.

^{يُعدّ تعقيد الوقت في} أسوأ الحالات لخوارزمية Shellsort مسألة مفتوحة ^، ويعتمد على تسلسل الفجوات المستخدم، حيث تتراوح التعقيدات المعروفة من O ( n² ) إلى O ( n⁴ ^/³ ) وΘ( n log₂n ) . هذا، بالإضافة إلى كون Shellsort خوارزميةً تُنفّذ في مكانها ، ولا تتطلب سوى قدر ضئيل نسبيًا من التعليمات البرمجية، ولا تستلزم استخدام مكدس الاستدعاءات ، يجعلها مفيدةً في الحالات التي تكون فيها الذاكرة محدودة، كما هو الحال في الأنظمة المدمجة ونواة أنظمة التشغيل .

فرز الفقاعات وأنواعه

تُعدّ خوارزميات فرز الفقاعات، ومشتقاتها مثل فرز المشط وفرز الكوكتيل ، خوارزميات فرز بسيطة وغير فعّالة للغاية. كثيراً ما تُذكر في الكتب التمهيدية لسهولة تحليلها، ولكن نادراً ما تُستخدم عملياً.

فرز الفقاعات

فرز الفقاعات خوارزمية فرز بسيطة. تبدأ الخوارزمية من بداية مجموعة البيانات، حيث تقارن أول عنصرين، وإذا كان الأول أكبر من الثاني، فإنها تبدلهما. وتستمر في فعل ذلك لكل زوج من العناصر المتجاورة حتى نهاية مجموعة البيانات. ثم تبدأ من جديد مع أول عنصرين، وتكرر العملية حتى لا يحدث أي تبديل في الدورة الأخيرة. ^{[ 29 ]} يبلغ متوسط ​​وقت هذه الخوارزمية وأداؤها في أسوأ الحالات O( ^n² ) ، لذا نادرًا ما تُستخدم لفرز مجموعات البيانات الكبيرة غير المرتبة. يمكن استخدام فرز الفقاعات لفرز عدد قليل من العناصر (حيث لا يمثل عدم كفاءتها التقاربية عيبًا كبيرًا). كما يمكن استخدامها بكفاءة على قائمة بأي طول مرتبة تقريبًا (أي أن العناصر ليست خارجة عن ترتيبها بشكل ملحوظ). على سبيل المثال، إذا كان أي عدد من العناصر خارج مكانه بمقدار موضع واحد فقط (مثل 0123546789 و 1032547698)، فإن عملية التبادل في فرز الفقاعات ستجعلها مرتبة في المرور الأول، وسيجد المرور الثاني جميع العناصر بالترتيب، لذلك سيستغرق الفرز 2n مرة فقط .

فرز المشط

فرز المشط هو خوارزمية فرز بسيطة نسبيًا تعتمد على فرز الفقاعات ، وقد صممها في الأصل فلودزيميرز دوبوسيفيتش عام 1980. ^{[ 30 ]} أُعيد اكتشافها ونشرها لاحقًا على يد ستيفن لاسي وريتشارد بوكس ​​من خلال مقال نُشر في مجلة بايت في أبريل 1991. تتلخص الفكرة الأساسية في التخلص من "السلاحف "، أو القيم الصغيرة القريبة من نهاية القائمة، لأنها تُبطئ عملية الفرز بشكل كبير في فرز الفقاعات. (أما " الأرانب" ، وهي القيم الكبيرة في بداية القائمة، فلا تُشكل مشكلة في فرز الفقاعات). يُحقق فرز المشط ذلك عن طريق تبديل العناصر التي تفصل بينها مسافة معينة في المصفوفة، بدلًا من تبديل العناصر المتجاورة فقط، ثم تقليص المسافة المختارة تدريجيًا حتى يعمل كفرز فقاعات عادي. وبالتالي، إذا كان فرز شيل يُعتبر نسخة مُعممة من فرز الإدراج تُبدل العناصر المتباعدة بمسافة معينة، فإن فرز المشط يُمكن اعتباره نفس التعميم مُطبقًا على فرز الفقاعات.

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

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

إحدى طرق التغلب على هذه المشكلة، والتي تُجدي نفعًا عند فرز السجلات المعقدة (كما هو الحال في قواعد البيانات العلائقية ) باستخدام حقل مفتاح صغير نسبيًا، هي إنشاء فهرس في المصفوفة ثم فرز الفهرس، بدلًا من فرز المصفوفة بأكملها. (يمكن حينها إنتاج نسخة مُفرزة من المصفوفة بأكملها بقراءة واحدة من الفهرس، ولكن غالبًا ما يكون ذلك غير ضروري، إذ يكفي وجود الفهرس المُفرز). ولأن الفهرس أصغر بكثير من المصفوفة بأكملها، فإنه قد يتسع بسهولة في الذاكرة حيث لا تتسع المصفوفة بأكملها، مما يُزيل فعليًا مشكلة تبديل القرص. تُسمى هذه العملية أحيانًا "فرز الوسوم". ^{[ 32 ]}

من التقنيات الأخرى للتغلب على مشكلة حجم الذاكرة استخدام الفرز الخارجي ، فعلى سبيل المثال، تتمثل إحدى الطرق في دمج خوارزميتين بطريقة تستفيد من نقاط قوة كل منهما لتحسين الأداء العام. فعلى سبيل المثال، يمكن تقسيم المصفوفة إلى أجزاء بحجم يتناسب مع ذاكرة الوصول العشوائي (RAM)، ثم فرز محتويات كل جزء باستخدام خوارزمية فعالة (مثل الفرز السريع )، ودمج النتائج باستخدام دمج متعدد الاتجاهات (k -way merge merge) مشابه للدمج المستخدم في فرز الدمج . هذه الطريقة أسرع من تطبيق فرز الدمج أو الفرز السريع على القائمة بأكملها. ^{[ 33 ] [ 34 ]}

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

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

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

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

توجد خوارزميات فرز للمقارن "الضوضائي" (الذي قد يكون غير صحيح)، وخوارزميات فرز لزوج من المقارنات "السريعة وغير الدقيقة" (أي "الضوضائية") و"الدقيقة". قد يكون هذا مفيدًا عندما تكون دالة المقارنة الكاملة مكلفة. ^{[ 35 ]}

• التجميع – تجميع المعلومات المكتوبة في ترتيب قياسي 
• تسلسل مصنف K
• تحويل شوارتز – أسلوب برمجي لفرز قائمة بكفاءة باستخدام مفتاح محسوب 
• خوارزمية البحث – أي خوارزمية تحل مشكلة البحث 
• الفرز الكمومي – خوارزميات الفرز لأجهزة الكمبيوتر الكمومية 

• كنوت، دونالد إي. (1998)، الفرز والبحث ، فن برمجة الحاسوب، المجلد  3 (  الطبعة الثانية)، بوسطن: أديسون-ويسلي، ISBN 0-201-89685-0
• سيدجويك، روبرت (1980)، "الفرز الفعال بواسطة الحاسوب: مقدمة" ، الاحتمالات الحسابية ، نيويورك: أكاديميك برس، ص 101-130 ، ISBN  0-12-394680-8

• رسوم متحركة لخوارزمية الفرز على موقع Wayback Machine (تمت أرشفته في 3 مارس 2015) .
• خوارزميات الفرز التسلسلي والمتوازي – شروحات وتحليلات للعديد من خوارزميات الفرز.
• قاموس الخوارزميات وهياكل البيانات والمشاكل – قاموس الخوارزميات والتقنيات والوظائف الشائعة والمشاكل.
• نظرة متشككة بعض الشيء حول خوارزميات الفرز - يناقش العديد من الخوارزميات الكلاسيكية ويروج لبدائل لخوارزمية الفرز السريع .
• 15 خوارزمية فرز في 6 دقائق (يوتيوب) - عرض مرئي و"مسموع" لـ 15 خوارزمية فرز في 6 دقائق.
• التسلسل A036604 في قاعدة بيانات OEIS بعنوان "فرز الأرقام: الحد الأدنى لعدد المقارنات اللازمة لفرز n عنصرًا" - تم تنفيذه بواسطة خوارزمية فورد جونسون .
• خوارزميات الفرز المستخدمة في اللوحات الشهيرة (يوتيوب) - عرض مرئي لخوارزميات الفرز على العديد من اللوحات الشهيرة.
• مقارنة خوارزميات الفرز - يقوم بتشغيل سلسلة من الاختبارات على 9 من خوارزميات الفرز الرئيسية باستخدام Python timeit و Google Colab .