DAA - เรียงฟอง

Bubble Sort เป็นอัลกอริทึมการเรียงลำดับพื้นฐานซึ่งทำงานโดยแลกเปลี่ยนองค์ประกอบที่อยู่ติดกันซ้ำ ๆ หากจำเป็น เมื่อไม่จำเป็นต้องมีการแลกเปลี่ยนไฟล์จะถูกจัดเรียง

นี่เป็นเทคนิคที่ง่ายที่สุดในบรรดาอัลกอริทึมการเรียงลำดับ

Algorithm: Sequential-Bubble-Sort (A) 
fori← 1 to length [A] do 
for j ← length [A] down-to i +1 do 
   if A[A] < A[j - 1] then 
      Exchange A[j] ↔ A[j-1]

การนำไปใช้

voidbubbleSort(int numbers[], intarray_size) { 
   inti, j, temp; 
   for (i = (array_size - 1); i >= 0; i--) 
   for (j = 1; j <= i; j++) 
      if (numbers[j - 1] > numbers[j]) { 
         temp = numbers[j-1]; 
         numbers[j - 1] = numbers[j]; 
         numbers[j] = temp; 
      } 
}

การวิเคราะห์

ที่นี่จำนวนการเปรียบเทียบคือ

1 + 2 + 3 +...+ (n - 1) = n(n - 1)/2 = O(n²)

เห็นได้ชัดว่ากราฟแสดงไฟล์ n² ลักษณะของการเรียงฟอง

ในอัลกอริทึมนี้จำนวนการเปรียบเทียบจะไม่คำนึงถึงชุดข้อมูลกล่าวคือองค์ประกอบอินพุตที่ให้มาจะเรียงตามลำดับหรือเรียงลำดับย้อนกลับหรือสุ่ม

ความต้องการหน่วยความจำ

จากอัลกอริทึมที่ระบุไว้ข้างต้นเป็นที่ชัดเจนว่าการเรียงฟองไม่จำเป็นต้องใช้หน่วยความจำเพิ่มเติม

ตัวอย่าง

Unsorted list:

5 2 1 4 3 7 6

1 ^{เซนต์}ซ้ำ:

5 > 2 swap	2 5 1 4 3 7 6
5 > 1 swap	2 1 5 4 3 7 6
5 > 4 swap	2 1 4 5 3 7 6
5 > 3 swap	2 1 4 3 5 7 6
5 < 7 no swap	2 1 4 3 5 7 6
7 > 6 swap	2 1 4 3 5 6 7

การทำซ้ำ2 ^{ครั้ง} :

2 > 1 swap	1 2 4 3 5 6 7
2 < 4 no swap	1 2 4 3 5 6 7
4 > 3 swap	1 2 3 4 5 6 7
4 < 5 no swap	1 2 3 4 5 6 7
5 < 6 no swap	1 2 3 4 5 6 7

มีการเปลี่ยนแปลงใน 3 ไม่เป็น^ถนน 4 ^วัน 5 ^วันและ 6 ^THซ้ำ

สุดท้าย

the sorted list is

1 2 3 4 5 6 7