Flashsort
ಫ್ಲ್ಯಾಶ್ ಸಾರ್ಟ್ ಎಂಬುದು ಏಕರೂಪವಾಗಿ ವಿತರಿಸಲಾದ ದತ್ತಾಂಶ ಸೆಟ್ಗಳಿಗೆ ರೇಖೀಯ ಕಂಪ್ಯೂಟೇಶನಲ್ ಸಂಕೀರ್ಣತೆ ಮತ್ತು ತುಲನಾತ್ಮಕವಾಗಿ ಕಡಿಮೆ ಹೆಚ್ಚುವರಿ ಮೆಮೊರಿ ಅಗತ್ಯವನ್ನು ತೋರಿಸುವ ವಿತರಣಾ ವಿಂಗಡಣಾ ಅಲ್ಗಾರಿದಮ್ ಆಗಿದೆ. ಮೂಲ ಕೃತಿಯನ್ನು 1998ರಲ್ಲಿ ಕಾರ್ಲ್-ಡೈಟ್ರಿಚ್ ನ್ಯೂಬರ್ಟ್ ಪ್ರಕಟಿಸಿದರು. ಫ್ಲ್ಯಾಶ್ ಸಾರ್ಟ್ ಎಂಬ ಪರಿಕಲ್ಪನೆಯು ಹಿಸ್ಟೋಗ್ರಾಮ್ ಸಾರ್ಟ್ನ ಸಮರ್ಥವಾದ ಸ್ಥಳ ಅನುಷ್ಠಾನವಾಗಿದೆ, ಇದು ಸ್ವತಃ ಒಂದು ರೀತಿಯ ಬಕೆಟ್ ಸಾರ್ಟ್ ಆಗಿದೆ. ಇದು ಪ್ರತಿಯೊಂದು ಇನ್ಪುಟ್ ಅಂಶಗಳನ್ನು ಬಕೆಟ್ಗಳಲ್ಲಿ ಒಂದಕ್ಕೆ ನಿಯೋಜಿಸುತ್ತದೆ, ಬಕೆಟ್ಗಳನ್ನು ಸರಿಯಾದ ಕ್ರಮದಲ್ಲಿ ಇರಿಸಲು ಇನ್ಪುಟ್ ಅನ್ನು ಪರಿಣಾಮಕಾರಿಯಾಗಿ ಮರುಹೊಂದಿಸುತ್ತದೆ, ನಂತರ ಪ್ರತಿ ಬಕೆಟ್ ಅನ್ನು ವಿಂಗಡಿಸುತ್ತದೆ. ಮೂಲ ಅಲ್ಗಾರಿದಮ್ ಇನ್ಪುಟ್ ಶ್ರೇಣಿಯನ್ನು ಈ ಕೆಳಗಿನಂತೆ ವಿಂಗಡಿಸುತ್ತದೆಃ ಇನ್ಪುಟ್ ಅಥವಾ ಆದ್ಯತೆಯ ಜ್ಞಾನದ ಮೇಲೆ ಮೊದಲ ಪಾಸ್ ಅನ್ನು ಬಳಸಿಕೊಂಡು, ಕನಿಷ್ಠ ಮತ್ತು ಗರಿಷ್ಠ ವಿಂಗಡಣಾ ಕೀಲಿಗಳನ್ನು ಹುಡುಕಿ. ಶ್ರೇಣಿಯನ್ನು ರೇಖೀಯವಾಗಿ ಬಕೆಟ್ಗಳಾಗಿ ವಿಭಜಿಸಿ. ಪ್ರತಿ ಬಕೆಟ್ನಲ್ಲಿ ಬೀಳುವ ಅಂಶಗಳ ಸಂಖ್ಯೆಯನ್ನು ಎಣಿಸುತ್ತಾ, ಇನ್ಪುಟ್ ಮೇಲೆ ಒಂದು ಪಾಸ್ ಮಾಡಿ. (ನ್ಯೂಬರ್ಟ್ ಬಕೆಟ್ಗಳನ್ನು "ವರ್ಗಗಳು" ಮತ್ತು ಅವುಗಳ ಬಕೆಟ್ಗಳಿಗೆ ಅಂಶಗಳನ್ನು ನಿಯೋಜಿಸುವುದನ್ನು "ವರ್ಗೀಕರಣ" ಎಂದು ಕರೆಯುತ್ತಾರೆ.) ಪ್ರತಿ ಬಕೆಟ್ನಲ್ಲಿನ ಅಂಶಗಳ ಎಣಿಕೆಗಳನ್ನು ಪೂರ್ವಪ್ರತ್ಯಯ ಮೊತ್ತಕ್ಕೆ ಪರಿವರ್ತಿಸಿ, ಅಲ್ಲಿ ಬಕೆಟ್ನಲ್ಲಿನ ಅಂಶಗಳ ಸಂಖ್ಯೆ ಅಥವಾ ಕಡಿಮೆ ಇರುತ್ತದೆ. (ಮತ್ತು.) ಇನ್ಪುಟ್ ಅನ್ನು ಮರುಹೊಂದಿಸಿ, ಆದ್ದರಿಂದ ಪ್ರತಿ ಬಕೆಟ್ನ ಎಲ್ಲಾ ಅಂಶಗಳನ್ನು ಅಲ್ಲಿ ಇರಿಸಲಾಗಿರುವ ಸ್ಥಾನಗಳಲ್ಲಿ ಸಂಗ್ರಹಿಸಲಾಗುತ್ತದೆ. ಪ್ರತಿ ಬಕೆಟ್ ಅನ್ನು ಇನ್ಸರ್ಷನ್ ಸಾರ್ಟ್ ಬಳಸಿ ವಿಂಗಡಿಸಿ. ಹಂತಗಳು 1-3 ಮತ್ತು 6 ಯಾವುದೇ ಬಕೆಟ್ ಪ್ರಕಾರಕ್ಕೆ ಸಾಮಾನ್ಯವಾಗಿದೆ, ಮತ್ತು ಬಕೆಟ್ ಪ್ರಕಾರಗಳಿಗೆ ಸಾಮಾನ್ಯ ತಂತ್ರಗಳನ್ನು ಬಳಸಿಕೊಂಡು ಸುಧಾರಿಸಬಹುದು. ನಿರ್ದಿಷ್ಟವಾಗಿ ಹೇಳುವುದಾದರೆ, ಬಕೆಟ್ಗಳು ಸರಿಸುಮಾರು ಸಮಾನ ಗಾತ್ರದಲ್ಲಿರಬೇಕು (ಪ್ರತಿಯೊಂದು ಅಂಶಗಳೂ), ಆದರ್ಶವೆಂದರೆ ಕ್ವಾಂಟೈಲ್ಗಳಾಗಿ ವಿಂಗಡಿಸುವುದು. ಮೂಲ ಅಲ್ಗಾರಿದಮ್ ಒಂದು ರೇಖೀಯ ಅಂತರ್ವೇಶನ ವಿಧವಾಗಿದ್ದರೂ, ಇನ್ಪುಟ್ ವಿತರಣೆಯು ಏಕರೂಪವಲ್ಲದ್ದು ಎಂದು ತಿಳಿದಿದ್ದರೆ, ರೇಖೀಯವಲ್ಲದ ವಿಭಾಗವು ಈ ಆದರ್ಶವನ್ನು ಹೆಚ್ಚು ನಿಕಟವಾಗಿ ಅಂದಾಜು ಮಾಡುತ್ತದೆ. ಅಂತೆಯೇ, ಅಂತಿಮ ವಿಂಗಡಣೆ ಪುನರಾವರ್ತಿತ ಫ್ಲಾಶ್ ವಿಂಗಡಣೆ ಸೇರಿದಂತೆ ಹಲವಾರು ತಂತ್ರಗಳನ್ನು ಬಳಸಬಹುದು. ಫ್ಲಾಶ್ ಸಾರ್ಟ್ ಅನ್ನು ಪ್ರತ್ಯೇಕಿಸುವ ಹಂತವೆಂದರೆ ಹಂತ 5: ಹೆಚ್ಚುವರಿ ಮೆಮೊರಿಯ ಪದಗಳನ್ನು ಮಾತ್ರ ಬಳಸಿಕೊಂಡು ಪ್ರತಿ ಬಕೆಟ್ನ ಅಂಶಗಳನ್ನು ಸರಿಯಾದ ಸಾಪೇಕ್ಷ ಕ್ರಮದಲ್ಲಿ ಒಟ್ಟುಗೂಡಿಸಲು ಪರಿಣಾಮಕಾರಿ ಇನ್-ಪ್ಲೇಸ್ ಅಲ್ಗಾರಿದಮ್. ಮೆಮೊರಿ ದಕ್ಷ ಅನುಷ್ಠಾನ ಫ್ಲ್ಯಾಶ್ ಸಾರ್ಟ್ ಮರುಜೋಡಣೆ ಹಂತವು ಚಕ್ರಗಳಲ್ಲಿ ಕಾರ್ಯನಿರ್ವಹಿಸುತ್ತದೆ. ಅಂಶಗಳು "ವರ್ಗೀಕರಿಸದ" ಎಂದು ಪ್ರಾರಂಭವಾಗುತ್ತವೆ, ನಂತರ ಅವುಗಳನ್ನು ಸರಿಯಾದ ಬಕೆಟ್ಗೆ ಸ್ಥಳಾಂತರಿಸಲಾಗುತ್ತದೆ ಮತ್ತು "ವರ್ಗೀಕರಿಸಲಾಗಿದೆ" ಎಂದು ಪರಿಗಣಿಸಲಾಗುತ್ತದೆ. ಮೂಲ ಕಾರ್ಯವಿಧಾನವೆಂದರೆ ವರ್ಗೀಕರಿಸದ ಅಂಶವನ್ನು ಆಯ್ಕೆ ಮಾಡುವುದು, ಅದರ ಸರಿಯಾದ ಬಕೆಟ್ ಅನ್ನು ಕಂಡುಹಿಡಿಯುವುದು, ಅದನ್ನು ಅಲ್ಲಿ ವರ್ಗೀಕರಿಸದ ಅಂಶದೊಂದಿಗೆ ವಿನಿಮಯ ಮಾಡಿಕೊಳ್ಳುವುದು (ಇದು ಅಸ್ತಿತ್ವದಲ್ಲಿರಬೇಕು, ಏಕೆಂದರೆ ನಾವು ಪ್ರತಿ ಬಕೆಟ್ನ ಗಾತ್ರವನ್ನು ಸಮಯಕ್ಕಿಂತ ಮುಂಚಿತವಾಗಿ ಲೆಕ್ಕ ಹಾಕಿದ್ದೇವೆ), ಅದನ್ನು ವರ್ಗೀಕರಿಸಿದಂತೆ ಗುರುತಿಸಿ, ನಂತರ ಕೇವಲ-ವಿನಿಮಯಗೊಂಡ ವರ್ಗೀಕರಿಸದ ಅಂಶದೊಂದಿಗೆ ಪುನರಾವರ್ತಿಸಿ. ಅಂತಿಮವಾಗಿ, ಅಂಶವು ತನ್ನೊಂದಿಗೆ ವಿನಿಮಯಗೊಳ್ಳುತ್ತದೆ ಮತ್ತು ಚಕ್ರವು ಕೊನೆಗೊಳ್ಳುತ್ತದೆ. ಪ್ರತಿ ಬಕೆಟ್ಗೆ ಎರಡು (ಪದ-ಗಾತ್ರದ) ಅಸ್ಥಿರಗಳನ್ನು ಬಳಸಿಕೊಂಡು ವಿವರಗಳನ್ನು ಅರ್ಥಮಾಡಿಕೊಳ್ಳುವುದು ಸುಲಭ. ಬುದ್ಧಿವಂತ ಭಾಗವೆಂದರೆ ಆ ಅಸ್ಥಿರಗಳಲ್ಲಿ ಒಂದನ್ನು ತೆಗೆದುಹಾಕುವುದು, ಇದು ಎರಡು ಪಟ್ಟು ಹೆಚ್ಚು ಬಕೆಟ್ಗಳನ್ನು ಬಳಸಲು ಅನುವು ಮಾಡಿಕೊಡುತ್ತದೆ ಮತ್ತು ಆದ್ದರಿಂದ ಅಂತಿಮ ವಿಂಗಡಣೆಗಾಗಿ ಅರ್ಧದಷ್ಟು ಸಮಯವನ್ನು ಕಳೆಯುತ್ತದೆ. ಪ್ರತಿ ಬಕೆಟ್ಗೆ ಎರಡು ಅಸ್ಥಿರಗಳೊಂದಿಗೆ ಇದನ್ನು ಅರ್ಥಮಾಡಿಕೊಳ್ಳಲು, ಹೆಚ್ಚುವರಿ ಪದಗಳ ಎರಡು ಸರಣಿಗಳಿವೆ ಎಂದು ಭಾವಿಸಿಃ ಬಕೆಟ್ (ಮತ್ತು) ನ (ಸ್ಥಿರ) ಮೇಲಿನ ಮಿತಿಯಾಗಿದೆ, ಆದರೆ ಬಕೆಟ್ಗೆ (ಚಲಿಸಬಲ್ಲ) ಸೂಚ್ಯಂಕವಾಗಿದೆ, ಆದ್ದರಿಂದ. ಪ್ರತಿ ಬಕೆಟ್ ಅನ್ನು ವರ್ಗೀಕರಿಸದ ಪೂರ್ವಪ್ರತ್ಯಯವಾಗಿ (ಅವುಗಳ ಗುರಿ ಬಕೆಟ್ಗಳಿಗೆ ಇನ್ನೂ ಸ್ಥಳಾಂತರಿಸಬೇಕಾಗಿಲ್ಲ) ಮತ್ತು ವರ್ಗೀಕೃತ ಪ್ರತ್ಯಯವಾಗಿ (ಎಲ್ಲವೂ ಸರಿಯಾದ ಬಕೆಟ್ನಲ್ಲಿವೆ ಮತ್ತು ಮತ್ತೆ ಚಲಿಸಲಾಗುವುದಿಲ್ಲ) ವಿಂಗಡಿಸಲಾಗಿದೆ ಎಂದು ನಾವು ಲೂಪ್ ಇನ್ವೇರಿಯಂಟ್ ಅನ್ನು ನಿರ್ವಹಿಸುತ್ತೇವೆ. ಆರಂಭದಲ್ಲಿ ಮತ್ತು ಎಲ್ಲಾ ಅಂಶಗಳನ್ನು ವರ್ಗೀಕರಿಸಲಾಗಿಲ್ಲ. ವಿಂಗಡಣೆ ಮುಂದುವರೆದಂತೆ, ಎಲ್ಲಾ ಅಂಶಗಳನ್ನು ಸರಿಯಾದ ಬಕೆಟ್ ಆಗಿ ವರ್ಗೀಕರಿಸುವವರೆಗೆ ಅವುಗಳನ್ನು ಕಡಿಮೆ ಮಾಡಲಾಗುತ್ತದೆ. ಪ್ರತಿ ಸುತ್ತು ಮೊದಲ ಅಪೂರ್ಣವಾಗಿ ವರ್ಗೀಕರಿಸಲಾದ ಬಕೆಟ್ ಅನ್ನು (ಹೊಂದಿರುವ) ಕಂಡುಹಿಡಿಯುವ ಮೂಲಕ ಮತ್ತು ಆ ಬಕೆಟ್ನಲ್ಲಿ ಮೊದಲ ವರ್ಗೀಕರಿಸದ ಅಂಶವನ್ನು ತೆಗೆದುಕೊಳ್ಳುವ ಮೂಲಕ ಪ್ರಾರಂಭವಾಗುತ್ತದೆ. (ನ್ಯೂಬರ್ಟ್ ಇದನ್ನು "ಸೈಕಲ್ ಲೀಡರ್" ಎಂದು ಕರೆಯುತ್ತಾರೆ.) ತಾತ್ಕಾಲಿಕ ಚಲಪರಿಮಾಣಕ್ಕೆ ನಕಲು ಮಾಡಿ ಮತ್ತು ಪುನರಾವರ್ತಿಸಿಃ ಯಾವ ಬಕೆಟ್ಗೆ ಸೇರಿದೆ ಎಂಬುದನ್ನು ಲೆಕ್ಕಾಚಾರ ಮಾಡಿ. ಅದನ್ನು ಶೇಖರಿಸಿಡುವ ಸ್ಥಳವಾಗಿರಲಿ. ವಿನಿಮಯ ಮಾಡಿಕೊಳ್ಳಿ, ಅಂದರೆ. ಹಿಂದಿನ ಮೌಲ್ಯವನ್ನು ತರುವಾಗ ಆ ಮೂಲಕ ಸ್ಥಳಾಂತರಗೊಂಡಾಗ ಸಂಗ್ರಹಿಸಿ. ಈಗ ಸರಿಯಾಗಿ ವರ್ಗೀಕರಿಸಲಾಗಿರುವ ಅಂಶವನ್ನು ಪ್ರತಿಬಿಂಬಿಸುವ ಇಳಿಕೆ. ಹಾಗಿದ್ದಲ್ಲಿ, ಈ ಲೂಪ್ ಅನ್ನು ಹೊಸದರೊಂದಿಗೆ ಮರುಪ್ರಾರಂಭಿಸಿ. ಈ ಸುತ್ತು ಮುಗಿದಿದ್ದರೆ ಮತ್ತು ಹೊಸ ಮೊದಲ ವರ್ಗೀಕರಿಸದ ಅಂಶವನ್ನು ಹುಡುಕಿ. ಹೆಚ್ಚು ವರ್ಗೀಕರಿಸದ ಅಂಶಗಳು ಇಲ್ಲದಿದ್ದಾಗ, ಬಕೆಟ್ಗಳಲ್ಲಿ ವಿತರಣೆ ಪೂರ್ಣಗೊಳ್ಳುತ್ತದೆ. ಈ ರೀತಿಯಲ್ಲಿ ಪ್ರತಿ ಬಕೆಟ್ಗೆ ಎರಡು ಅಸ್ಥಿರಗಳೊಂದಿಗೆ ಕಾರ್ಯಗತಗೊಳಿಸಿದಾಗ, ಪ್ರತಿ ಸುತ್ತಿನ ಆರಂಭಿಕ ಬಿಂದುವಿನ ಆಯ್ಕೆಯು ವಾಸ್ತವವಾಗಿ ಅನಿಯಂತ್ರಿತವಾಗಿರುತ್ತದೆ; ಯಾವುದೇ ವರ್ಗೀಕರಿಸದ ಅಂಶವನ್ನು ಸೈಕಲ್ ಲೀಡರ್ ಆಗಿ ಬಳಸಬಹುದು. ಸೈಕಲ್ ಲೀಡರ್ಗಳನ್ನು ಪರಿಣಾಮಕಾರಿಯಾಗಿ ಕಂಡುಹಿಡಿಯುವುದು ಮಾತ್ರ ಅವಶ್ಯಕತೆಯಾಗಿದೆ. ಹಿಂದಿನ ವಿವರಣೆಯು ಸೈಕಲ್ ಲೀಡರ್ಗಳನ್ನು ಕಂಡುಹಿಡಿಯಲು ಬಳಸುತ್ತದೆಯಾದರೂ, ವಾಸ್ತವವಾಗಿ ಅದು ಇಲ್ಲದೆ ಮಾಡಲು ಸಾಧ್ಯವಿದೆ, ಇದು ಸಂಪೂರ್ಣ ಪದ ಶ್ರೇಣಿಯನ್ನು ತೆಗೆದುಹಾಕಲು ಅನುವು ಮಾಡಿಕೊಡುತ್ತದೆ. (ವಿತರಣೆ ಪೂರ್ಣಗೊಂಡ ನಂತರ, ಬಕೆಟ್ ಗಡಿಗಳನ್ನು ಇಲ್ಲಿ ಕಾಣಬಹುದು.) ನಾವು ಎಲ್ಲಾ ಅಂಶಗಳನ್ನು ವರ್ಗೀಕರಿಸಿದ್ದೇವೆ ಮತ್ತು ಸಂಭಾವ್ಯ ಹೊಸ ಸೈಕಲ್ ಲೀಡರ್ ಎಂದು ಪರಿಗಣಿಸುತ್ತಿದ್ದೇವೆ ಎಂದು ಭಾವಿಸೋಣ. ಅದರ ಗುರಿ ಬಕೆಟ್ ಅನ್ನು ಲೆಕ್ಕ ಹಾಕುವುದು ಸುಲಭ. ಲೂಪ್ ಇನ್ವೇರಿಯಂಟ್ನಿಂದ, ಅದನ್ನು ವರ್ಗೀಕರಿಸಲಾಗುತ್ತದೆ ಮತ್ತು ವರ್ಗೀಕರಿಸಲಾಗದಿದ್ದರೆ ಅದು ಆ ವ್ಯಾಪ್ತಿಯ ಹೊರಗಿರುತ್ತದೆ. ಮೊದಲಿನ ಅಸಮಾನತೆಯನ್ನು ಪರೀಕ್ಷಿಸುವುದು ಸುಲಭ, ಆದರೆ ಎರಡನೆಯದಕ್ಕೆ ಮೌಲ್ಯದ ಅಗತ್ಯವಿರುತ್ತದೆ. ಎಲ್ಲಾ ಅಂಶಗಳನ್ನು ವರ್ಗೀಕರಿಸಲಾಗಿದೆ ಎಂಬ ಪ್ರಚೋದನೆಯ ಊಹೆಯು ಅದನ್ನು ಸೂಚಿಸುತ್ತದೆ, ಆದ್ದರಿಂದ ಎರಡನೇ ಅಸಮಾನತೆಯನ್ನು ಪರೀಕ್ಷಿಸುವ ಅಗತ್ಯವಿಲ್ಲ. ಯಾವ ಸ್ಥಾನವು ಯಾವ ಬಕೆಟ್ಗೆ ಬೀಳುತ್ತದೆ ಎಂಬುದನ್ನು ಪರಿಗಣಿಸಿ. ಅಂದರೆ,. ಇಂಡಕ್ಷನ್ ಹೈಪೋಥೆಸಿಸ್ನ ಪ್ರಕಾರ, ಎಲ್ಲಾ ಬಕೆಟ್ಗಳನ್ನು ಒಳಗೊಂಡಿರುವ ಕೆಳಗಿನ ಎಲ್ಲಾ ಅಂಶಗಳನ್ನು ಸಂಪೂರ್ಣವಾಗಿ ವರ್ಗೀಕರಿಸಲಾಗಿದೆ. ಐ. ಇ. ಆ ಬಕೆಟ್ಗಳಲ್ಲಿ ಸೇರಿರುವ ಯಾವುದೇ ಅಂಶಗಳು ಉಳಿದ ಶ್ರೇಣಿಯಲ್ಲಿ ಉಳಿಯುವುದಿಲ್ಲ. ಆದ್ದರಿಂದ, ಇದು ಸಾಧ್ಯವಿಲ್ಲ. ಉಳಿದಿರುವ ಏಕೈಕ ಪ್ರಕರಣವೆಂದರೆ, ಅಂದರೆ, ಕ್ಯೂ. ಇ. ಡಿ. ಇದನ್ನು ಸಂಯೋಜಿಸಿ, ಫ್ಲಾಶ್ ಸಾರ್ಟ್ ಡಿಸ್ಟ್ರಿಬ್ಯೂಷನ್ ಅಲ್ಗಾರಿದಮ್ ಮೇಲೆ ವಿವರಿಸಿದಂತೆ ಪ್ರಾರಂಭವಾಗುತ್ತದೆ. ನಂತರ ಮುಂದುವರಿಸಿಃ ವಿತರಣೆಯು ಪೂರ್ಣಗೊಂಡಿದ್ದರೆ. ಕೊಟ್ಟಿರುವಂತೆ, ಅದು ಯಾವ ಬಕೆಟ್ಗೆ ಸೇರಿದೆ ಎಂಬುದನ್ನು ಲೆಕ್ಕ ಹಾಕಿ. ಇದ್ದರೆ, ನಂತರ ವರ್ಗೀಕರಿಸಲಾಗಿಲ್ಲ. ಇದನ್ನು ತಾತ್ಕಾಲಿಕ ವೇರಿಯೇಬಲ್ ಆಗಿ ನಕಲು ಮಾಡಿ ಮತ್ತುಃ ಅದನ್ನು ಸಂಗ್ರಹಿಸಲಾಗುವ ಸ್ಥಳವಾಗಿರಲಿ. ವಿನಿಮಯ ಮಾಡಿಕೊಳ್ಳಿ, ಅಂದರೆ. ಹಿಂದಿನ ಮೌಲ್ಯವನ್ನು ತರುವಾಗ ಆ ಮೂಲಕ ಸ್ಥಳಾಂತರಗೊಂಡಾಗ ಸಂಗ್ರಹಿಸಿ. ಈಗ ಸರಿಯಾಗಿ ವರ್ಗೀಕರಿಸಲಾಗಿರುವ ಅಂಶವನ್ನು ಪ್ರತಿಬಿಂಬಿಸುವ ಇಳಿಕೆ. ಇದ್ದರೆ, ಯಾವ ಬಕೆಟ್ಗೆ ಸೇರಿದೆ ಎಂಬುದನ್ನು ಲೆಕ್ಕ ಹಾಕಿ ಮತ್ತು ಈ (ಒಳಗಿನ) ಲೂಪ್ ಅನ್ನು ಹೊಸದರೊಂದಿಗೆ ಮರುಪ್ರಾರಂಭಿಸಿ. ಈಗ ಅದನ್ನು ಸರಿಯಾಗಿ ವರ್ಗೀಕರಿಸಲಾಗಿದೆ. (ಹೊರಗಿನ) ಲೂಪ್ ಅನ್ನು ಹೆಚ್ಚಿಸಿ ಮತ್ತು ಮರುಪ್ರಾರಂಭಿಸಿ. ಮೆಮೊರಿಯನ್ನು ಉಳಿಸುವಾಗ, ಫ್ಲ್ಯಾಶ್ಸಾರ್ಟ್ ಅನಾನುಕೂಲತೆಯನ್ನು ಹೊಂದಿದೆ, ಅದು ಈಗಾಗಲೇ ವರ್ಗೀಕರಿಸಲಾದ ಅನೇಕ ಅಂಶಗಳಿಗೆ ಬಕೆಟ್ ಅನ್ನು ಮರು ಲೆಕ್ಕಾಚಾರ ಮಾಡುತ್ತದೆ. ಇದನ್ನು ಈಗಾಗಲೇ ಪ್ರತಿ ಅಂಶಕ್ಕೆ ಎರಡು ಬಾರಿ ಮಾಡಲಾಗುತ್ತದೆ (ಒಮ್ಮೆ ಬಕೆಟ್ ಎಣಿಕೆಯ ಹಂತದಲ್ಲಿ ಮತ್ತು ಪ್ರತಿ ಅಂಶವನ್ನು ಚಲಿಸುವಾಗ ಎರಡನೇ ಬಾರಿಗೆ), ಆದರೆ ಮೊದಲ ವರ್ಗೀಕರಿಸದ ಅಂಶವನ್ನು ಹುಡುಕಲು ಹೆಚ್ಚಿನ ಅಂಶಗಳಿಗೆ ಮೂರನೇ ಗಣನೆಯ ಅಗತ್ಯವಿದೆ. ಸರಳ ರೇಖೀಯ ಅಂತರ್ವೇಶನಕ್ಕಿಂತ ಹೆಚ್ಚು ಸಂಕೀರ್ಣವಾದ ಸೂತ್ರವನ್ನು ಬಳಸಿಕೊಂಡು ಬಕೆಟ್ಗಳನ್ನು ನಿಯೋಜಿಸಿದರೆ ಇದು ದುಬಾರಿಯಾಗಬಹುದು. ಒಂದು ರೂಪಾಂತರವು ಅಪೂರ್ಣವಾದ ಬಕೆಟ್ನಲ್ಲಿ ಕೊನೆಯ ವರ್ಗೀಕರಿಸದ ಅಂಶವನ್ನು ಸೈಕಲ್ ಲೀಡರ್ ಆಗಿ ತೆಗೆದುಕೊಳ್ಳುವ ಮೂಲಕ ಲೆಕ್ಕಾಚಾರಗಳ ಸಂಖ್ಯೆಯನ್ನು ಬಹುತೇಕದಿಂದ ಗರಿಷ್ಠಕ್ಕೆ ಕಡಿಮೆ ಮಾಡುತ್ತದೆಃ ಮೊದಲ ಅಪೂರ್ಣವಾಗಿ ವರ್ಗೀಕರಿಸಲಾದ ಬಕೆಟ್ ಅನ್ನು ಗುರುತಿಸುವ ವೇರಿಯೇಬಲ್ ಅನ್ನು ನಿರ್ವಹಿಸಿ. ಪ್ರಾರಂಭಿಸೋಣ, ಮತ್ತು ಯಾವಾಗ, ವಿತರಣೆ ಪೂರ್ಣಗೊಳ್ಳುತ್ತದೆ. ಬಿಡಿ. ಇದ್ದರೆ, ಈ ಲೂಪ್ ಅನ್ನು ಹೆಚ್ಚಿಸಿ ಮತ್ತು ಮರುಪ್ರಾರಂಭಿಸಿ. (.) ಯಾವ ಬಕೆಟ್ಗೆ ಸೇರಿದೆ ಎಂಬುದನ್ನು ಲೆಕ್ಕ ಹಾಕಿ. ಇಫ್, ನಂತರ ಮತ್ತು ನಾವು ಬಕೆಟ್ನೊಂದಿಗೆ ಮುಗಿಸಿದ್ದೇವೆ. ಈ ಲೂಪ್ ಅನ್ನು ಹೆಚ್ಚಿಸಿ ಮತ್ತು ಮರುಪ್ರಾರಂಭಿಸಿ. ಇದ್ದರೆ, ವರ್ಗೀಕರಣವು ಕ್ಷುಲ್ಲಕವಾಗಿದೆ. ಈ ಲೂಪ್ ಅನ್ನು ಕಡಿಮೆ ಮಾಡಿ ಮತ್ತು ಮರುಪ್ರಾರಂಭಿಸಿ. ಇದ್ದರೆ, ನಂತರ ವರ್ಗೀಕರಿಸಲಾಗಿಲ್ಲ. ಹಿಂದಿನ ಪ್ರಕರಣದಂತೆಯೇ ಅದೇ ವರ್ಗೀಕರಣ ಲೂಪ್ ಅನ್ನು ನಿರ್ವಹಿಸಿ, ನಂತರ ಈ ಲೂಪ್ ಅನ್ನು ಮರುಪ್ರಾರಂಭಿಸಿ. ಹೆಚ್ಚಿನ ಅಂಶಗಳು ತಮ್ಮ ಬಕೆಟ್ಗಳನ್ನು ಎರಡು ಬಾರಿ ಮಾತ್ರ ಲೆಕ್ಕ ಹಾಕುತ್ತವೆ, ಪ್ರತಿ ಬಕೆಟ್ನಲ್ಲಿನ ಅಂತಿಮ ಅಂಶವನ್ನು ಹೊರತುಪಡಿಸಿ, ಇದನ್ನು ಮುಂದಿನ ಬಕೆಟ್ನ ಪೂರ್ಣಗೊಳಿಸುವಿಕೆಯನ್ನು ಪತ್ತೆಹಚ್ಚಲು ಬಳಸಲಾಗುತ್ತದೆ. ವರ್ಗೀಕರಿಸದ ಅಂಶಗಳ ಎಣಿಕೆಯನ್ನು ನಿರ್ವಹಿಸುವ ಮೂಲಕ ಮತ್ತು ಅದು ಶೂನ್ಯವನ್ನು ತಲುಪಿದಾಗ ನಿಲ್ಲಿಸುವ ಮೂಲಕ ಇನ್ನೂ ಒಂದು ಸಣ್ಣ ಕಡಿತವನ್ನು ಸಾಧಿಸಬಹುದು. ಕಾರ್ಯಕ್ಷಮತೆ ಬಕೆಟ್ ಮಿತಿಗಳನ್ನು ಸಂಗ್ರಹಿಸಲು ಸಹಾಯಕ ವಾಹಕ ಮತ್ತು ಬಳಸಿದ ಇತರ ಅಸ್ಥಿರಗಳ ಸ್ಥಿರ ಸಂಖ್ಯೆಗಳು ಮಾತ್ರ ಹೆಚ್ಚುವರಿ ಮೆಮೊರಿ ಅವಶ್ಯಕತೆಗಳಾಗಿವೆ. ಇದಲ್ಲದೆ, ಪ್ರತಿ ಅಂಶವನ್ನು ಒಮ್ಮೆ ಮಾತ್ರ ಸರಿಸಲಾಗುತ್ತದೆ (ತಾತ್ಕಾಲಿಕ ಬಫರ್ ಮೂಲಕ, ಆದ್ದರಿಂದ ಎರಡು ಚಲನೆ ಕಾರ್ಯಾಚರಣೆಗಳು). ಆದಾಗ್ಯೂ, ಈ ಮೆಮೊರಿ ದಕ್ಷತೆಯು ರಚನೆಯನ್ನು ಯಾದೃಚ್ಛಿಕವಾಗಿ ಪ್ರವೇಶಿಸುವ ಅನಾನುಕೂಲತೆಯೊಂದಿಗೆ ಬರುತ್ತದೆ, ಆದ್ದರಿಂದ ಇಡೀ ರಚನೆಯ ಚಿಕ್ಕದಾದ ಡೇಟಾ ಕ್ಯಾಶ್ನ ಲಾಭವನ್ನು ಪಡೆಯಲು ಸಾಧ್ಯವಿಲ್ಲ. ಎಲ್ಲಾ ಬಕೆಟ್ ಪ್ರಕಾರಗಳಂತೆಯೇ, ಕಾರ್ಯಕ್ಷಮತೆಯು ಬಕೆಟ್ಗಳ ಸಮತೋಲನದ ಮೇಲೆ ವಿಮರ್ಶಾತ್ಮಕವಾಗಿ ಅವಲಂಬಿತವಾಗಿರುತ್ತದೆ. ಸಮತೋಲಿತ ದತ್ತಾಂಶ ಗುಂಪಿನ ಆದರ್ಶ ಸಂದರ್ಭದಲ್ಲಿ, ಪ್ರತಿ ಬಕೆಟ್ ಸರಿಸುಮಾರು ಒಂದೇ ಗಾತ್ರದ್ದಾಗಿರುತ್ತದೆ. ಇನ್ಪುಟ್ ಗಾತ್ರದಲ್ಲಿ ಬಕೆಟ್ಗಳ ಸಂಖ್ಯೆಯು ರೇಖೀಯವಾಗಿದ್ದರೆ, ಪ್ರತಿ ಬಕೆಟ್ ಸ್ಥಿರವಾದ ಗಾತ್ರವನ್ನು ಹೊಂದಿರುತ್ತದೆ, ಆದ್ದರಿಂದ ಇನ್ಸರ್ಷನ್ ಸಾರ್ಟ್ನಂತಹ ಅಲ್ಗಾರಿದಮ್ನೊಂದಿಗೆ ಒಂದೇ ಬಕೆಟ್ ಅನ್ನು ವಿಂಗಡಿಸುವುದು ಸಂಕೀರ್ಣತೆಯನ್ನು ಹೊಂದಿರುತ್ತದೆ. ಆದ್ದರಿಂದ ಅಂತಿಮ ಅಳವಡಿಕೆಯ ಪ್ರಕಾರಗಳ ಚಾಲನೆಯಲ್ಲಿರುವ ಸಮಯ. ಒಂದು ಮೌಲ್ಯವನ್ನು ಆಯ್ಕೆ ಮಾಡುವುದು, ಬಕೆಟ್ಗಳ ಸಂಖ್ಯೆ, ಅಂಶಗಳನ್ನು ವರ್ಗೀಕರಿಸಲು (ಹೆಚ್ಚಿನ) ಮತ್ತು ಅಂತಿಮ ಅಳವಡಿಕೆ ವಿಂಗಡಣಾ ಹಂತದಲ್ಲಿ (ಕಡಿಮೆ) ಕಳೆದ ಸಮಯವನ್ನು ಕಳೆಯುವ ಸಮಯ. ಉದಾಹರಣೆಗೆ, ಅನುಪಾತದಲ್ಲಿ ಆಯ್ಕೆ ಮಾಡಿದರೆ, ಅಂತಿಮ ಅಳವಡಿಕೆಯ ಪ್ರಕಾರಗಳ ಚಾಲನೆಯಲ್ಲಿರುವ ಸಮಯವು ಆದ್ದರಿಂದ. ಬಹುತೇಕ ಎಲ್ಲಾ ಅಂಶಗಳು ಕೆಲವು ಬಕೆಟ್ಗಳಲ್ಲಿರುವ ಕೆಟ್ಟ-ಸನ್ನಿವೇಶಗಳಲ್ಲಿ, ಅಲ್ಗಾರಿದಮ್ನ ಸಂಕೀರ್ಣತೆಯು ಅಂತಿಮ ಬಕೆಟ್-ವಿಂಗಡಣಾ ವಿಧಾನದ ಕಾರ್ಯಕ್ಷಮತೆಯಿಂದ ಸೀಮಿತವಾಗಿರುತ್ತದೆ, ಆದ್ದರಿಂದ ಕೆಳಮಟ್ಟಕ್ಕೆ ಕುಸಿಯುತ್ತದೆ. ಅಲ್ಗಾರಿದಮ್ನ ವ್ಯತ್ಯಾಸಗಳು ಒಂದು ನಿರ್ದಿಷ್ಟ ಗಾತ್ರದ ಮಿತಿಯನ್ನು ಮೀರಿದ ಬಕೆಟ್ಗಳ ಮೇಲೆ ಕ್ವಿಕ್ಸಾರ್ಟ್ ಅಥವಾ ರಿಕರ್ಸಿವ್ ಫ್ಲ್ಯಾಷ್ಸಾರ್ಟ್ನಂತಹ ಉತ್ತಮ-ಕಾರ್ಯಕ್ಷಮತೆಯ ಪ್ರಕಾರಗಳನ್ನು ಬಳಸುವ ಮೂಲಕ ಕೆಟ್ಟ-ಪರಿಸ್ಥಿತಿಯ ಕಾರ್ಯಕ್ಷಮತೆಯನ್ನು ಸುಧಾರಿಸುತ್ತವೆ. ಏಕರೂಪವಾಗಿ ವಿತರಿಸಲಾದ ಯಾದೃಚ್ಛಿಕ ದತ್ತಾಂಶದೊಂದಿಗೆ, ಫ್ಲ್ಯಾಷ್ಸಾರ್ಟ್ ಎಲ್ಲರಿಗೂ ಹೀಪ್ಸಾರ್ಟ್ಗಿಂತ ವೇಗವಾಗಿರುತ್ತದೆ ಮತ್ತು ಕ್ವಿಕ್ಸಾರ್ಟ್ಗಿಂತ ವೇಗವಾಗಿರುತ್ತದೆ. ಇದು ತ್ವರಿತಗತಿಯ ವೇಗಕ್ಕಿಂತ ಸುಮಾರು ಎರಡು ಪಟ್ಟು ವೇಗವಾಗಿರುತ್ತದೆ. ಈ ಅಳತೆಗಳನ್ನು 1990 ರ ದಶಕದ ಕೊನೆಯಲ್ಲಿ ತೆಗೆದುಕೊಳ್ಳಲಾಗಿದೆ ಎಂಬುದನ್ನು ಗಮನಿಸಿ, ಮೆಮೊರಿ ಶ್ರೇಣಿ ವ್ಯವಸ್ಥೆಗಳು ಕ್ಯಾಶಿಂಗ್ ಮೇಲೆ ಕಡಿಮೆ ಅವಲಂಬಿತವಾಗಿದ್ದವು. ಅದರ ವರ್ಗೀಕರಣ ಪ್ರಕ್ರಿಯೆಯಲ್ಲಿ ಫ್ಲಾಶ್ಸಾರ್ಟ್ ನಿರ್ವಹಿಸುವ ಇನ್ ಸಿಟು ಕ್ರಮಪಲ್ಲಟನೆಯಿಂದಾಗಿ, ಫ್ಲಾಶ್ಸಾರ್ಟ್ ಸ್ಥಿರವಾಗಿಲ್ಲ. ಸ್ಥಿರತೆಯ ಅಗತ್ಯವಿದ್ದರೆ, ಅಂಶಗಳನ್ನು ಅನುಕ್ರಮವಾಗಿ ವರ್ಗೀಕರಿಸಲು ಎರಡನೇ ಶ್ರೇಣಿಯನ್ನು ಬಳಸಲು ಸಾಧ್ಯವಿದೆ. ಆದಾಗ್ಯೂ, ಈ ಸಂದರ್ಭದಲ್ಲಿ, ಅಲ್ಗಾರಿದಮ್ಗೆ ಹೆಚ್ಚುವರಿ ಮೆಮೊರಿಯ ಅಗತ್ಯವಿರುತ್ತದೆ. ಉಲ್ಲೇಖಗಳನ್ನು ವಿಂಗಡಿಸುವ ಬದಲು ಹುಡುಕಲು ವಸ್ತುಗಳ ವಿತರಣೆಯನ್ನು ಬಳಸಿಕೊಂಡು ಇಂಟರ್ಪೊಲೇಷನ್ ಹುಡುಕಾಟವನ್ನು ಸಹ ನೋಡಿ ಬಾಹ್ಯ ಕೊಂಡಿಗಳು ದೊಡ್ಡ ಸಮಾನಾಂತರ ಯಂತ್ರಗಳಲ್ಲಿ ಯಾದೃಚ್ಛಿಕ ವಿಂಗಡಣೆಗಳ ಅನುಷ್ಠಾನಗಳು (1992) ಸಮಾನಾಂತರ ಕ್ರಮಾವಳಿಗಳ ಅನುಷ್ಠಾನ (1992) ಫ್ಲ್ಯಾಶ್ಸಾರ್ಟ್ ವಿಂಗಡಣೆ ಕ್ರಮಾವಳಿಗಳ ದೃಶ್ಯೀಕರಣ