ಬಬಲ್ ಸಾರ್ಟ್

 

Bubble sort

Static visualization of bubble sort
Class	Sorting algorithm
Data structure	Array
Worst-case performance	$O(n^2)$ comparisons, $O(n^2)$ swaps
Best-case performance	$O(n)$ comparisons, $O(1)$ swaps
Average performance	$O(n^2)$ comparisons, $O(n^2)$ swaps
Worst-case space complexity	$O(n)$ total, $O(1)$ auxiliary

ಬಬಲ್ ಸಾರ್ಟ್ ಅಥವಾ ಬಬಲ್ ವಿಂಗಡಣೆಯನ್ನು ಕೆಲವೊಮ್ಮೆ ಸಿಂಕಿಂಗ್ ಸಾರ್ಟ್ ಅಥವಾ ಸಿಂಕಿಂಗ್ ವಿಂಗಡಣೆ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ. ಇದು ಒಂದು ಸರಳ ವಿಂಗಡಣೆ ಅಲ್ಗಾರಿದಮ್ ಆಗಿದ್ದು, ಇನ್‌ಪುಟ್ ಪಟ್ಟಿ (ಅರ್ರೇ)ಯ ಪ್ರತಿಯೊಂದು ಎಲಿಮೆಂಟ್ ಗಳನ್ನು ಪದೇ ಪದೇ ಗಮನಿಸುತ್ತ, ಪ್ರಸ್ತುತ ಎಲಿಮೆಂಟನ್ನು ಅದರ ನಂತರದ ಎಲಿಮೆಂಟಿನೊಂದಿಗೆ ಹೋಲಿಸುತ್ತದೆ, ಅಗತ್ಯವಿದ್ದರೆ ಅವುಗಳ ವ್ಯಾಲ್ಯೂಗಳನ್ನು ವಿನಿಮಯ (ಎಕ್ಸ್ ಚೇಂಜ್) ಮಾಡಿಕೊಳ್ಳುತ್ತದೆ . ಪಟ್ಟಿಯಲ್ಲಿ ಎಲ್ಲಾ ಎಲಿಮೆಂಟ್ ಗಳನ್ನು ಒಂದು ಬಾರಿ ಹೋಲಿಸುವುದನ್ನು ಒಂದು ಪಾಸ್ ಕರೆಯಲಾಗುತ್ತದೆ. ಹೀಗೆ ಇದನ್ನು ಪ್ರತಿ ಸಮಯದಲ್ಲಿ ಯಾವುದೇ ಸ್ವಾಪ್‌ಗಳನ್ನು ನಿರ್ವಹಿಸುವವರೆಗೆ ಪಟ್ಟಿಯ ಮೂಲಕ ಈ ಪಾಸ್‌ಗಳನ್ನು ಪುನರಾವರ್ತಿಸಲಾಗುತ್ತದೆ, ಅಂದರೆ ಪಟ್ಟಿಯನ್ನು ಸಂಪೂರ್ಣವಾಗಿ ವಿಂಗಡಿಸಲಾಗಿದೆ. ಹೋಲಿಕೆಯ ರೀತಿಯ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಪಟ್ಟಿಯ ಮೇಲ್ಭಾಗದವರೆಗೆ ದೊಡ್ಡ ಅಂಶಗಳು "ಬಬಲ್" ಮಾಡುವ ವಿಧಾನಕ್ಕೆ ಹೆಸರಿಸಲಾಗಿದೆ.

ಈ ಸರಳ ಅಲ್ಗಾರಿದಮ್ ನೈಜ ಪ್ರಪಂಚ(ರಿಯಲ್ ವರ್ಲ್ಡ್) ದ ಬಳಕೆಯಲ್ಲಿ ಕಳಪೆಯಾಗಿ ಕಾರ್ಯನಿರ್ವಹಿಸುತ್ತದೆ ಮತ್ತು ಪ್ರಾಥಮಿಕವಾಗಿ ಶೈಕ್ಷಣಿಕ ಸಾಧನವಾಗಿ ಬಳಸಲಾಗುತ್ತದೆ. ಕ್ವಿಕ್‌ಸಾರ್ಟ್, ಟಿಮ್‌ಸಾರ್ಟ್ ಅಥವಾ ಮರ್ಜ್ ಸಾರ್ಟ್ ನಂತಹ ಹೆಚ್ಚು ಪರಿಣಾಮಕಾರಿ ಕ್ರಮಾವಳಿಗಳನ್ನು ಪೈಥಾನ್ ಮತ್ತು ಜಾವಾದಂತಹ ಜನಪ್ರಿಯ ಪ್ರೋಗ್ರಾಮಿಂಗ್ ಭಾಷೆಗಳಲ್ಲಿ ನಿರ್ಮಿಸಲಾದ ವಿಂಗಡಣೆ ಲೈಬ್ರರಿಗಳಿಂದ ಬಳಸಲಾಗುತ್ತದೆ.

ವಿಶ್ಲೇಷಣೆ

ಬಬಲ್ ವಿಂಗಡಣೆಯ ಉದಾಹರಣೆ. ಪಟ್ಟಿಯ ಪ್ರಾರಂಭದಿಂದ ಪ್ರಾರಂಭಿಸಿ, ಪ್ರತಿ ಪಕ್ಕದ ಜೋಡಿಯನ್ನು ಹೋಲಿಕೆ ಮಾಡಿ, ಸರಿಯಾದ ಕ್ರಮದಲ್ಲಿ ಇಲ್ಲದಿದ್ದರೆ ಅವರ ಸ್ಥಾನವನ್ನು ಬದಲಾಯಿಸುತ್ತದೆ. (ಎರಡನೆಯದು ಹಿಂದಿನದಕ್ಕಿಂತ ಚಿಕ್ಕದಾಗಿದೆ). ಪ್ರತಿ ಪುನರಾವರ್ತನೆಯ ನಂತರ, ಹೋಲಿಸಲು ಯಾವುದೇ ಹೆಚ್ಚಿನ ಎಲಿಮೆಂಟ್ ಗಳು ಉಳಿಯುವವರೆಗೆ ಒಂದು ಕಡಿಮೆ ಎಲಿಮೆಂಟನ್ನು (ಕೊನೆಯದು) ಹೋಲಿಸುವ ಅಗತ್ಯವಿದೆ.

ಪ್ರದರ್ಶನ

ಬಬಲ್ ಸಾರ್ಟ್ ಕೆಟ್ಟ ಸಂಕೀರ್ಣತೆ ಮತ್ತು ಸರಾಸರಿ ಸಂಕೀರ್ಣತೆಯನ್ನು ಹೊಂದಿದೆ $O(n^2)$, ಎಲ್ಲಿ $n$ ವಿಂಗಡಿಸಲಾದ ಐಟಂಗಳ ಸಂಖ್ಯೆ. ಹೆಚ್ಚಿನ ಪ್ರಾಯೋಗಿಕ ವಿಂಗಡಣೆ ಕ್ರಮಾವಳಿಗಳು ಗಣನೀಯವಾಗಿ ಉತ್ತಮವಾದ ಕೆಟ್ಟ ಸಂಕೀರ್ಣತೆ ಅಥವಾ ಸರಾಸರಿ ಸಂಕೀರ್ಣತೆಯನ್ನು ಹೊಂದಿರುತ್ತವೆ. $O(n\log n)$ . ಇತರೆ ಕೂಡ $O(n^2)$ ವಿಂಗಡಣೆಯ ಕ್ರಮಾವಳಿಗಳು, ಉದಾಹರಣೆಗೆ ಅಳವಡಿಕೆ ವಿಂಗಡಣೆ, ಸಾಮಾನ್ಯವಾಗಿ ಬಬಲ್ ವಿಂಗಡಣೆಗಿಂತ ವೇಗವಾಗಿ ಚಲಿಸುತ್ತವೆ ಮತ್ತು ಹೆಚ್ಚು ಸಂಕೀರ್ಣವಾಗಿಲ್ಲ. ಈ ಕಾರಣಕ್ಕಾಗಿ, ಬಬಲ್ ವಿಂಗಡಣೆಯನ್ನು ಆಚರಣೆಯಲ್ಲಿ ವಿರಳವಾಗಿ ಬಳಸಲಾಗುತ್ತದೆ.

ಅಳವಡಿಕೆ (ಇನ್ಸರ್ಷನ್) ಸಾರ್ಟಿನಂತರ, ಬಬಲ್ ಸಾರ್ಟ್ ಹೊಂದಿಕೊಳ್ಳಬಲ್ಲದು, ಇದು ಕ್ವಿಕ್‌ಸಾರ್ಟ್‌ನಂತಹ ಅಲ್ಗಾರಿದಮ್‌ಗಳಿಗೆ ಹೋಲಿಸಿದರೆ ಹೆಚ್ಚು ಪ್ರಯೋಜನವನ್ನು ನೀಡುತ್ತದೆ. ಇದರರ್ಥ ಪಟ್ಟಿಯು ಈಗಾಗಲೇ ಹೆಚ್ಚಾಗಿ ವಿಂಗಡಿಸಲಾದ ಸಂದರ್ಭಗಳಲ್ಲಿ (ಕಡಿಮೆ ಸಂಖ್ಯೆಯ ವಿಲೋಮಗಳನ್ನು ಹೊಂದಿರುವ) ಇದು ಆ ಅಲ್ಗಾರಿದಮ್‌ಗಳನ್ನು ಮೀರಿಸುತ್ತದೆ, ಇದು ಕೆಟ್ಟ ಸರಾಸರಿ-ಕೇಸ್ ಸಮಯದ ಸಂಕೀರ್ಣತೆಯನ್ನು ಹೊಂದಿದೆ ಎಂಬ ಅಂಶದ ಹೊರತಾಗಿಯೂ. ಉದಾಹರಣೆಗೆ, ಬಬಲ್ ವಿಂಗಡಣೆಯಾಗಿದೆ $O(n)$ ಈಗಾಗಲೇ ವಿಂಗಡಿಸಲಾದ ಪಟ್ಟಿಯಲ್ಲಿ, ಕ್ವಿಕ್‌ಸಾರ್ಟ್ ಇನ್ನೂ ಸಂಪೂರ್ಣ ಕಾರ್ಯನಿರ್ವಹಿಸುತ್ತದೆ $O(n\log n)$ ವಿಂಗಡಿಸುವ ಪ್ರಕ್ರಿಯೆ.

ಯಾವುದೇ ಸಾರ್ಟಿಂಗ್ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ವಿಂಗಡಿಸದೇ ನೀಡಿದ ಇನ್ಪುಟನ್ನು ಬಳಸಬಹುದು ಮತ್ತದರ ಕಾಂಪ್ಲಕ್ಸಿಟಿಯು $O(n)$ ಆಗಿರುತ್ತದೆ. ಅಲ್ಗಾರಿದಮ್ ರನ್ ಆಗುವ ಮೊದಲು ಪಟ್ಟಿಯನ್ನು ಪರಿಶೀಲಿಸುವ ಮೂಲಕ ಪೂರ್ವನಿರ್ಧರಿತ ಪಟ್ಟಿಯಲ್ಲಿ, ಬಹುತೇಕ ವಿಂಗಡಿಸಲಾದ ಪಟ್ಟಿಗಳಲ್ಲಿ ಸುಧಾರಿತ ಕಾರ್ಯಕ್ಷಮತೆಯನ್ನು ಪುನರಾವರ್ತಿಸಲು ಕಷ್ಟವಾಗುತ್ತದೆ.

ಮೊಲಗಳು ಮತ್ತು ಆಮೆಗಳು

ಸಾರ್ಟ್ ಮಾಡುವ ಸಮಯದಲ್ಲಿ ಅಂಶ (ಎಲಿಮೆಂಟ್)ಗಳು ಚಲಿಸಬೇಕಾದ ದೂರ ಮತ್ತು ದಿಕ್ಕು ಬಬಲ್ ವಿಂಗಡಣೆಯ ಕಾರ್ಯಕ್ಷಮತೆಯನ್ನು ನಿರ್ಧರಿಸುತ್ತದೆ ಏಕೆಂದರೆ ಅಂಶಗಳು ವಿಭಿನ್ನ ವೇಗದಲ್ಲಿ ವಿಭಿನ್ನ ದಿಕ್ಕುಗಳಲ್ಲಿ ಚಲಿಸುತ್ತವೆ. ಪಟ್ಟಿಯ ಅಂತ್ಯಕ್ಕೆ ಚಲಿಸಬೇಕಾದ ಎಲಿಮೆಂಟ್ ತ್ವರಿತವಾಗಿ ಚಲಿಸಬಹುದು .ಏಕೆಂದರೆ ಅದು ಸತತ ಸ್ವಾಪ್‌ಗಳಲ್ಲಿ ಭಾಗವಹಿಸಬಹುದು. ಉದಾಹರಣೆಗೆ, ಪಟ್ಟಿಯಲ್ಲಿರುವ ದೊಡ್ಡ ಅಂಶ (ಎಲಿಮೆಂಟ್)ವು ಪ್ರತಿ ಸ್ವಾಪ್ ಅನ್ನು ಗೆಲ್ಲುತ್ತದೆ, ಆದ್ದರಿಂದ ಅದು ಪ್ರಾರಂಭದ ಸಮೀಪದಲ್ಲಿ ಪ್ರಾರಂಭವಾದರೂ ಮೊದಲ ಪಾಸ್‌ನಲ್ಲಿ ಅದರ ವಿಂಗಡಿಸಲಾದ ಸ್ಥಾನಕ್ಕೆ ಚಲಿಸುತ್ತದೆ. ಮತ್ತೊಂದೆಡೆ, ಪಟ್ಟಿಯ ಪ್ರಾರಂಭದ ಕಡೆಗೆ ಚಲಿಸಬೇಕಾದ ಅಂಶವು ಪ್ರತಿ ಪಾಸ್‌ಗೆ ಒಂದು ಹೆಜ್ಜೆಗಿಂತ ವೇಗವಾಗಿ ಚಲಿಸಲು ಸಾಧ್ಯವಿಲ್ಲ, ಆದ್ದರಿಂದ ಅಂಶಗಳು ಪ್ರಾರಂಭದ ಕಡೆಗೆ ಬಹಳ ನಿಧಾನವಾಗಿ ಚಲಿಸುತ್ತವೆ. ಚಿಕ್ಕ ಅಂಶವು ಪಟ್ಟಿಯ ಕೊನೆಯಲ್ಲಿದ್ದರೆ, ಅದು ತೆಗೆದುಕೊಳ್ಳುತ್ತದೆ $n-1$ ಅದನ್ನು ಆರಂಭಕ್ಕೆ ಸರಿಸಲು ಹಾದುಹೋಗುತ್ತದೆ. ಇದು ಈಸೋಪನ ನೀತಿಕಥೆಯಾದ ಆಮೆ ಮತ್ತು ಮೊಲದಲ್ಲಿನ ಪಾತ್ರಗಳ ನಂತರ ಈ ರೀತಿಯ ಅಂಶಗಳನ್ನು ಕ್ರಮವಾಗಿ ಮೊಲಗಳು ಮತ್ತು ಆಮೆಗಳು ಎಂದು ಹೆಸರಿಸಲು ಕಾರಣವಾಯಿತು.

ಬಬಲ್ ಸಾರ್ಟಿನ ವೇಗವನ್ನು ಸುಧಾರಿಸಲು ವಿವಿಧ ಪ್ರಯತ್ನಗಳನ್ನು ಮಾಡಲಾಗಿದೆ. ಕಾಕ್ಟೈಲ್ ವಿಂಗಡಣೆಯು ಎರಡು ದಿಕ್ಕಿನ ಬಬಲ್ ವಿಂಗಡಣೆಯಾಗಿದ್ದು, ಅದು ಆರಂಭದಿಂದ ಕೊನೆಯವರೆಗೆ ಹೋಗುತ್ತದೆ ಮತ್ತು ನಂತರ ಸ್ವತಃ ಹಿಮ್ಮುಖವಾಗುತ್ತದೆ ಅಂದರೆ ಅಂತ್ಯದಿಂದ ಆರಂಭಕ್ಕೆ ಹೋಗುತ್ತದೆ. ಇದು ಆಮೆಗಳನ್ನು ತಕ್ಕಮಟ್ಟಿಗೆ ಸರಿಸಬಲ್ಲದು, ಆದರೆ ಅದು ಉಳಿಸಿಕೊಳ್ಳುತ್ತದೆ $O(n^2)$ ಕೆಟ್ಟ ಸಂದರ್ಭದಲ್ಲಿ ಸಂಕೀರ್ಣತೆ. ಕೊಂಬ್ ವಿಂಗಡಣೆಯು ದೊಡ್ಡ ಅಂತರದಿಂದ ಬೇರ್ಪಟ್ಟ ಅಂಶಗಳನ್ನು ಹೋಲಿಸುತ್ತದೆ ಮತ್ತು ಪಟ್ಟಿಯನ್ನು ಸುಗಮಗೊಳಿಸಲು ಚಿಕ್ಕ ಮತ್ತು ಚಿಕ್ಕ ಅಂತರಗಳಿಗೆ ಮುಂದುವರಿಯುವ ಮೊದಲು ಆಮೆಗಳನ್ನು ತ್ವರಿತವಾಗಿ ಚಲಿಸಬಹುದು. ಇದರ ಸರಾಸರಿ ವೇಗವನ್ನು ಕ್ವಿಕ್‌ಸಾರ್ಟ್‌ನಂತಹ ವೇಗದ ಅಲ್ಗಾರಿದಮ್‌ಗಳಿಗೆ ಹೋಲಿಸಬಹುದು.

ಹಂತ ಹಂತದ ಉದಾಹರಣೆ

"5 1 4 2 8" ಸಂಖ್ಯೆಗಳ ಒಂದು ಶ್ರೇಣಿಯನ್ನು ತೆಗೆದುಕೊಳ್ಳಿ ಮತ್ತು ಬಬಲ್ ವಿಂಗಡಣೆಯನ್ನು ಬಳಸಿಕೊಂಡು ಕಡಿಮೆ ಸಂಖ್ಯೆಯಿಂದ ದೊಡ್ಡ ಸಂಖ್ಯೆಗೆ ಶ್ರೇಣಿಯನ್ನು ವಿಂಗಡಿಸಿ. ಪ್ರತಿ ಹಂತದಲ್ಲಿ, ದಪ್ಪ ಅಕ್ಷರದಲ್ಲಿ ಬರೆಯಲಾದ ಎಲಿಮೆಂಟ್ ಗಳನ್ನು ಹೋಲಿಸಲಾಗುತ್ತದೆ. ಮೂರು ಪಾಸುಗಳ ಅಗತ್ಯವಿದೆ;

ಮೊದಲ ಪಾಸ್

( 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 ), ಈಗ, ಈ ಎಲಿಮೆಂಟ್ ಗಳು ಈಗಾಗಲೇ ಕ್ರಮದಲ್ಲಿರುವುದರಿಂದ (8 > 5), ನಿಜವಿದ್ದರೂ ಅಲ್ಗಾರಿದಮ್ ಅವುಗಳನ್ನು ಬದಲಾಯಿಸುವುದಿಲ್ಲ.

ಎರಡನೇ ಪಾಸ್

( 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 )

ಅರ್ರೇಯನ್ನು ಈಗಾಗಲೇ ವಿಂಗಡಿಸಲಾಗಿದೆ, ಆದರೆ ಅಲ್ಗಾರಿದಮ್ ಪೂರ್ಣಗೊಂಡಿದೆಯೇ ಎಂದು ತಿಳಿದಿಲ್ಲ. ಅಲ್ಗಾರಿದಮ್ ಅರ್ರೇಯನ್ನು ವಿಂಗಡಿಸಲಾಗಿದೆ ಎಂದು ತಿಳಿಯಲು ಯಾವುದೇ ಸ್ವಾಪ್ ಇಲ್ಲದ ಒಂದು ಹೆಚ್ಚುವರಿ ಸಂಪೂರ್ಣ ಪಾಸ್ ಅಗತ್ಯವಿದೆ.

ಮೂರನೇ ಪಾಸ್

( 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 )

ಬಬಲ್ ವಿಂಗಡಣೆಯನ್ನು ಉತ್ತಮಗೊಳಿಸುವುದು

n -th ಪಾಸ್ ನಲ್ಲಿ n -th ದೊಡ್ಡ ಎಲಿಮೆಂಟನ್ನು ಕಂಡುಕೊಳ್ಳುತ್ತದೆ ಮತ್ತು ಅದನ್ನು ಅದರ ಅಂತಿಮ ಸ್ಥಳದಲ್ಲಿ ಇರಿಸುತ್ತದೆ ಎಂಬುದನ್ನು ಗಮನಿಸುವುದರ ಮೂಲಕ ಬಬಲ್ ವಿಂಗಡಣೆಯ ಅಲ್ಗಾರಿದಮನ್ನು ಆಪ್ಟಿಮೈಸ್ ಮಾಡಬಹುದು. ಆದ್ದರಿಂದ, ಒಳಗಿನ ಲೂಪ್ n -ನೇ ಬಾರಿಗೆ ಚಾಲನೆಯಲ್ಲಿರುವಾಗ ಕೊನೆಯ n - 1 ಐಟಂಗಳನ್ನು ನೋಡುವುದನ್ನು ತಪ್ಪಿಸಬಹುದು:

ಸಾಮಾನ್ಯವಾಗಿ, ಒಂದೇ ಪಾಸ್‌ನಲ್ಲಿ ಒಂದಕ್ಕಿಂತ ಹೆಚ್ಚು ಎಲಿಮೆಂಟುಗಳನ್ನು ಅವುಗಳ ಅಂತಿಮ ಸ್ಥಾನದಲ್ಲಿ ಇರಿಸಲಾಗುತ್ತದೆ. ನಿರ್ದಿಷ್ಟವಾಗಿ ಹೇಳುವುದಾದರೆ, ಪ್ರತಿ ಪಾಸ್ ನಂತರ, ಕೊನೆಯ ಸ್ವಾಪ್ ನಂತರದ ಎಲ್ಲಾ ಎಲಿಮೆಂಟ್ ಗಳನ್ನು ವಿಂಗಡಿಸಲಾಗುತ್ತದೆ ಮತ್ತು ಮತ್ತೆ ಪರಿಶೀಲಿಸುವ ಅಗತ್ಯವಿರುವುದಿಲ್ಲ. ಇದು ಅನೇಕ ಎಲಿಮೆಂಟ್ ಗಳನ್ನು ಬಿಟ್ಟುಬಿಡಲು ಅನುವು ಮಾಡಿಕೊಡುತ್ತದೆ. ಇದರ ಪರಿಣಾಮವಾಗಿ ಹೋಲಿಕೆಯ ಎಣಿಕೆಯಲ್ಲಿ 50% ಸುಧಾರಣೆ (ಸ್ವಾಪ್ ಎಣಿಕೆಗಳಲ್ಲಿ ಯಾವುದೇ ಸುಧಾರಣೆ ಇಲ್ಲದಿದ್ದರೂ), ಮತ್ತು ಹೊಸ ಕೋಡ್ "ಸ್ವಾಪ್ಡ್" ವೇರಿಯೇಬಲ್ ಅನ್ನು ಒಳಗೊಳ್ಳುವ ಕಾರಣ ಕಡಿಮೆ ಸಂಕೀರ್ಣತೆಯನ್ನು ಸೇರಿಸುತ್ತದೆ:

ಇದನ್ನು ಸೂಡೊಕೋಡ್‌ನಲ್ಲಿ ಸಾಧಿಸಲು, ಈ ಕೆಳಗಿನವುಗಳನ್ನು ಬರೆಯಬಹುದು:

ಪರ್ಯಾಯ ಮಾರ್ಪಾಡುಗಳಾದ ಕಾಕ್‌ಟೈಲ್ ಶೇಕರ್ ಸಾರ್ಟ್, ಬಬಲ್ ಸಾರ್ಟಿನ ಕಾರ್ಯಕ್ಷಮತೆಯನ್ನು ಸುಧಾರಿಸಲು ಪ್ರಯತ್ನಿಸುತ್ತದೆ ಮತ್ತು ಪಕ್ಕದ ಎಲಿಮೆಂಟ್ ಗಳನ್ನು ಪದೇ ಪದೇ ಹೋಲಿಸುವ ಮತ್ತು ವಿನಿಮಯ ಮಾಡಿಕೊಳ್ಳುವ ಒಂದೇ ಆಲೋಚನೆಯನ್ನು ಇರಿಸುತ್ತದೆ.

ಬಳಸಿ

ಬಬಲ್ ವಿಂಗಡಣೆ. ಪಟ್ಟಿಯನ್ನು ಕಾರ್ಟೀಸಿಯನ್ ನಿರ್ದೇಶಾಂಕ ವ್ಯವಸ್ಥೆಯಲ್ಲಿ ರೂಪಿಸಲಾಗಿದೆ, ಪ್ರತಿ ಪಾಯಿಂಟ್ ( x, y ) ಮೌಲ್ಯವು y ಅನ್ನು ಇಂಡೆಕ್ಸ್ x ನಲ್ಲಿ ಸಂಗ್ರಹಿಸಿದೆ ಎಂದು ಸೂಚಿಸುತ್ತದೆ. ನಂತರ ಪಟ್ಟಿಯನ್ನು ಪ್ರತಿ ಪಿಕ್ಸೆಲ್‌ನ ಮೌಲ್ಯದ ಪ್ರಕಾರ ಬಬಲ್ ವಿಂಗಡಣೆಯಿಂದ ವಿಂಗಡಿಸಲಾಗುತ್ತದೆ. ದೊಡ್ಡ ತುದಿಯನ್ನು ಮೊದಲು ವಿಂಗಡಿಸಲಾಗುತ್ತದೆ ಎಂಬುದನ್ನು ಗಮನಿಸಿ, ಚಿಕ್ಕ ಎಲಿಮೆಂಟುಗಳು ಅವುಗಳ ಸರಿಯಾದ ಸ್ಥಾನಗಳಿಗೆ ಚಲಿಸಲು ಹೆಚ್ಚು ಸಮಯ ತೆಗೆದುಕೊಳ್ಳುತ್ತದೆ.

ಬಬಲ್ ವಿಂಗಡಣೆಯು ಅರ್ಥಮಾಡಿಕೊಳ್ಳಲು ಮತ್ತು ಕಾರ್ಯಗತಗೊಳಿಸಲು ಸರಳವಾದ ಸಾರ್ಟಿಂಗ್ ಅಲ್ಗಾರಿದಂಗಳಲ್ಲಿ ಒಂದಾಗಿದ್ದರೂ, ಅದರ O ( n ² ) ಕಾಂಪ್ಲೆಕ್ಸಿಟಿ ಎಂದರೆ ಅದರ ದಕ್ಷತೆಯು ಕಡಿಮೆ ಸಂಖ್ಯೆಯ ಎಲಿಮೆಂಟುಗಳ ಪಟ್ಟಿಗಳಲ್ಲಿ ನಾಟಕೀಯವಾಗಿ ಕಡಿಮೆಯಾಗುತ್ತದೆ. ಸರಳ O ( n ² ) ವಿಂಗಡಣೆ ಅಲ್ಗಾರಿದಮ್‌ಗಳ ನಡುವೆಯೂ ಸಹ, ಅಳವಡಿಕೆಯ ರೀತಿಯ ಕ್ರಮಾವಳಿಗಳು ಸಾಮಾನ್ಯವಾಗಿ ಗಣನೀಯವಾಗಿ ಹೆಚ್ಚು ಪರಿಣಾಮಕಾರಿಯಾಗಿರುತ್ತವೆ.

ಅದರ ಸರಳತೆಯಿಂದಾಗಿ, ಕಂಪ್ಯೂಟರ್ ಸೈನ್ಸ್ ಮೊದಲ ಸಲ ಕಲಿಯುವ ವಿದ್ಯಾರ್ಥಿಗಳಿಗೆ ಅಲ್ಗಾರಿದಮ್ ಅಥವಾ ವಿಂಗಡಣೆ ಅಲ್ಗಾರಿದಮ್‌ನ ಪರಿಕಲ್ಪನೆಯನ್ನು ಪರಿಚಯಿಸಲು ಬಬಲ್ ವಿಂಗಡಣೆಯನ್ನು ಹೆಚ್ಚಾಗಿ ಬಳಸಲಾಗುತ್ತದೆ. ಆದಾಗ್ಯೂ, ಓವೆನ್ ಅಸ್ಟ್ರಾಚನ್‌ನಂತಹ ಕೆಲವು ಸಂಶೋಧಕರು ಬಬಲ್ ಪ್ರಕಾರವನ್ನು ಮತ್ತು ಕಂಪ್ಯೂಟರ್ ವಿಜ್ಞಾನ ಶಿಕ್ಷಣದಲ್ಲಿ ಅದರ ಮುಂದುವರಿದ ಜನಪ್ರಿಯತೆಯನ್ನು ತಿರಸ್ಕರಿಸಲು ಹೆಚ್ಚಿನ ಪ್ರಯತ್ನಗಳನ್ನು ಮಾಡಿದ್ದಾರೆ, ಇದನ್ನು ಇನ್ನು ಮುಂದೆ ಕಲಿಸಬಾರದು ಎಂದು ಶಿಫಾರಸು ಮಾಡುತ್ತಾರೆ.

ಬೊಗೊಸಾರ್ಟ್ ಅನ್ನು ಪ್ರಸಿದ್ಧವಾಗಿ " ಆರ್ಕಿಟಿಪಿಕಲ್ [sic] ವಿಕೃತವಾಗಿ ಭೀಕರವಾದ ಅಲ್ಗಾರಿದಮ್" ಎಂದು ಕರೆಯುವ ಪರಿಭಾಷೆ ಫೈಲ್, ಬಬಲ್ ಪ್ರಕಾರವನ್ನು "ಜೆನೆರಿಕ್ ಬ್ಯಾಡ್ ಅಲ್ಗಾರಿದಮ್" ಎಂದೂ ಕರೆಯುತ್ತದೆ. ಡೊನಾಲ್ಡ್ ಕ್ನೂತ್ ಅವರು, ದಿ ಆರ್ಟ್ ಆಫ್ ಕಂಪ್ಯೂಟರ್ ಪ್ರೋಗ್ರಾಮಿಂಗ್‌ನಲ್ಲಿ, "ಆಕರ್ಷಕ ಹೆಸರು ಮತ್ತು ಇದು ಕೆಲವು ಆಸಕ್ತಿದಾಯಕ ಸೈದ್ಧಾಂತಿಕ ಸಮಸ್ಯೆಗಳಿಗೆ ಕಾರಣವಾಗುತ್ತದೆ ಎಂಬ ಅಂಶವನ್ನು ಹೊರತುಪಡಿಸಿ ಬಬಲ್ ಪ್ರಕಾರವು ಶಿಫಾರಸು ಮಾಡಲು ಏನೂ ಇಲ್ಲ ಎಂದು ತೋರುತ್ತದೆ" ಎಂದು ತೀರ್ಮಾನಿಸಿದರು, ಅವುಗಳಲ್ಲಿ ಕೆಲವನ್ನು ಅವರು ಚರ್ಚಿಸಿದರು.

ಕೆಟ್ಟ ಸಂದರ್ಭದಲ್ಲಿ ಇನ್ಸರ್ಷನ್ ವಿಂಗಡಣೆಗೆ ಚಾಲನೆಯಲ್ಲಿರುವ ಸಮಯದಲ್ಲಿ ಬಬಲ್ ವಿಂಗಡಣೆಯು ಅಸಮಪಾರ್ಶ್ವವಾಗಿ ಸಮನಾಗಿರುತ್ತದೆ, ಆದರೆ ಎರಡು ಅಲ್ಗಾರಿದಮ್‌ಗಳು ಅಗತ್ಯವಾದ ಸ್ವಾಪ್‌ಗಳ ಸಂಖ್ಯೆಯಲ್ಲಿ ಬಹಳ ಭಿನ್ನವಾಗಿರುತ್ತವೆ. ಅಸ್ಟ್ರಾಚಾನ್‌ನಂತಹ ಪ್ರಾಯೋಗಿಕ ಫಲಿತಾಂಶಗಳು ಯಾದೃಚ್ಛಿಕ ಪಟ್ಟಿಗಳಲ್ಲಿಯೂ ಸಹ ಒಳಸೇರಿಸುವಿಕೆಯ ವಿಂಗಡಣೆಯು ಗಣನೀಯವಾಗಿ ಉತ್ತಮವಾಗಿ ಕಾರ್ಯನಿರ್ವಹಿಸುತ್ತದೆ ಎಂದು ತೋರಿಸಿದೆ. ಈ ಕಾರಣಗಳಿಗಾಗಿ ಅನೇಕ ಆಧುನಿಕ ಅಲ್ಗಾರಿದಮ್ ಪಠ್ಯಪುಸ್ತಕಗಳು ಅಳವಡಿಕೆಯ ವಿಂಗಡಣೆಯ ಪರವಾಗಿ ಬಬಲ್ ಸಾರ್ಟ್ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಬಳಸುವುದನ್ನು ತಪ್ಪಿಸುತ್ತವೆ.

ಬಬಲ್ ಸಾರ್ಟ್ ಆಧುನಿಕ CPU ನ ಯಂತ್ರಾಂಶದೊಂದಿಗೆ ಕಳಪೆಯಾಗಿ ಸಂವಹಿಸುತ್ತದೆ. ಇದು ಇನ್ಸರ್ಷನ್ ವಿಂಗಡಣೆಯಂತೆ ಕನಿಷ್ಠ ಎರಡು ಪಟ್ಟು ಹೆಚ್ಚು ಬರಹಗಳನ್ನು ಉತ್ಪಾದಿಸುತ್ತದೆ. ಎರಡು ಪಟ್ಟು ಹೆಚ್ಚು ಕ್ಯಾಶ್ ಮಿಸ್‌ಗಳು ಮತ್ತು ಅಸಮಪಾರ್ಶ್ವವಾಗಿ ಹೆಚ್ಚಿನ ಶಾಖೆಯ ತಪ್ಪುಗ್ರಹಿಕೆಗಳನ್ನು ಉತ್ಪಾದಿಸುತ್ತದೆ .ಟೆಂಪ್ಲೇಟು:Fact ಜಾವಾದಲ್ಲಿ ಅಸ್ಟ್ರಾಚಾನ್ ಸ್ಟ್ರಿಂಗ್‌ಗಳ ವಿಂಗಡಣೆಯ ಪ್ರಯೋಗಗಳು ಬಬಲ್ ಸಾರ್ಟ್ ಒಂದು ಇನ್ಸರ್ಷನ್ ಸಾರ್ಟಿನಂತೆ ಸರಿಸುಮಾರು ಐದನೇ ಒಂದು ಭಾಗದಷ್ಟು ವೇಗವಾಗಿರುತ್ತದೆ ಮತ್ತು ಆಯ್ಕೆಯ ವಿಂಗಡಣೆಯಂತೆ 70% ವೇಗವಾಗಿರುತ್ತದೆ.

ಕಂಪ್ಯೂಟರ್ ಗ್ರಾಫಿಕ್ಸ್‌ನಲ್ಲಿ ಬಬಲ್ ಸಾರ್ಟು ಬಹುಪಾಲು-ವಿಂಗಡಿಸಿದ ಅರ್ರೇಗಳಲ್ಲಿ (ಕೇವಲ ಎರಡು ಎಲಿಮೆಂಟುಗಳ ಸ್ವಾಪ್‌ನಂತಹ) ಸಣ್ಣ ದೋಷವನ್ನು ಪತ್ತೆಹಚ್ಚುವ ಸಾಮರ್ಥ್ಯಕ್ಕಾಗಿ ಜನಪ್ರಿಯವಾಗಿದೆ. ಅದನ್ನು ಕೇವಲ ರೇಖೀಯ ಸಂಕೀರ್ಣತೆಯೊಂದಿಗೆ (2 n ) ಸರಿಪಡಿಸುತ್ತದೆ. ಉದಾಹರಣೆಗೆ, ಇದನ್ನು ಬಹುಭುಜಾಕೃತಿ ಭರ್ತಿ ಮಾಡುವ ಅಲ್ಗಾರಿದಮ್‌ನಲ್ಲಿ ಬಳಸಲಾಗುತ್ತದೆ, ಅಲ್ಲಿ ಬೌಂಡಿಂಗ್ ಲೈನ್‌ಗಳನ್ನು ನಿರ್ದಿಷ್ಟ ಸ್ಕ್ಯಾನ್ ಲೈನ್‌ನಲ್ಲಿ ( x (ಎಕ್ಸ್)ಅಕ್ಷಕ್ಕೆ ಸಮಾನಾಂತರವಾಗಿರುವ ರೇಖೆ) ಅವುಗಳ x (ಎಕ್ಸ್) ನಿರ್ದೇಶಾಂಕದಿಂದ ವಿಂಗಡಿಸಲಾಗುತ್ತದೆ ಮತ್ತು y(ವೈ) ಅನ್ನು ಹೆಚ್ಚಿಸುವುದರೊಂದಿಗೆ ಅವುಗಳ ಕ್ರಮ ಬದಲಾವಣೆಗಳು (ಎರಡು ಎಲಿಮೆಂಟುಗಳನ್ನು ಬದಲಾಯಿಸಲಾಗುತ್ತದೆ) ಎರಡು ಸಾಲುಗಳ ಛೇದಕಗಳು. ಬಬಲ್ ವಿಂಗಡಣೆಯು ಇನ್ಸಶರ್ಷನ್ ವಿಂಗಡಣೆಯಂತೆ ಸ್ಥಿರ ವಿಂಗಡಣೆ ಅಲ್ಗಾರಿದಮ್ ಆಗಿದೆ.

ಮಾರ್ಪಾಡುಗಳು

• ಬೆಸ-ಸಮ ವಿಂಗಡಣೆಯು ಸಂದೇಶ ರವಾನಿಸುವ ವ್ಯವಸ್ಥೆಗಳಿಗೆ ಬಬಲ್ ವಿಂಗಡಣೆಯ ಸಮಾನಾಂತರ ಆವೃತ್ತಿಯಾಗಿದೆ.
• ಪಾಸ್‌ಗಳು ಎಡದಿಂದ ಬಲಕ್ಕೆ ಬದಲಾಗಿ ಬಲದಿಂದ ಎಡಕ್ಕೆ ಆಗಿರಬಹುದು. ವಿಂಗಡಿಸದ ಐಟಂಗಳನ್ನು ಕೊನೆಯಲ್ಲಿ ಸೇರಿಸಲಾದ ಪಟ್ಟಿಗಳಿಗೆ ಇದು ಹೆಚ್ಚು ಪರಿಣಾಮಕಾರಿಯಾಗಿರುತ್ತದೆ.
• ಕಾಕ್ಟೈಲ್ ಶೇಕರ್ ವಿಂಗಡಣೆಯು ಎಡಕ್ಕೆ ಮತ್ತು ಬಲಕ್ಕೆ ಪರ್ಯಾಯವಾಗಿ ಹಾದುಹೋಗುತ್ತದೆ.
• ಇದು ಬಬಲ್ ಸಾರ್ಟ್ ತಪ್ಪಾದ ಆವೃತ್ತಿಯಂತೆ ಕಂಡುಬರುವ ವಿಂಗಡಣೆ ಅಲ್ಗಾರಿದಮ್ ಎಂದು ನಾನು ನಂಬಲು ಸಾಧ್ಯವಿಲ್ಲ, ಆದರೆ ಅಳವಡಿಕೆಯ ವಿಂಗಡಣೆಗೆ ಹೆಚ್ಚು ಹೋಲುವ ರೀತಿಯಲ್ಲಿ ಕಾರ್ಯನಿರ್ವಹಿಸುತ್ತದೆ ಎಂದು ಔಪಚಾರಿಕವಾಗಿ ಸಾಬೀತುಪಡಿಸಬಹುದು.

ಹೆಸರಿನ ಮೇಲೆ ಚರ್ಚೆ

ಬಬಲ್ ವಿಂಗಡಣೆಯನ್ನು ಸಾಂದರ್ಭಿಕವಾಗಿ "ಸಿಂಕಿಂಗ್ ಸಾರ್ಟಿಂಗ್" ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ.

ಉದಾಹರಣೆಗೆ, ಡೊನಾಲ್ಡ್ ಕ್ನೂತ್ ಅವರು ಬಯಸಿದ ಸ್ಥಳದಲ್ಲಿ ಅಥವಾ ಕಡೆಗೆ ಮೌಲ್ಯ (ವ್ಯಾಲ್ಯೂ)ಗಳನ್ನು ಸೇರಿಸುವುದರ ಬಗ್ಗೆ ವಿವರಿಸುತ್ತಾರೆ "[ಮೌಲ್ಯ ] ಅದರ ಸರಿಯಾದ ಮಟ್ಟಕ್ಕೆ ನೆಲೆಗೊಳ್ಳಲು ಅವಕಾಶ ನೀಡುತ್ತದೆ", ಮತ್ತು "ಈ ವಿಂಗಡಣೆಯ ವಿಧಾನವನ್ನು ಕೆಲವೊಮ್ಮೆ ಸಿಫ್ಟಿಂಗ್ ಅಥವಾ ಸಿಂಕಿಂಗ್ ತಂತ್ರ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ.

ಎರಡು ವಿಭಿನ್ನ ಆದರೆ ಸಮಾನವಾಗಿ ಮಾನ್ಯವಾದ ದೃಷ್ಟಿಕೋನಗಳಿಂದ ಈ ಅಲ್ಗಾರಿದಮನ್ನಯು ಪರಿಗಣಿಸುವ ಸುಲಭತೆಯಿಂದ ಈ ಚರ್ಚೆಯು ಶಾಶ್ವತವಾಗಿದೆ:

1. ದೊಡ್ಡ ಮೌಲ್ಯ(ವ್ಯಾಲ್ಯೂ)ಗಳನ್ನು ಭಾರವೆಂದು ಪರಿಗಣಿಸಬಹುದು ಮತ್ತು ಆದ್ದರಿಂದ ಅವುಗಳು ಹಂತಹಂತವಾಗಿ ಪಟ್ಟಿಯ ಕೆಳಭಾಗಕ್ಕೆ ಮುಳುಗುವುದನ್ನು ಕಾಣಬಹುದು.
2. ಚಿಕ್ಕ ಚಿಕ್ಕ ಮೌಲ್ಯ(ವ್ಯಾಲ್ಯೂ)ಗಳನ್ನು ಹಗುರವೆಂದು ಪರಿಗಣಿಸಬಹುದು ಮತ್ತು ಆದ್ದರಿಂದ ಅವುಗಳು ಪಟ್ಟಿಯ ಮೇಲ್ಭಾಗದವರೆಗೆ ಕ್ರಮೇಣವಾಗಿ ಬಬಲ್ ಆಗುವುದನ್ನು ಕಾಣಬಹುದು.

ಜನಪ್ರಿಯ ಸಂಸ್ಕೃತಿಯಲ್ಲಿ

2007 ರಲ್ಲಿ, ಗೂಗಲ್ ಮಾಜಿ ಸಿಇಒ ಎರಿಕ್ ಸ್ಮಿತ್ ಅವರು ಆಗಿನ ಅಮೆರಿಕಾದ ಅಧ್ಯಕ್ಷೀಯ ಅಭ್ಯರ್ಥಿಯಾಗಿದ್ದ ಬರಾಕ್ ಒಬಾಮಾ ಅವರನ್ನು ಸಂದರ್ಶನವೊಂದರಲ್ಲಿ ಒಂದು ಮಿಲಿಯನ್ ಪೂರ್ಣಾಂಕಗಳನ್ನು ವಿಂಗಡಿಸಲು ಉತ್ತಮ ಮಾರ್ಗವನ್ನು ಕೇಳಿದರು ; ಒಬಾಮಾ ಒಂದು ಕ್ಷಣ ವಿರಾಮಗೊಳಿ ಉತ್ತರಿಸಿದರು: "ಬಬಲ್ ಸಾರ್ಟ್ ತಪ್ಪು ದಾರಿ ಎಂದು ನಾನು ಭಾವಿಸುತ್ತೇನೆ."

ಉಲ್ಲೇಖಗಳು

• ಥಾಮಸ್ ಎಚ್. ಕಾರ್ಮೆನ್, ಚಾರ್ಲ್ಸ್ ಇ. ಲೀಸರ್ಸನ್, ರೊನಾಲ್ಡ್ ಎಲ್. ರಿವೆಸ್ಟ್ ಮತ್ತು ಕ್ಲಿಫರ್ಡ್ ಸ್ಟೈನ್ . ಅಲ್ಗಾರಿದಮ್‌ಗಳ ಪರಿಚಯ, ಎರಡನೇ ಆವೃತ್ತಿ. MIT ಪ್ರೆಸ್ ಮತ್ತು ಮೆಕ್‌ಗ್ರಾ-ಹಿಲ್, 2001. ISBN 0-262-03293-7 . ಸಮಸ್ಯೆ 2-2, ಪುಟ.40.
• ಬ್ರಾಂಚ್ ಪ್ರಿಡಿಕ್ಷನ್ ಮತ್ತು ಕ್ಯಾಷ್‌ಗಳ ಉಪಸ್ಥಿತಿಯಲ್ಲಿ ವಿಂಗಡಿಸುವುದು
• ಎಲ್ಲಿಸ್ ಹೊರೊವಿಟ್ಜ್, ಸರ್ತಾಜ್ ಸಾಹ್ನಿ ಮತ್ತು ಸುಸಾನ್ ಆಂಡರ್ಸನ್-ಫ್ರೀಡ್ ಅವರಿಂದ ಡೇಟಾ ರಚನೆಗಳ ಮೂಲಭೂತ ಅಂಶಗಳು 
• ಓವನ್ ಅಸ್ಟ್ರಾಚನ್ . ಬಬಲ್ ವಿಂಗಡಣೆ: ಪುರಾತತ್ವ ಅಲ್ಗಾರಿದಮಿಕ್ ವಿಶ್ಲೇಷಣೆ
• Spasic PhD, Srdic MSc, ಓಪನ್ ಸೋರ್ಸ್, 1987 ರಿಂದ ಕಂಪ್ಯೂಟರ್ ಇಂಟಿಗ್ರೇಟೆಡ್ ಮ್ಯಾನುಫ್ಯಾಕ್ಚರಿಂಗ್.

ಬಾಹ್ಯ ಕೊಂಡಿಗಳು

• ಟೆಂಪ್ಲೇಟು:Cite web – graphical demonstration
• ಟೆಂಪ್ಲೇಟು:Cite web (Java applet animation)
• OEIS sequence A008302 (Table (statistics) of the number of permutations of [n] that need k pair-swaps during the sorting)