ബബിൾ സോർട്ട്

ഒരു അടുക്കിലെയോ പട്ടികയിലെയോ സംഖ്യകളെയും മറ്റും ക്രമത്തിലാക്കാൻ ഉപയോഗിക്കുന്ന ഒരു ക്രമീകരണ അൽഗൊരിതമാണ്‌ **ബബിൾ ക്രമീകരണം** (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[3]നെയും മേൽപ്പറഞ്ഞ പ്രക്രിയയ്ക്ക് വിധേയമാക്കുക. ഇപ്രകാരം N-1തവണ ഇതേ പ്രക്രിയ ആവർത്തിച്ചു കഴിഞ്ഞാൽ (അഥവാ A[N-1]ഉം A[N]ഉം ഇതേ പ്രക്രിയയ്ക്ക് വിധേയമായിക്കഴിഞ്ഞാൽ), ഒന്നാമത്തെ ഘട്ടം കഴിഞ്ഞു.

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

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

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

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



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

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

വർഗ്ഗം:സോർട്ടിങ്ങ് അൽഗൊരിതങ്ങൾ