Bubble Sort — முழு விளக்கம்

Bubble sort என்பது அண்டை உறுப்புகளை ஒப்பிட்டு, தேவையானால் பரிமாற்றம் செய்வதன் மூலம் வரிசைப்படுத்தும் எளிய கதை. பெரிய தரவில் இது அரிதாகவே பயன்படும்; ஆனால் invariant, pass, stability போன்ற கருத்துகளைப் புரிந்துகொள்ள இது சிறந்த முதல் படி.

உண்மை உலகில் இது ஏன் முக்கியம்?

ஐந்து குழந்தைகளின் உயரத்தை ஒரு புகைப்படத்திற்கு வரிசைப்படுத்தும் செவிலியர் கற்பனை செய்து பாருங்கள்: நீங்கள் மீண்டும் மீண்டும் வரிசையில் நடந்து, தவறான இடத்தில் இருப்பவர்களைப் பரிமாற்றலாம் — இதுவே bubble sort. விமான நிலையத்தில் சில gate மாற்றங்கள், கிடங்கில் சில pallet-கள் மட்டுமே திரையில் இருக்கும்போது சிறிய nக்கு எளிய குறியீடு முக்கியமாக இருக்கும். ஆனால் கோடிக்கணக்கான பதிவுகள் இருந்தால், அதே முறை பயனர்களுக்காகக் காத்திருக்கும் CPU நேரத்தை வீணடிக்கும்.

மையக் கருத்து (மாணவர்களுக்கான விளக்கம்)

வலது முனையில் வரிசைப்படுத்தப்பட்ட பின்னொட்டு (sorted suffix) வளர்வதை மனதில் கொள்ளுங்கள். ஒவ்வொரு வெளிப்புற சுற்றிலும் இடமிருந்து வலதுக்கு நடந்து, a[i] > a[i+1] என்றால் பரிமாற்றம் செய்யவும். p ஆவது சுற்றுக்குப் பிறகு, வலது முனையில் p பெரிய உறுப்புகள் நிலைநிறுத்தப்படுகின்றன. swapped கொடி சேர்த்தால், ஒரு சுற்றில் பரிமாற்றம் இல்லையெனில் ஏற்கனவே வரிசைப்படுத்தப்பட்டது — சிறந்த சூழலில் O(n). சராசரி/மோசமான சூழலில் ஒப்பீடுகள் O(n²) என்பதை மறக்காதீர்கள்.

Pythonில் முயற்சி செய்வோம்

def bubble_sort(a: list[int]) -> list[int]:
    a = a[:]
    n = len(a)
    for i in range(n):
        swapped = False
        for j in range(0, n - 1 - i):
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
                swapped = True
        if not swapped:
            break
    return a


print(bubble_sort([4, 1, 3, 9, 2]))

அடிக்கடி நேரும் தவறுகள்

• ஒவ்வொரு pass-க்கும் உட்புற வளையத்தின் மேல் எல்லையைக் குறைக்க மறந்துவிடுதல்.
• நகல் மதிப்புகள் அதிகமாக இருந்தாலும் எல்லை சுருக்காமல் விடுவது.
• ஒப்பீடுகள் எண்ணிக்கையையும் பரிமாற்ற எண்ணிக்கையையும் கலந்துவிடுவது.

முக்கியச் சுருக்கக் குறிப்புகள்

• இடது உறுப்பு உண்மையில் பெரியது என்றால் மட்டுமே பரிமாற்றம் செய்தால் stable sort.
• சராசரி/மோசம் O(n²); ஏற்கனவே sorted என்று கண்டுபிடித்தால் சிறந்தது O(n).
• கற்பித்தலுக்கு ஏற்றது; உண்மையான சிறிய production பாதைகளில் insertion sort அல்லது library sort பயன்படுத்தவும்.