ബബിൾ സോർട്ട്

ബബിൾ_സോർട്ട് എഡിറ്റുചെയ്ത നിറം

ഒരു അടുക്കിലെയോ പട്ടികയിലെയോ സംഖ്യകളെയും മറ്റും ക്രമത്തിലാക്കാൻ ഉപയോഗിക്കുന്ന ഒരു ക്രമീകരണ അൽഗൊരിതമാണ്‌ ബബിൾ ക്രമീകരണം (Bubble Sort) അഥവാ കുമിള ക്രമീകരണം. വിവരിക്കാൻ എളുപ്പമുള്ളതും, സമയസങ്കീർണ്ണത കൂടിയതിനാൽ വളരെ സമയമെടുക്കുന്നതുമായ ഒരു ക്രമീകരണ അൽഗൊരിതമാണിത്. $N$അംഗങ്ങളുള്ള ഇൻപുട്ട് ക്രമപ്പെടുത്താനായിക്കൊണ്ട് ഈ അൽഗൊരിതത്തിന് വേണ്ടുന്ന സമയസങ്കീർണ്ണത $O(N^2)$ഉം സ്ഥലസങ്കീർണ്ണത $O(N)$ഉമാണ്‌. ഒരു സ്വസ്ഥല അൽഗൊരിതമാണ്‌ (in-place algorithm) ഇത് എന്നതിനാൽ ഇൻപുട്ടിന് പുറമെ $O(1)$മെമ്മറി മാത്രമേ ഇതിന്‌ ആവശ്യമുള്ളൂ.

ക്രമത്തിലല്ലാത്തവയും അടുത്തടുത്തുള്ളവയുമായ സംഖ്യകളെ പരസ്പരം ആവർത്തിച്ചാവർത്തിച്ച് മാറ്റുന്നതു വഴിയാണ്‌ ബബിൾ ക്രമീകരണം സംഖ്യകളെ ക്രമീകരിക്കുന്നത്. ക്രമീകരിക്കപ്പെട്ട സംഖ്യകൾ കുമിളകളെപ്പോലെ (bubbles) പട്ടികയുടെ ഒരു ഭാഗത്തേക്കു പോകുന്നു എന്നതിനാലാണ്‌ ഈ അൽഗൊരിതത്തിന്‌ പേര്‌ ലഭിച്ചത്. സംഖ്യകളെ താരതമ്യം ചെയ്ത് ക്രമീകരിക്കുന്നതിനാൽ ഇത് ഒരു താരതമ്യ സോർട്ട് ആണ്‌.

അൽഗൊരിതം

$A[1..N]$എന്ന ചിഹ്നത്താൽ കുറിയ്ക്കുന്നതും $N$അംഗങ്ങളുള്ളതുമായ ഒരടുക്ക് ഇൻപുട്ടായി തന്നിട്ടുണ്ടെന്ന് കരുതുക. $N$ഘട്ടങ്ങളായാണ് ബബിൾ ക്രമീകരണ അൽഗൊരിതം പ്രവർത്തിക്കുന്നത്.

ആദ്യഘട്ടത്തിൽ ഇനിപ്പറയുന്ന പ്രക്രിയ ചെയ്യുക. $A[1]$ഉം $A[2]$ഉം താരതമ്യം ചെയ്യുക. $A[1]>A[2]$ആണെങ്കിൽ ആ രണ്ട് വിലകളെയും അടുക്കിൽ പരസ്പരം സ്ഥാനം മാറ്റുക. കൂടുതൽ വ്യക്തമായിപ്പറഞ്ഞാൽ, $A[1]$ഇൽ $A[2]$ന്റെ വില സൂക്ഷിക്കുകയും $A[2]$ഇൽ $A[1]$ന്റെ വില സൂക്ഷിക്കുകയും ചെയ്യുക. മറിച്ച് $A[1]<A[2]$ആണെങ്കിൽ അവയെ അവഗണിച്ച് $A[2]$നെയും $A[3]$നെയും മേൽപ്പറഞ്ഞ പ്രക്രിയയ്ക്ക് വിധേയമാക്കുക. ഇപ്രകാരം $N-1$തവണ ഇതേ പ്രക്രിയ ആവർത്തിച്ചു കഴിഞ്ഞാൽ (അഥവാ $A[N-1]$ഉം $A[N]$ഉം ഇതേ പ്രക്രിയയ്ക്ക് വിധേയമായിക്കഴിഞ്ഞാൽ), ഒന്നാമത്തെ ഘട്ടം കഴിഞ്ഞു.

രണ്ടാമത്തെ ഘട്ടത്തിൽ മേൽപ്പറഞ്ഞ പ്രക്രിയകൾ $N-2$തവണയേ ആവർത്തിക്കുന്നുള്ളൂ. അതായത് $A[N-2]$ഉം $A[N-1]$ഉം ഈ പ്രക്രിയക്ക് വിധേയമായിക്കഴിയുന്നതു വരെ മാത്രം. ഇപ്രകാരം $i$ആമത്തെ ഘട്ടത്തിൽ മേൽപ്പറഞ്ഞ പ്രക്രിയകൾ $N-i$തവണ മാത്രം ആവർത്തിക്കുന്നു.

ഇങ്ങനെ ആകെ $N$ഘട്ടങ്ങൾക്കു ശേഷം അടുക്കിലെ അംഗങ്ങളെല്ലാം ക്രമത്തിലാകും.

ഔപചാരിക വിവരണം

$N$അംഗങ്ങളുള്ള $A$എന്ന അടുക്ക് ബബിൾ ക്രമീകരണം വഴി ക്രമപ്പെടുത്താൻ:

1. അവസാനം $\leftarrow N$
2. കൊടി $\leftarrow$ ശരി
3. (അവസാനം == 1 അഥവാ കൊടി == തെറ്റ്) ആണെങ്കിൽ നിർത്തുക
4. കൊടി $\leftarrow$ തെറ്റ്
5. $1$മുതൽ അവസാനം$-1$ വരെയുള്ള വിലകൾ ഓരോന്നോരോന്നായി $i$യ്ക്ക് നൽകി പടി 6ഉം 7ഉം ചെയ്യുക
6. $A[i]>A[i+1]$ആണെങ്കിൽ അവയെ പരസ്പരം സ്ഥലം മാറ്റുക                                                     7. കൊടി $\leftarrow$ ശരി
8. അവസാനം $\leftarrow$അവസാനം $-1$
9. 3ആം പടിയിലേക്ക് പോകുക

വിശകലനം

സംഖ്യകൾ തികച്ചും വിപരീതക്രമത്തിലാകുമ്പോൾ $\frac{N(N-1)}{2}$തവണ പടി 6 ചെയ്യേണ്ടി വരുന്നു എന്നതിനാൽ കുമിളക്രമീകരണത്തിന്റെ കൂടിയ സമയസങ്കീർണ്ണത $O(N^2)$ആണ്‌. സംഖ്യകൾ തികച്ചും ക്രമത്തിലാകുമ്പോൾ ഇത് $N-1$തവണ മാത്രം ചെയ്താൽ മതി എന്നതിനാൽ കുറഞ്ഞ സമയസങ്കീർണ്ണത $O(N)$ ആണ്‌. ശരാശരി സമയസങ്കീർണ്ണത $O(N^2)$തന്നെ. ശരാശരി, കൂടിയ സമയസങ്കീർണ്ണതകൾ $O(N\log N)$ആയുള്ള ക്രമീകരണ അൽഗൊരിതങ്ങൾ ഉണ്ട്. $O(N^2)$സമയസങ്കീർണ്ണത ഉള്ള ഇൻസർഷൻ സോർട്ട് മുതലായ അൽഗൊരിതങ്ങളും കുമിളക്രമീകരണത്തെക്കാൾ വേഗത്തിൽ ക്രമീകരണം നടത്തുന്നു എന്നതിനാൽ വലിയ പട്ടികകളോ അടുക്കുകളോ ക്രമപ്പെടുത്താൻ കുമിളക്രമീകരണം ഉപയോഗിക്കാറില്ല.

പുറത്തേക്കുള്ള കണ്ണികൾ

• Bubble Sort in 29 languages ഫലകം:Webarchive
• Animated Sorting Algorithms: Bubble Sort – graphical demonstration and discussion of bubble sort
• Bubble Sort Demo ഫലകം:Webarchive
• Bubble Sort Demonstration
• Lafore's Bubble Sort ഫലകം:Webarchive
• Sorting Applets in C++
• Analyze Bubble Sort in an online Javascript IDE
• A colored graphical Java applet ഫലകം:Webarchive which allows experimentation with initial state and shows statistics
• BubbleSort tutorial, code, and a simple example ഫലകം:Webarchive
• An animated video that explains bubble sort and quick sort and compares their performance.
• A much better visualization of the action of bubble sort.