عرض مصدر فرز فقاعي

{{بطاقة خوارزمية|اسم=ترتيب فقاعي|الصورة=[[ملف:Bubble sort animation.gif]]|الصنف=[[خوارزمية ترتيب]]|بنية المعطيات=[[مصفوفة (توضيح)|مصفوفة]]|زمن أسوأ={{يسار إلى يمين|О(''n''<sup>2</sup>)}}|زمن وسطي=|أداء وسطي={{يسار إلى يمين|О(''n''<sup>2</sup>)}}|زمن مثالي={{يسار إلى يمين|О(''n'')}}|الفضاء={{يسار إلى يمين|О(''1'')}}|اسم أصلي=ترتيب الفقاعات|حجم الصورة=}}[[ملف:Bubblesort-edited-color.svg|تصغير|يسار|200بك|ترتيب_الفقاعات]]
'''الفرز الفقاعي'''<ref>{{ترقيم استشهادات|نمط=محرف عربي
|م1={{استشهاد بويكي بيانات|Q124094449|ص=54}}
|م2={{استشهاد بويكي بيانات|Q113638576|ص=47}}
|م3={{استشهاد بويكي بيانات|Q108408025|ص=63}}
}}</ref> {{إنج|Bubble sort}} هي [[خوارزمية ترتيب]] منتقدة لبطئها<ref name=":0">[[دونالد كينوث|Donald Knuth]].</ref><ref>{{استشهاد بويب |الأخير=Cortesi |الأول=Aldo |عنوان=Visualising Sorting Algorithms |مسار=https://corte.si/posts/code/visualisingsorting/index.html |تاريخ=27 April 2007 |تاريخ الوصول=16 March 2017| مسار أرشيف = http://web.archive.org/web/20170707184753/https://corte.si/posts/code/visualisingsorting/index.html | تاريخ أرشيف = 07 يوليو 2017 }}
</ref><ref>
{{استشهاد بويب|مسار=http://www.jargon.net/jargonfile/b/bogo-sort.html|عنوان=jargon, node: bogo-sort|ناشر=| مسار أرشيف = https://web.archive.org/web/20170505132315/http://www.jargon.net/jargonfile/b/bogo-sort.html | تاريخ أرشيف = 05 مايو 2017 }}</ref><ref>{{استشهاد بدورية محكمة |الأخير1=Astrachan |الأول1=Owen |عنوان=Bubble sort: an archaeological algorithmic analysis |مسار=https://users.cs.duke.edu/~ola/papers/bubble.pdf |صحيفة=ACM SIGCSE Bulletin |المجلد=35 |العدد=1 |سنة=2003 |صفحات=1–5 |issn=0097-8418 |doi=10.1145/792548.611918| مسار أرشيف = https://web.archive.org/web/20150923211503/http://www.cs.duke.edu/~ola/papers/bubble.pdf | تاريخ أرشيف = 23 سبتمبر 2015 }}</ref> ، هي تعمل على رفع العنصر الأكبر كفقاعة الهواء التي ترتفع إلى أعلى وذلك بترتيب العناصر بتتابع، أي نقوم بمقارنة العنصرين الأول والثاني، ونحتفظ بالعنصر الأكبر، ونبدل الأماكن إذا كانا غير مرتبين، ونقوم بهذه العملية إلى آخر عنصر، وبعد ذلك نعيد العمليات إلى المكان ما قبل الأخير وهكذا دواليك، ثم نتوقف عند وجود جدول بالبعد 1 أو عندما لا نقوم بالتبديلات عند آخر عملية.

لترتيب N عناصر في المصفوفة A ، عدد المقارنات سيكون: <math>{N(N-1) \over 2} = \sum_{i=0}^N x_i</math>.

أما عدد التبديلات فهو في المتوسط <math>N(N-1) \over 4</math>. حيث N هي عدد العناصر.

تعقيد الخوارزم هو <math> \mathcal{O} \left(n^2 \right) </math> في المعدل، و<math> \mathcal{O} \left(n \right) </math> في الحالة المثلى.

== خوارزمية الفرز الفقاعي ==
<div class="ltr"><!-- Code blocks don't accept direction or text-align properties in firefox, therefore I had to wrap it into a div -->
<div style="direction:ltr;">
<code>

 '''procedure''' bubbleSort(A ''':''' list of sortable items) '''defined as:'''
 '''do'''
 swapped := false
 '''for each''' i '''in''' 0 '''to''' length(A) - 2 '''inclusive do:'''
 '''if''' A[ i ] > A[ i + 1 ] '''then'''
  swap(A[ i ], A[ i + 1 ])
  swapped := true
 '''end if'''
 '''end for'''
 '''while''' swapped
 '''end procedure'''
</code>
</div>
</div>

== في الاستخدام العملي ==
<div class="ltr">
مع أن ترتيب الفقاعات هو أحد أسهل الخوارزمات للفهم والتطبيق، إلا أن تعقيده الزمني <math> \mathcal{O} \left(n^2 \right) </math> يجعل كفائته تقل كلما زاد طول المدخل، هذا يجعل منه خوارزم غير ملائم لترتيب مصفوفات كبيرة. خوارزمات أخرى بتعقيد <math> \mathcal{O} \left(n^2 \right) </math> مثل [[ترتيب بالإدراج|الترتيب بالإدراج]] تتمكن من حل المشكلة بكفائة أعلى.

بسبب بساطة الخوارزم يتم استخدامه كأول مثال لخوارزم ترتيب يتعلمه طلاب علم الحاسوب. لكن بعض الباحثين مثل Owen Astrachan ينصحون بالابتعاد عن هذا الخوارزم وعدم استخدامه حتى في التعليم.<ref>Owen Astrachan. Bubble Sort: An Archaeological Algorithmic Analysis. SIGCSE 2003 Hannan Akhtar . [https://users.cs.duke.edu/~ola/papers/bubble.pdf (pdf)] {{Webarchive|url=https://web.archive.org/web/20090915042852/http://www.cs.duke.edu/~ola/papers/bubble.pdf |date=15 سبتمبر 2009}}</ref>

قاموس The Jargon File الذي سمى خوارزم Bogosort ب«المثال الأعلى لخوارزم شنيع» سمى خوارزم الترتيب بالفقاعات «خوارزم سيء».<ref>{{استشهاد بويب
| مسار = http://www.jargon.net/jargonfile/b/bogo-sort.html
| عنوان = jargon, node: bogo-sort
| موقع = www.jargon.net
| تاريخ الوصول = 2016-12-30
| مسار أرشيف = https://web.archive.org/web/20170505132315/http://www.jargon.net/jargonfile/b/bogo-sort.html | تاريخ أرشيف = 5 مايو 2017 }}</ref> في كتاب [[فن برمجة الحاسوب]] يستنتج [[دونالد كينوث|دونالد كانوث]] «لا يوجد سبب للنظر في خوارزم ترتيب الفقاعات الا اسمه الجميل وكونه يولد بعض المشاكل النظرية المثيرة للاهتمام», ثم يقوم بذكر بعض هذه المشاكل النظرية.

</div>

== ترتيب الفقاعات بلغات مختلفة ==

=== كود ترتيب الفقاعات بلغة C ===
<!-- Code blocks don't accept direction or text-align properties in firefox, therefore I had to wrap it into a div -->
<syntaxhighlight lang="c">
 typedef int tab_entiers[MAX];
 void bubble_sort(tab_entiers t) {
 	int i، j، tmp;
 	for(i = 1 ; i < MAX ; i++)
 		for(j = 0 ; j < MAX - i ; j++)
 			if(t[j] > t[j+1]) {
 				tmp = t[j+1];
 				t[j+1] = t[j];
 				t[j] = tmp;
 			}
 }
</syntaxhighlight>

=== كود ترتيب الفقاعات بلغة Java ===
<!-- Code blocks don't accept direction or text-align properties in firefox, therefore I had to wrap it into a div -->
<syntaxhighlight lang="c">
 [MAX];
 public class Bubble_sort {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		
		int name[]= {20,10,-5,6,2,1};
		int a = 0 ;
		for (int x = 0; x < name.length; x++) 
			System.out.print(name[x]+"   ");
		System.out.println();

		 for (int x = name.length - 1 ; x > 0; x--) {
			for (int y = 0; y < name.length-1; y++) {
				int temp = name[y];
				int temp2 = name[y+1]; 
				if(name[y] > name[y+1]) {
					name[y]  = temp2;
					name[y+1]= temp ;
					a++ ;
					for (int m = 0; m < name.length; m++) 
						System.out.print(name[m]+"   ");
					System.out.println(); 
					

				}			
			} 					System.out.println();

		}
	    for (int v = 0; v < name.length; v++) 
			System.out.print(name[v]+"   ");
		System.out.println();
		System.out.println("the num of changes of the array is "+a);

		
	}
	}
}
 }
</syntaxhighlight>
== مراجع ==
{{مراجع}}

{{خوارزميات الترتيب}}
{{شريط بوابات|خوارزميات|رياضيات|علم الحاسوب}}

{{تصنيف كومنز|Bubble sort}}

[[تصنيف:خوارزميات ترتيب]]