Bubble Sort คือ?

Bubble Sort เป็นอัลกอริทึมการจัดเรียงที่ง่ายที่สุด โดยการเปรียบเทียบข้อมูลสองตำแหน่งที่อยู่ติดกัน ถ้าข้อมูลเรียงกันไม่ถูกต้องก็จะถูกสลับไปเรื่อยๆจนถึงคู่สุดท้าย จะเรียงจากน้อยไปมาก (Ascending) หรือมากไปน้อย (Descending) ก็ได้ แต่อัลกอริทึมนี้ไม่เหมาะกับข้อมูลขนาดใหญ่เนื่องจากความซับซ้อนของเวลา (Time complexity) ค่อนข้างสูง

Bubble Sort ทำงานอย่างไร?

ตัวอย่าง: 5 1 4 2 8 ให้เรียงจากน้อยไปมาก
รอบที่ 1: เริ่มต้นด้วยการเปรียบเทียบคู่แรกแล้วจับคู่ไปเรื่อยๆ ดูว่าตัวใดมากกว่ากันให้สลับไปอยู่ด้านขวา

( 5 1 4 2 8 ) –> ( 1 5 4 2 8 ) 5 > 1 สลับ
( 1 5 4 2 8 ) –> ( 1 4 5 2 8 ) 5 > 4 สลับ
( 1 4 5 2 8 ) –> ( 1 4 2 5 8 ) 5 > 2 สลับ
( 1 4 2 5 8 ) –> ( 1 4 2 5 8 ) 5 < 8 ไม่ต้องสลับ

รอบที่ 2: ทำซ้ำเหมือนรอบแรก

( 1 4 2 5 8 ) –> ( 1 4 2 5 8 )
( 1 4 2 5 8 ) –> ( 1 2 4 5 8 ) 4 > 2 สลับ
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )

รอบที่ 3: ตอนนี้ข้อมูลถูกจัดเรียงแล้ว แต่อัลกอริทึมของเราไม่รู้ว่ามันเสร็จสมบูรณ์หรือไม่ ดังนั้นต้องทำอีกหนึ่งครั้ง หากไม่มีการสลับเกิดขึ้นเลย โปรแกรมจะรู้ว่าข้อมูลจัดเรียงสำเร็จ

( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )

ตัวอย่างการเขียนโค้ด

#include <iostream>
using namespace std;

void bubbleSort(int arr[], int n){
	for (int i = 0; i < n - 1; i++)
		for (int j = 0; j < n - 1; j++)
			if (arr[j] > arr[j + 1])
				swap(arr[j], arr[j + 1]);
}

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

int main()
{
	int arr[] = { 5, 2, 4, 6, 1, 3};
	int size = sizeof(arr) / sizeof(arr[0]);
	bubbleSort(arr, size);
	cout << "Sorted array: ";
	printArray(arr, size);
	return 0;
}

ผลลัพธ์:
Sorted array: 1 2 3 4 5 6

Worst and Average Case Time Complexity: O(N²)
Best Case Time Complexity: O(N) กรณีที่ข้อมูลถูกจัดเรียงแล้ว