ಸದಸ್ಯ:Bright Antony/WEP 2018-19 dec

ಬಬಲ್ ವಿಂಗಡನೆ

bubble sorting

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

ಫಾರ್ಮುಲಾ ವಿವರಣೆ

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

ಅನುಕೂಲಗಳು/ಅನಾನುಕೂಲಗಳು

method of bubble sorting

ಅಲ್ಗಾರಿದಮ್ ಸರಳವಾಗಿದ್ದರೂ ಸಹ, ಅಳವಡಿಕೆ ವಿಧಕ್ಕೆ ಹೋಲಿಸಿದರೆ ಇದು ತುಂಬಾ ನಿಧಾನ ಮತ್ತು ಅಪ್ರಾಯೋಗಿಕವಾಗಿದೆ. ಇನ್ಪುಟ್ ಹೆಚ್ಚಾಗಿ ವಿಂಗಡಿಸಲಾದ ಕ್ರಮದಲ್ಲಿ ಕೆಲವು ಔಟ್-ಆಫ್-ಆರ್ಡರ್ ಅಂಶಗಳೊಂದಿಗೆ ಸ್ಥಾನದಲ್ಲಿದ್ದರೆ ಬಬಲ್ ವಿಂಗಡನೆಯು ಪ್ರಾಯೋಗಿಕವಾಗಿರಬಹುದು. ಅಳವಡಿಕೆಯ ರೀತಿಯಂತಹ ಇತರ O(n^ 2) ವಿಂಗಡಣೆಯ ಕ್ರಮಾವಳಿಗಳು ಸಾಮಾನ್ಯವಾಗಿ ಬಬಲ್ ವಿಂಗಡಣೆಗಿಂತ ವೇಗವಾಗಿ ರನ್ ಆಗುತ್ತವೆ ಮತ್ತು ಹೆಚ್ಚು ಸಂಕೀರ್ಣವಾಗಿರುವುದಿಲ್ಲ. ಆದ್ದರಿಂದ, ಬಬಲ್ ವಿಂಗಡಣೆಯು ಪ್ರಾಯೋಗಿಕ ವಿಂಗಡಣಾ ಕ್ರಮಾವಳಿ ಅಲ್ಲ. ಗುಳ್ಳೆ ವಿಂಗಡನೆಯು ಇತರ ಅಲ್ಗಾರಿದಮ್ಗಳ ಮೇಲೆ, ಕ್ವಿಕ್ಸ್ಟೋರ್ನಲ್ಲೂ ಕೂಡಾ ಇದೆ, ಆದರೆ ಒಳಸೇರಿಸುವಿಕೆಯ ರೀತಿಯಲ್ಲ, ಪಟ್ಟಿಗಳನ್ನು ಪರಿಣಾಮಕಾರಿಯಾಗಿ ವರ್ಗೀಕರಿಸಲಾಗಿದೆ ಎಂದು ಕಂಡುಹಿಡಿಯುವ ಸಾಮರ್ಥ್ಯ ಅಲ್ಗಾರಿದಮ್ಗೆ ನಿರ್ಮಿಸಲ್ಪಡುತ್ತದೆ.

ಬಬಲ್ ಸಾರ್ಟಿಂಗ್ ವಿಧಾನ

ಪಟ್ಟಿಯ ಅಂತ್ಯದ ಕಡೆಗೆ ಚಲಿಸಬೇಕಾದ ಅಂಶವು ವೇಗವಾಗಿ ಚಲಿಸಬಹುದು ಏಕೆಂದರೆ ಅದು ಸತತ ವಿನಿಮಯಗಳಲ್ಲಿ ಭಾಗವಹಿಸಬಹುದು. ಉದಾಹರಣೆಗೆ, ಪಟ್ಟಿಯಲ್ಲಿರುವ ಅತಿ ದೊಡ್ಡ ಅಂಶವು ಪ್ರತಿ ಸ್ವಾಪ್ ಅನ್ನು ಗೆಲ್ಲುತ್ತದೆ, ಆದ್ದರಿಂದ ಇದು ಆರಂಭದ ಬಳಿ ಪ್ರಾರಂಭಿಸಿದರೂ ಸಹ ಮೊದಲ ಪಾಸ್ನಲ್ಲಿ ಅದರ ವಿಂಗಡಿಸಲಾದ ಸ್ಥಾನಕ್ಕೆ ಚಲಿಸುತ್ತದೆ. ಮತ್ತೊಂದೆಡೆ, ಪಟ್ಟಿಯ ಆರಂಭದ ಕಡೆಗೆ ಚಲಿಸಬೇಕಾದ ಅಂಶವು ಒಂದು ಹಂತಕ್ಕೆ ಒಂದು ಹೆಜ್ಜೆಗಿಂತ ವೇಗವಾಗಿ ಚಲಿಸಲು ಸಾಧ್ಯವಿಲ್ಲ, ಆದ್ದರಿಂದ ಅಂಶಗಳು ಆರಂಭಕ್ಕೆ ಬಹಳ ನಿಧಾನವಾಗಿ ಚಲಿಸುತ್ತವೆ. ಚಿಕ್ಕ ಅಂಶವು ಪಟ್ಟಿಯ ಅಂತ್ಯದಲ್ಲಿದ್ದರೆ, ಅದು ಆರಂಭದಲ್ಲಿ ಅದನ್ನು ಚಲಿಸಲು n-1 ಪಾಸ್ಗಳನ್ನು ತೆಗೆದುಕೊಳ್ಳುತ್ತದೆ. ಈ ರೀತಿಯ ಅಂಶಗಳಿಗೆ ಅನುಗುಣವಾಗಿ ಮೊಲಗಳು ಮತ್ತು ಆಮೆಗಳು ಎಂಬ ಹೆಸರನ್ನು ನೀಡಲಾಗಿದೆ, ಈಸೋಪನ ಆಮೆ ಮತ್ತು ದಿ ಹೇರ್ ಕಥೆಯ ಪಾತ್ರಗಳ ನಂತರ. ಬಬಲ್ ರೀತಿಯ ವೇಗವನ್ನು ಸುಧಾರಿಸಲು ಆಮೆಗಳನ್ನು ತೊಡೆದುಹಾಕಲು ಹಲವಾರು ಪ್ರಯತ್ನಗಳನ್ನು ಮಾಡಲಾಗಿದೆ. ಕಾಕ್ಟೇಲ್ ರೀತಿಯು ಎರಡು-ದಿಕ್ಕಿನ ಬಬಲ್ ವಿಂಗಡಣೆಯಾಗಿದ್ದು, ಅದು ಪ್ರಾರಂಭದಿಂದ ಕೊನೆಯವರೆಗೆ ಹೋಗುತ್ತದೆ ಮತ್ತು ನಂತರ ಸ್ವತಃ ಹಿಮ್ಮುಖವಾಗುವುದು, ಆರಂಭಕ್ಕೆ ಕೊನೆಗೊಳ್ಳುತ್ತದೆ. ಇದು ಆಮೆಗಳನ್ನು ಸಾಕಷ್ಟು ಚೆನ್ನಾಗಿ ಚಲಿಸಬಹುದು, ಆದರೆ ಇದು O (n2) ಕೆಟ್ಟ-ಸಂಕೀರ್ಣತೆಯನ್ನು ಉಳಿಸಿಕೊಂಡಿದೆ. ಬಾಚಣಿಗೆ ರೀತಿಯ ದೊಡ್ಡ ಅಂತರಗಳಿಂದ ಬೇರ್ಪಟ್ಟ ಅಂಶಗಳನ್ನು ಹೋಲಿಸುತ್ತದೆ ಮತ್ತು ಸಣ್ಣ ಮತ್ತು ಸಣ್ಣ ಅಂತರಗಳಿಗೆ ಮುಂದುವರಿಯುವುದಕ್ಕೆ ಮುಂಚಿತವಾಗಿ ಆಮೆಗಳನ್ನು ಶೀಘ್ರವಾಗಿ ಚಲಿಸಬಹುದು. ಇದರ ಸರಾಸರಿ ವೇಗವು ತ್ವರಿತಗತಿಯ ಕ್ರಮಾವಳಿಗಳಿಗೆ ಹೋಲಿಸಬಹುದು. ಬಬಲ್ ವಿಂಗಡಣೆಯನ್ನು ಅರ್ಥಮಾಡಿಕೊಳ್ಳಲು ಮತ್ತು ಕಾರ್ಯಗತಗೊಳಿಸಲು ಸರಳ ವಿಂಗಡಣೆಯ ಕ್ರಮಾವಳಿಗಳ ಪೈಕಿ ಒಂದಾಗಿದೆಯಾದರೂ, ಅದರ O(n^2) ಸಂಕೀರ್ಣತೆ ಅದರ ಸಾಮರ್ಥ್ಯವು ಸಣ್ಣ ಸಂಖ್ಯೆಯ ಅಂಶಗಳಿಗಿಂತ ಹೆಚ್ಚು ಪಟ್ಟಿಗಳಲ್ಲಿ ನಾಟಕೀಯವಾಗಿ ಕಡಿಮೆಯಾಗುತ್ತದೆ ಎಂದರ್ಥ. ಸರಳ O(n^2) ಸಾರ್ಟಿಂಗ್ ಅಲ್ಗಾರಿದಮ್ಗಳ ನಡುವೆ, ಅಳವಡಿಕೆ ರೀತಿಯ ಕ್ರಮಾವಳಿಗಳು ಸಾಮಾನ್ಯವಾಗಿ ಹೆಚ್ಚು ಪರಿಣಾಮಕಾರಿಯಾಗಿವೆ. ಅದರ ಸರಳತೆಯ ಕಾರಣದಿಂದಾಗಿ, ಪರಿವರ್ತನಾ ಕಂಪ್ಯೂಟರ್ ವಿಜ್ಞಾನ ವಿದ್ಯಾರ್ಥಿಗಳಿಗೆ ಅಲ್ಗಾರಿದಮ್ ಅಥವಾ ವಿಂಗಡಣೆಯ ಅಲ್ಗಾರಿದಮ್ ಎಂಬ ಪರಿಕಲ್ಪನೆಯನ್ನು ಪರಿಚಯಿಸಲು ಬಬಲ್ ರೀತಿಯನ್ನು ಬಳಸಲಾಗುತ್ತದೆ. ಆದಾಗ್ಯೂ, ಓವನ್ ಆಸ್ಟ್ರಾಚನ್ ನಂತಹ ಕೆಲವು ಸಂಶೋಧಕರು ಬಬಲ್ ರೀತಿಯನ್ನು ಅನೂರ್ಜಿತಗೊಳಿಸಲು ಮತ್ತು ಗಣಕ ವಿಜ್ಞಾನ ಶಿಕ್ಷಣದಲ್ಲಿ ಅದರ ಮುಂದುವರಿದ ಜನಪ್ರಿಯತೆಯನ್ನು ಹೆಚ್ಚಿಸಲು ಹೋಗಿದ್ದಾರೆ, ಅದನ್ನು ಇನ್ನು ಮುಂದೆ ಕಲಿಸಲಾಗುವುದಿಲ್ಲ ಎಂದು ಶಿಫಾರಸು ಮಾಡಿದ್ದಾರೆ. ಬೋಗೊಸೋರ್ಟನ್ನು "ಪ್ರತಿಮಾರೂಪದ [sic] ವಿಪರ್ಯಾಸವಾಗಿ ಅಸಹನೀಯ ಅಲ್ಗಾರಿದಮ್" ಎಂದು ಕರೆಯಲಾಗುವ ಜಾರ್ಗನ್ ಫೈಲ್, ಬಬಲ್ ರೀತಿಯ "ಜೆನೆರಿಕ್ ಕೆಟ್ಟ ಅಲ್ಗಾರಿದಮ್" ಎಂದು ಸಹ ಕರೆಯುತ್ತದೆ. ದಿ ಆರ್ಟ್ ಆಫ್ ಕಂಪ್ಯೂಟರ್ ಪ್ರೋಗ್ರಾಮಿಂಗ್ನಲ್ಲಿರುವ ಡೊನಾಲ್ಡ್ ನುತ್ ಅವರು "ಕುಖ್ಯಾತ ಹೆಸರನ್ನು ಹೊರತುಪಡಿಸಿ, ಇದು ಕೆಲವು ಆಸಕ್ತಿಕರ ಸೈದ್ಧಾಂತಿಕ ಸಮಸ್ಯೆಗಳಿಗೆ ದಾರಿಯಾಗುತ್ತದೆ ಎಂಬ ಅಂಶವನ್ನು ಹೊರತುಪಡಿಸಿ, ಗುಳ್ಳೆ ರೀತಿಯು ಅದನ್ನು ಶಿಫಾರಸು ಮಾಡಲು ಏನೂ ಇಲ್ಲವೆಂದು ತೋರುತ್ತದೆ" ಎಂದು ತೀರ್ಮಾನಿಸಿದರು, ಅದರಲ್ಲಿ ಕೆಲವರು ನಂತರ ಚರ್ಚಿಸುತ್ತಿದ್ದಾರೆ.

ಬಬಲ್ ಸಾರ್ಟಿಂಗ್ ಬಗ್ಗೆ ಇನ್ನಷ್ಟು

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