ബബിള് സോര്ട്ട്
വിക്കിപീഡിയ, ഒരു സ്വതന്ത്ര വിജ്ഞാനകോശം.
 സംഖ്യകളുടെ ഒരു ലിസ്റ്റില് ബബിള് സോര്ട്ട് നടക്കുമ്പോള് സംഭവിക്കുന്നത്. |
|
| കുടുംബം | സോര്ട്ടിങ്ങ് അല്ഗൊരിതം |
|---|---|
| ഡാറ്റാ സ്ട്രക്ചര് | അറേ |
| മോശം സമയസങ്കീര്ണ്ണത | O(N2) |
| നല്ല സമയസങ്കീര്ണ്ണത | O(N) |
| ശരാശരി സമയസങ്കീര്ണ്ണത | O(N2) |
| മോശം മെമ്മറി സങ്കീര്ണ്ണത | ആകെ O(N), ലിസ്റ്റിനു പുറമെ O(1) |
| Optimal | അല്ല |
ഒരു ലിസ്റ്റിലെ സംഖ്യകളെയും മറ്റും ക്രമത്തിലാക്കാന് ഉപയോഗിക്കുന്ന ഒരു സോര്ട്ടിങ്ങ് അല്ഗൊരിതമാണ് ബബിള് സോര്ട്ട്. എളുപ്പമുള്ളതും, എന്നാല് ഗണനപരമായ സങ്കീര്ണ്ണത കൂടിയതിനാല് വളരെ സമയമെടുക്കുന്നതുമായ ഒരു സോര്ട്ടിങ്ങ് അല്ഗൊരിതമാണിത്. ഇതിന്റെ സമയസങ്കീര്ണ്ണത O(N2) ഉം മെമ്മറി സങ്കീര്ണ്ണത O(N) ഉമാണ്. എന്നാല് ഒരു in-place അല്ഗൊരിതമാണ് ഇത് എന്നതിനാല് ലിസ്റ്റിന് പുറമെ O(1) മെമ്മറി മാത്രമേ ഇതിന് ആവശ്യമുള്ളൂ.
ക്രമത്തിലല്ലാതെയുള്ള അടുത്തടുത്തുള്ള സംഖ്യകളെ പരസ്പരം മാറ്റുന്നതു വഴിയാണ് ബബിള് സോര്ട്ട് സംഖ്യകളെ ക്രമീകരിക്കുന്നത്. ക്രമീകരിക്കപ്പെട്ട സംഖ്യകള് കുമിളകളെപ്പോലെ ലിസ്റ്റിന്റെ ഒരു ഭാഗത്തേക്കു പോകുന്നു എന്നതിനാലാണ് ഈ അല്ഗൊരിതത്തിന് പേര് ലഭിച്ചത്. സംഖ്യകളെ താരതമ്യം ചെയ്യുക വഴിയാണ് സോര്ട്ടിങ്ങ് നടത്തുന്നത് എന്നതിനാല് ഇത് ഒരു താരതമ്യ സോര്ട്ട് ആണ്.
ഉള്ളടക്കം |
[തിരുത്തുക] അല്ഗൊരിതം
(1,2) മുതല് (N-1,N) വരെയുള്ള സംഖ്യാദ്വയങ്ങളെ പരിഗണിക്കുക. ഒരു ദ്വയം ക്രമത്തിലല്ലെങ്കില് ആ രണ്ട് സംഖ്യകളെ പരസ്പരം മാറ്റുക. ഇങ്ങനെ ചെയ്യുന്നതു വഴി ഏറ്റവും വലിയ സംഖ്യ ലിസ്റ്റിന്റെ ഏറ്റവും അവസാനമായി മാറും. ഇതിനുശേഷം ഈ പ്രക്രിയ ലിസ്റ്റിലെ ആദ്യത്തെ N-1, N-2....2 സംഖ്യകള്ക്ക് തുടര്ന്നാല് ലിസ്റ്റിലെ സംഖ്യകളെല്ലാം ക്രമത്തിലാകും
[തിരുത്തുക] സ്യൂഡോകോഡ്
N സംഖ്യകളുള്ള array എന്ന ലിസ്റ്റ് ബബിള് സോര്ട്ട് വഴി ക്രമത്തിലാക്കാന്:
1. end <- N 2. flag <- ശരി 3. end = 1 അഥവാ flag = തെറ്റ് ആണെങ്കില് നിര്ത്തുക 4. flag <- തെറ്റ് 5. i <- 1 മുതല് end-1 വരെ വിലകളുപയോഗിച്ച് പടി 6 ചെയ്യുക 6. array[i] array[i+1] നെക്കാള് വലുതാണെങ്കില് അവയെ പരസ്പരം മാറ്റുകയും flag <- ശരി ആക്കുകയും ചെയ്യുക 7. end <- end - 1 8. പടി 3 ലേക്ക് പോകുക
[തിരുത്തുക] വിശകലനം
സംഖ്യകള് തികച്ചും വിപരീതക്രമത്തിലാകുമ്പോള് 
തവണ പടി 6 ചെയ്യേണ്ടി വരുന്നു എന്നതിനാല് ബബിള് സോര്ട്ടിന്റെ മോശം സമയസങ്കീര്ണ്ണത O(N2) ആണ്. സംഖ്യകള് തികച്ചും ക്രമത്തിലാകുമ്പോള് ഇത് N − 1 തവണ മാത്രം ചെയ്താല് മതി. അതിനാല് നല്ല സമയസങ്കീര്ണ്ണത O(N) ആണ്. ശരാശരി സമയസങ്കീര്ണ്ണത O(N2) തന്നെ. ശരാശരി, മോശം സമയസങ്കീര്ണ്ണതകള് O(NlogN) ആയുള്ള സോര്ട്ടിങ്ങ് അല്ഗൊരിതങ്ങള് ഉണ്ട്. O(N2) സമയസങ്കീര്ണ്ണത ഉള്ള ഇന്സര്ഷന് സോര്ട്ട് മുതലായ അല്ഗൊരിതങ്ങളും ബബിള് സോര്ട്ടിനെക്കാള് വേഗത്തില് സോര്ട്ടിങ്ങ് നടത്തുന്നു എന്നതിനാല് വലിയ ലിസ്റ്റുകള് സോര്ട്ട് ചെയ്യാന് ബബിള് സോര്ട്ട് ഉപയോഗിക്കാറില്ല.
[തിരുത്തുക] പുറത്തേക്കുള്ള കണ്ണികള്
- 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.
