[Powered by Google Translate] [ಬಬಲ್ SORT] [JACKSON STEINKAMP ಹಾರ್ವರ್ಡ್ ವಿಶ್ವವಿದ್ಯಾಲಯ] [ಈ CS50 IS. CS50TV] ಬಬಲ್ ವಿಂಗಡಿಸಿ ಒಂದು ವಿಂಗಡಿಸುವ ಕ್ರಮಾವಳಿಯ ಒಂದು ಉದಾಹರಣೆ - ಎಂದು, ಅಂಶಗಳ ಒಂದು ಸೆಟ್ ವಿಂಗಡಿಸುವ ಒಂದು ವಿಧಾನ ಆರೋಹಣ ಅಥವಾ ಇಳಿಕೆಯ ಕ್ರಮದಲ್ಲಿ. ನೀವು ಒಂದು ಶ್ರೇಣಿಯನ್ನು ವಿಂಗಡಿಸಲು ಬಯಸಿದರೆ ಉದಾಹರಣೆಗೆ, ಸಂಖ್ಯೆಗಳನ್ನು ಒಳಗೊಂಡ [3, 5, 2, 9], ಬಬಲ್ ವಿಂಗಡಿಸಿ ಒಂದು ಸರಿಯಾದ ಅನುಷ್ಠಾನಕ್ಕೆ ಹಿಂದಿರುಗುತ್ತಿದ್ದವು ವಿಂಗಡಿಸಲಾದ ರಚನೆಯ [2, 3, 5, 9] ಏರಿಕೆಯ ಕ್ರಮದಲ್ಲಿ. ಈಗ, ನಾನು ಅಲ್ಗಾರಿದಮ್ ಕೆಲಸ ಹೇಗೆ ಸೂಡೊಕೋಡ್ಗಳನ್ನು ವಿವರಿಸಿರಿ ಪಡೆಯಲಿದ್ದೇನೆ. 

3, 2, 9, 6, ಮತ್ತು 5 - ನಮಗೆ 5 ಪೂರ್ಣಾಂಕಗಳ ಪಟ್ಟಿಯನ್ನು ವಿಂಗಡಿಸುವ ನೀವು ಹೇಳಬಹುದು. ಕ್ರಮಾವಳಿ, ಮೊದಲ ಎರಡು ಅಂಶಗಳು, 3 ಮತ್ತು 2 ನೇ ಹುಡುಕುವುದರಿಂದ ಆರಂಭಿಸುತ್ತದೆ ಅವರು ಪರಸ್ಪರ ಸಂಬಂಧಿತ ಕ್ರಮದಲ್ಲಿ ಇಲ್ಲ ವೇಳೆ ಮತ್ತು ಪರೀಕ್ಷಿಸುವುದು. ಅವು - 3 2 ಹೆಚ್ಚಾಗಿದೆ. ಆರೋಹಣ ಕ್ರಮದಲ್ಲಿ ಎಂದು, ಅವರು ಇತರ ಆಗಿರಬೇಕು. ಆದ್ದರಿಂದ, ನಾವು ಅವುಗಳನ್ನು ವಿನಿಮಯ. [2, 3, 9, 6, 5]: ಈಗ ಪಟ್ಟಿಯಲ್ಲಿ ಈ ತೋರುತ್ತಿದೆ. 

ಮುಂದೆ, ನಾವು ಎರಡನೇ ಮತ್ತು ಮೂರನೇ ಅಂಶಗಳು, 3 ಮತ್ತು 9 ನೋಡಲು. ಅವರು ಪರಸ್ಪರ ಸಂಬಂಧಿಸಿದಂತೆ ಸರಿಯಾದ ಕ್ರಮದಲ್ಲಿ ಆರ್. ಕ್ರಮಾವಳಿ ಅವುಗಳನ್ನು ಸ್ವ್ಯಾಪ್ ಮಾಡುವುದಿಲ್ಲ 9 ಕಡಿಮೆ ಆದ್ದರಿಂದ ಎಂದು, 3. ಮುಂದೆ, ನಾವು 9 ಮತ್ತು 6 ನೋಡಲು. ಅವರು ಆದೇಶ ಇಲ್ಲ. 

ಆದ್ದರಿಂದ, ನಾವು 9 6 ಹೆಚ್ಚಿನ ಏಕೆಂದರೆ ಅವುಗಳನ್ನು ಸ್ವ್ಯಾಪ್ ಅಗತ್ಯವಿದೆ. ಕೊನೆಯದಾಗಿ, ಕಳೆದ ಎರಡು ಪೂರ್ಣಾಂಕಗಳ, 9 ಮತ್ತು 5 ನೋಡಲು. ಅವರು ಕ್ರಮದಲ್ಲಿ ಇಲ್ಲ, ಆದ್ದರಿಂದ ಅವರು ವಿನಿಮಯವಾಗಿದೆ ಮಾಡಬೇಕು. ಪಟ್ಟಿ ಮೂಲಕ ಮೊದಲ ಸಂಪೂರ್ಣ ಪಾಸ್ ನಂತರ, [2, 3, 6, 5, 9]: ಇದು ಕಾಣುತ್ತದೆ. ಕೆಟ್ಟ. ಇದು ಬಹುತೇಕ ವಿಂಗಡಿಸಲಾದ ನ. ಆದರೆ ಇದು ಸಂಪೂರ್ಣವಾಗಿ ಪ್ರತ್ಯೇಕಿಸಬಹುದು ಪಡೆಯಲು ಮತ್ತೆ ಪಟ್ಟಿಯಲ್ಲಿ ಮೂಲಕ ಚಲಿಸಬೇಕಾಗುತ್ತದೆ. ಎರಡು 3 ಕಡಿಮೆ, ಆದ್ದರಿಂದ ನಾವು ಅದನ್ನು ಸ್ವ್ಯಾಪ್ ಮಾಡಬಾರದು. 

ಮೂರು 6 ಕಡಿಮೆ, ಆದ್ದರಿಂದ ನಾವು ಅದನ್ನು ಸ್ವ್ಯಾಪ್ ಮಾಡಬಾರದು. ಆರು 5 ಹೆಚ್ಚಾಗಿದೆ. ನಾವು ಬದಲಾಯಿಸಿಕೊಳ್ಳಬಹುದು. ಆರು 9 ಕಡಿಮೆ. ನಾವು ಸ್ವ್ಯಾಪ್ ಮಾಡಬಾರದು. ಮೂಲಕ ಎರಡನೇ ಪಾಸ್ ನಂತರ, ಇದು ಈ ತೋರುತ್ತಿದೆ: [2, 3, 5, 6, 9]. ಪರಿಪೂರ್ಣ. ಈಗ, ಇದು ಸೂಡೊಕೋಡ್ಗಳನ್ನು ರಲ್ಲಿ ಬರೆಯೋಣ. ಮೂಲತಃ, ಪಟ್ಟಿಯಲ್ಲಿ ಪ್ರತಿ ಅಂಶ, ನಾವು ನೋಡಬೇಕು ಮತ್ತು ನೇರವಾಗಿ ಅದರ ಬಲಕ್ಕೆ ಅಂಶ. ಅವರು ಆರ್ಡರ್ ಆಫ್ ಪರಸ್ಪರ ಸಂಬಂಧಿತ ಔಟ್ ಇದ್ದರೆ - ಎಂದು, ವೇಳೆ ಎಡಭಾಗದಲ್ಲಿ ಅಂಶ ಬಲಭಾಗದಲ್ಲಿ ಒಂದು ಹೆಚ್ಚಾಗಿದೆ - ನಾವು ಎರಡು ಅಂಶಗಳನ್ನು ವಿನಿಮಯ ಮಾಡಬೇಕು. 

ನಾವು ಪಟ್ಟಿಯ ಪ್ರತಿ ಅಂಶ ಹಾಗೆ, ಮತ್ತು ನಾವು ಮೂಲಕ ಒಂದು ಪಾಸ್ ಮಾಡಿದ. ಈಗ ನಾವು ಪಟ್ಟಿ ಖಚಿತಪಡಿಸಿಕೊಳ್ಳಲು ಪಾಸ್ ಮೂಲಕ ಸಾಕಷ್ಟು ಬಾರಿ ಮಾಡಬೇಕು ಸಂಪೂರ್ಣವಾಗಿ, ಸರಿಯಾಗಿ ವಿಂಗಡಿಸಲ್ಪಡುತ್ತದೆ. ಆದರೆ ನಾವು ಪಟ್ಟಿ ಮೂಲಕ ಹಾದುಹೋಗಲು ಎಷ್ಟು ಬಾರಿ ಹೊಂದಿಲ್ಲ ನಾವು ಮುಗಿಸಿದ ಎಂದು ಖಾತರಿ? ನಾವು ಸಂಪೂರ್ಣವಾಗಿ ಹಿಂದಕ್ಕೆ ಪಟ್ಟಿ ಹೊಂದಿದ್ದರೆ ಅಲ್ಲದೆ, ಕೆಟ್ಟ ಸಂದರ್ಭಗಳಲ್ಲಿ ಹೊಂದಿದೆ. ಆಗ ಇದು ಸಂಖ್ಯೆ ಸಮಾನವಾಗಿರುತ್ತದೆ ಹಾದು ಸಾಗುವಂತಹವರು ಹಲವಾರು ತೆಗೆದುಕೊಳ್ಳುತ್ತದೆ ಅಂಶಗಳನ್ನು N-1. ಈ ಅಂಶಕ್ಕೆ ಅರ್ಥದಲ್ಲಿ ಮಾಡುವುದಿಲ್ಲ, ಒಂದು ಸರಳ ಪ್ರಕರಣದ ಭಾವಿಸುತ್ತೇನೆ - ಪಟ್ಟಿ [2, 1]. 

ಈ ಸರಿಯಾಗಿ ವಿಂಗಡಿಸಲು ಒಂದು ಪಾಸ್ ಮೂಲಕ ತೆಗೆದುಕೊಂಡು ಹೋಗುತ್ತದೆ. [3, 2, 1] - ಕೆಟ್ಟ ಸಂದರ್ಭದಲ್ಲಿ, 3 ಅಂಶಗಳನ್ನು ಹಿಂದಕ್ಕೆ ವಿಂಗಡಿಸುತ್ತದೆ ಎಂದು ಇದು ರೀತಿಯ 2 ಪುನರಾವರ್ತನೆಗಳು ತೆಗೆದುಕೊಳ್ಳುವುದು. ಒಂದು ಪುನರಾವರ್ತನೆ ನಂತರ, [, 3 1 2] ನ. ಎರಡನೇ ಇಳುವರಿ ವಿಂಗಡಿಸಲಾದ ರಚನೆಯ [1, 2, 3]. ಆದ್ದರಿಂದ ನೀವು ಸಾಮಾನ್ಯವಾಗಿ, ಸರಣಿ ಮೂಲಕ ಹೋಗಲು ಎಂದಿಗೂ ತಿಳಿದಿರುವ N ರಚನೆಯ ಅಂಶಗಳ ಸಂಖ್ಯೆಯನ್ನು ಅಲ್ಲಿ N-1 ಪಟ್ಟು ಹೆಚ್ಚು. ದೊಡ್ಡ ಅಂಶಗಳನ್ನು 'ಬಬಲ್ ಅಪ್' ಒಲವು ಏಕೆಂದರೆ ಬಬಲ್ ವಿಂಗಡಿಸಿ ಕರೆಯಲಾಗುತ್ತದೆ ಬಹಳ ಬೇಗನೆ ಬಲಕ್ಕೆ. ವಾಸ್ತವವಾಗಿ, ಈ ಅಲ್ಗಾರಿದಮ್ ಕುತೂಹಲಕಾರಿ ನಡವಳಿಕೆಯನ್ನು ಹೊಂದಿದೆ. 

ಸಂಪೂರ್ಣ ರಚನೆಯ ಮೂಲಕ ಮೀ ಪುನರಾವರ್ತನೆಗಳು ನಂತರ, ಬಲತುದಿಯಲ್ಲಿ ಮೀ ಅಂಶಗಳನ್ನು ಖಾತ್ರಿಯಾಗಿರುತ್ತದೆ ಅವುಗಳ ಸರಿಯಾದ ಸ್ಥಾನದಲ್ಲಿ ವಿಂಗಡಿಸಲಾಗಿದೆ ಎಂದು. ನೀವು, ನಿಮ್ಮ ಈ ನೋಡಲು ಬಯಸಿದರೆ ನಾವು ಸಂಪೂರ್ಣವಾಗಿ ಹಿಂದಕ್ಕೆ ಪಟ್ಟಿ [9, 6, 5, 3, 2] ಇದನ್ನು ಪ್ರಯತ್ನಿಸಿ. ಸಂಪೂರ್ಣ ಪಟ್ಟಿ ಮೂಲಕ ಒಂದು ಪಾಸ್ ನಂತರ, [ಬರವಣಿಗೆಯ ಧ್ವನಿ] [6, 9, 5, 3, 2], [6, 5, 9, 3, 2], [6, 5, 3, 9, 2], [6, 5, 3, 2, 9] ಬಲತುದಿಯಲ್ಲಿ ಅಂಶ 9 ಸರಿಯಾದ ಸ್ಥಳದಲ್ಲಿ ಇದೆ. ಪಾಸ್ ಮೂಲಕ ಎರಡನೇ ನಂತರ, 6 'bubbled ಅಪ್' ಆಗಬೇಕು ಎರಡನೇ ಬಲತುದಿಯಲ್ಲಿ ಸ್ಥಾನ. 6 ಮತ್ತು 9 - - ಬಲ ಎರಡು ಅಂಶಗಳನ್ನು ತಮ್ಮ ಸರಿಯಾದ ಸ್ಥಳಗಳಲ್ಲಿ ಇರುತ್ತದೆ ಮೊದಲ ಎರಡು ಪಾಸ್ ಸಾಗುವಂತಹವರು ನಂತರ. 

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

ನೀವು N ಅಂಶಗಳನ್ನು ಒಂದು ಶ್ರೇಣಿಯನ್ನು ವಿಂಗಡಿಸುವ ನೀವು ಹಾಗಿದ್ದಲ್ಲಿ, ಮೊದಲ ಪುನರಾವರ್ತನೆ ರಂದು - you'll ಅಂಶಗಳನ್ನು ಎಲ್ಲಾ ವಿಂಗಡಿಸಲು ಹೊಂದಿವೆ - ಮೊದಲ N-0. ಎರಡನೇ ಪುನರಾವರ್ತನೆ ರಂದು, ನೀವು ಅಂಶಗಳನ್ನು ಎಲ್ಲಾ ಆದರೆ ಕೊನೆಯ ನೋಡಲು ಸಾಧ್ಯವಿದೆ - N-1 ಮೊದಲ. ಮತ್ತೊಂದು ಆಪ್ಟಿಮೈಜೇಷನ್ ಪಟ್ಟಿಯನ್ನು ಈಗಾಗಲೇ ಪ್ರತ್ಯೇಕಿಸಲ್ಪಡುತ್ತವೆ ವೇಳೆ ಪರಿಶೀಲಿಸಿ ಆಗುತ್ತದೆ ಪ್ರತಿ ಪುನರಾವರ್ತನೆ ನಂತರ. ಇದು ಈಗಾಗಲೇ ವಿಂಗಡಿಸಲಾದ ಇದ್ದರೆ, ನಾವು ಯಾವುದೇ ಪುನರಾವರ್ತನೆಗಳು ಮಾಡುವ ಅಗತ್ಯವಿಲ್ಲ ಪಟ್ಟಿ ಮೂಲಕ. ನಾವು ಹೇಗೆ ಮಾಡಬಹುದು? ಹಾಗೆಯೇ, ನಾವು ಒಂದು ಪಟ್ಟಿಯ ಪಾಸ್ ಮೂಲಕ ಯಾವುದೇ ವಿನಿಮಯ ಮಾಡಲು ಹೋದರೆ, ನಾವು ಏನು ಸ್ವ್ಯಾಪ್ ಕಾರಣ ಪಟ್ಟಿಯನ್ನು ಈಗಾಗಲೇ ವಿಂಗಡಿಸುತ್ತದೆ ಎಂದು ಸ್ಪಷ್ಟವಾಗಿ ಕಾಣುತ್ತದೆ. ನಾವು ಖಂಡಿತವಾಗಿಯೂ ಮತ್ತೆ ವಿಂಗಡಿಸಲು ಹೊಂದಿಲ್ಲ. 

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

ನೀವು ಹೇಳುವುದು ಒಂದು ರೀತಿಯಲ್ಲಿ ಹೊಂದಿರುವ ಎರಡು ಅಂಶಗಳನ್ನು ನೀಡಿದ ವೇಳೆ ಮೊದಲ ಒಂದು ಸಮನಾದ ಅಥವಾ ಎರಡನೇ ಕಡಿಮೆ, ಹೆಚ್ಚು. ಉದಾಹರಣೆಗೆ, ನೀವು ಹೇಳುವ ಮೂಲಕ ವರ್ಣಮಾಲೆಯ ಅಕ್ಷರಗಳನ್ನು ವಿಂಗಡಿಸಲು ಸಾಧ್ಯವಾಗಲಿಲ್ಲ ಒಂದು <ಬೌ, ಬೌ <ಸಿ, ಇತ್ಯಾದಿ ಎಂದು ಭಾನುವಾರ ಸೋಮವಾರ ಗಿಂತ ಕಡಿಮೆ ಅಥವಾ ನೀವು ವಾರದ ದಿನಗಳ ವಿಂಗಡಿಸಲು ಸಾಧ್ಯವಾಗಲಿಲ್ಲ ಇದು ಮಂಗಳವಾರ ಕಡಿಮೆ. 

ಯಾವುದೇ ಒಂದು ಅತ್ಯಂತ ಸಮರ್ಥ ಅಥವಾ ವೇಗದ ಬೇರ್ಪಡಿಸುವ ಅಲ್ಗಾರಿದಮ್ ಎಂದರೆ ಅದಕ್ಕೆ ಬಬಲ್ ವಿಂಗಡಿಸಿ ಹೊಂದಿದೆ. ಕೆಟ್ಟ ಪೆಟ್ಟಿಗೆ ರನ್ಟೈಮ್ N ದೊಡ್ಡ ಒ ² ನಷ್ಟು ವಿಸ್ತೀರ್ಣ ನೀವು ಪಟ್ಟಿಯನ್ನು ಮೂಲಕ N ಪುನರಾವರ್ತನೆಗಳು ಮಾಡಲು ಕಾರಣ ಪ್ರತಿ ಪಾಸ್ ಮೂಲಕ ಎಲ್ಲಾ N ಅಂಶಗಳನ್ನು ಪರಿಶೀಲಿಸುವ, nxn = N ². ಈ ರನ್ ಸಮಯದಲ್ಲಿ ಅಂಶಗಳ ಸಂಖ್ಯೆಯನ್ನು ನೀವು, ಹೆಚ್ಚಾಗುತ್ತದೆ ವಿಂಗಡಿಸುವ ನೀವು ಅರ್ಥ ರನ್ ಸಮಯ ವರ್ಗೀಯವಾಗಿ ಹೆಚ್ಚಿಸುತ್ತದೆ. 

ಆದರೆ ದಕ್ಷತೆ ನಿಮ್ಮ ಕಾರ್ಯಕ್ರಮದ ಪ್ರಮುಖ ಕಾಳಜಿ ಇದ್ದಲ್ಲಿ ಅಥವಾ ನೀವು ಕೇವಲ ಅಂಶಗಳ ಒಂದು ಸಣ್ಣ ಸಂಖ್ಯೆಯ ವಿಂಗಡಿಸುವ ಬಳಸುತ್ತಿದ್ದರೆ, ನೀವು ಬಬಲ್ ವಿಂಗಡಿಸಿ ಉಪಯುಕ್ತ ಏಕೆಂದರೆ ಅದನ್ನು ಅರ್ಥಮಾಡಿಕೊಳ್ಳಲು ಸರಳ ವಿಂಗಡಿಸುವ ಕ್ರಮಾವಳಿಗಳ ಒಂದಾಗಿದೆ ಮತ್ತು ಕೋಡ್ ಗೆ. ಇದು ಒಂದು ಸೈದ್ಧಾಂತಿಕ ಅನುವಾದಿಸಿದನು ಅನುಭವವನ್ನು ಪಡೆಯಲು ಉತ್ತಮ ವಿಧಾನ ನಿಜವಾದ ಕಾರ್ಯನಿರ್ವಹಣೆಯ ಕೋಡ್ ಆಗಿ ಕ್ರಮಾವಳಿ. ಅಲ್ಲದೆ, ಆ ನೀವು ಬಬಲ್ ವಿಂಗಡಿಸಿ ಇಲ್ಲಿದೆ. ವೀಕ್ಷಿಸಲು ಧನ್ಯವಾದಗಳು. CS50.TV