>> ಮಾರ್ಕ್ GROZEN-ಸ್ಮಿತ್: ಹಾಯ್, ನಾನು ಮಾರ್ಕ್ ಮನುಷ್ಯ ಸ್ಮಿತ್ Grozen, ಮತ್ತು ಈ Quicksort ಆಗಿದೆ.
ಕೇವಲ ಅಳವಡಿಕೆಯ ರೀತಿಯ ಮತ್ತು ಬಬಲ್ ಹಾಗೆ ರೀತಿಯ, Quicksort ಒಂದು ಕ್ರಮಾವಳಿ
ಪಟ್ಟಿ ಅಥವಾ ವಸ್ತುಗಳ ಒಂದು ಶ್ರೇಣಿಯನ್ನು ವಿಂಗಡಿಸುವ.
ಸರಳವಾಗಿ ಹೇಳಬೇಕೆಂದರೆ ಊಹಿಸುತ್ತವೆ ಅವಕಾಶ, ಆ ವಿಷಯಗಳನ್ನು ಕೇವಲ ಪೂರ್ಣಾಂಕಗಳ, ಆದರೆ
Quicksort ಕೆಲಸ ತಿಳಿದಿದೆ ಕೇವಲ ಸಂಖ್ಯೆಗಳನ್ನು ಹೆಚ್ಚು.
Quickstart ಒಂದು ಬಿಟ್ ಹೆಚ್ಚು ಸಂಕೀರ್ಣವಾಗಿದೆ ಹೆಚ್ಚು ಅಳವಡಿಕೆ ಅಥವಾ ಬಬಲ್, ಆದರೆ ಇದು
ಹೆಚ್ಚು ಪರಿಣಾಮಕಾರಿ ಹೆಚ್ಚಿನ ಸಂದರ್ಭಗಳಲ್ಲಿ.
ಎರಡನೇ ನಿರೀಕ್ಷಿಸಿ.
ಅವರು ಕೇವಲ "ಅತ್ಯಂತ ಸೇ ಡಿಡ್ ಸಂದರ್ಭಗಳಲ್ಲಿ, "ಅಲ್ಲ" ಎಲ್ಲಾ "?
ಸ್ವಾರಸ್ಯವೆಂದರೆ, ಯಾವುದೇ.
ಎಲ್ಲಾ ಸಂದರ್ಭಗಳಲ್ಲಿ ಒಂದೇ.
ಈ ಬಗ್ಗೆ ಚಿಂತಿಸಬೇಡಿ ನೀವು ವೇಳೆ ಇನ್ನೂ ದೊಡ್ಡ ಒ ಸಂಕೇತನ ಕಾಣಬಹುದು, ಆದರೆ ಮಾಡಿಲ್ಲ
Quicksort ಒ (N ವರ್ಗ) ಕ್ರಮಾವಳಿ ಕೆಟ್ಟ, ಕೇವಲ ಹಾಗೆ
ಅಳವಡಿಕೆ ಅಥವಾ ಬಬಲ್ ರೀತಿಯ.
ಆದಾಗ್ಯೂ, ಇದು ಸಾಮಾನ್ಯವಾಗಿ ಹೆಚ್ಚು ವರ್ತಿಸುತ್ತದೆ ಹಳೆಯ ಅನಲಾಗ್ ಮೀ ಅಲ್ಗಾರಿದಮ್ ಹಾಗೆ.
ಏಕೆ?
ನಾವು ನಂತರ ಮರಳಿ ಆ ಪಡೆಯುತ್ತೀರಿ.
ಆದರೆ ಈಗ, ಕೇವಲ ಕಲಿಯೋಣ Quicksort ಹೇಗೆ ಕೆಲಸ.
>> ಆದ್ದರಿಂದ ಅವರ ಈ Quicksorting ಸಂಚರಿಸಲು ಅವಕಾಶ ಚಿಕ್ಕ ಪೂರ್ಣಾಂಕಗಳ ರಚನೆಯ
ದೊಡ್ಡ ಗೆ.
ಇಲ್ಲಿ ನಾವು, ಪೂರ್ಣಾಂಕಗಳ 6 5, 1, 3, 8, 4, 7, 9 ಮತ್ತು 2.
ಮೊದಲ, ನಾವು ಅಂತಿಮ ಅಂಶ ಆಯ್ಕೆ ಈ ರಚನೆಯ - ಈ ಸಂದರ್ಭದಲ್ಲಿ, ಎರಡು -
ಮತ್ತು "ಪಿವೋಟ್." ಕರೆ ಮುಂದೆ, ನಾವು ಎರಡು ವಿಷಯಗಳನ್ನು ನೋಡಲು ಆರಂಭಿಸಲು -
ಒಂದು, ನಾನು ನೋಡಿ ಮಾಡುತ್ತೇವೆ ಕಡಿಮೆ ಸೂಚ್ಯಂಕ, ಹಕ್ಕನ್ನು ಉಳಿದರು ಎಂದು
ಗೋಡೆಯ, ಮತ್ತು, ಎರಡು, ಅತ್ಯಂತ ಎಡಗಡೆಯ ನಾನು "ಪ್ರಸ್ತುತ ಕರೆ ಮಾಡುತ್ತೇವೆ ಇದು ಅಂಶ,
ಅಂಶ. "ನಾವು ಏನು ನೀನು ಇತರ ಎಲ್ಲಾ ಅಂಶಗಳನ್ನು, ನೋಡಲು
ಪಿವೋಟ್ ಹೆಚ್ಚು, ಮತ್ತು ಎಲ್ಲಾ ಅಂಶಗಳನ್ನು ಹಾಕಲು ಗೆ ಪಿವೋಟ್ ಚಿಕ್ಕದಾಗಿದೆ
ಗೋಡೆಯ ಎಡಭಾಗದ ಮತ್ತು ಎಲ್ಲಾ ಗೆ ಪಿವೋಟ್ ದೊಡ್ಡದಾಗಿರುತ್ತದೆ
ಗೋಡೆಯ ಬಲ.
ನಂತರ, ಅಂತಿಮವಾಗಿ, ನಾವು ಪಿವೋಟ್ ಡ್ರಾಪ್ ವಿಲ್ ಬಲ ನಡುವೆ ಹಾಕಲು ಗೋಡೆಯ ಮೇಲೆ
ಇದು ಚಿಕ್ಕದಾಗಿದೆ ಎಲ್ಲಾ ಸಂಖ್ಯೆಗಳು ಮತ್ತು ಎಲ್ಲಾ ಸಂಖ್ಯೆಗಳು ದೊಡ್ಡ.
>> ಆದ್ದರಿಂದ ನ ಹಾಗೆ ಅವಕಾಶ.
2 ಎತ್ತಿಕೊಂಡು, ಗೋಡೆಯ ಪುಟ್ ಆರಂಭದಲ್ಲಿ, ಮತ್ತು 6 "ಪ್ರಸ್ತುತ ಕರೆ
ಅಂಶ. "ನಾವು ನೋಡಲು ಬಯಸುವ ನಮ್ಮ ಪ್ರಸ್ತುತ ಅಂಶ, 6.
ಮತ್ತು ಅದು ಹೆಚ್ಚಿನ ರಿಂದ 2, ನಾವು ಅಲ್ಲಿ ಬಿಡುತ್ತಾರೆ
ಗೋಡೆಯ ಬಲ.
ನಂತರ, ನಾವು 5 ನೋಡಲು ತೆರಳಿ ನಮ್ಮ ಪ್ರಸ್ತುತ ಅಂಶ ಮತ್ತು ನೋಡಿ ಈ
, ಮತ್ತೆ, ಪಿವೋಟ್ ದೊಡ್ಡದಾಗಿರುತ್ತದೆ, ಆದ್ದರಿಂದ ನಾವು ಇದು ಬಲ ಮೇಲೆ ಅಲ್ಲಿ ಬಿಡುತ್ತಾರೆ
ಗೋಡೆಯ ಒಂದು ಭಾಗದಲ್ಲಿ.
ನಾವು ತೆರಳಿ.
ನಮ್ಮ ಪ್ರಸ್ತುತ ಅಂಶ ಈಗ 1, ಮತ್ತು - ಓಹ್.
ಈ ಈಗ ಭಿನ್ನವಾಗಿದೆ.
ಪ್ರಸ್ತುತ ಅಂಶ ಈಗ ಚಿಕ್ಕದಾಗಿದೆ ಪಿವೋಟ್, ಆದ್ದರಿಂದ ನಾವು ಅದನ್ನು ಹಾಕಲು ಬಯಸುವ
ಗೋಡೆಯ ಎಡ.
ಇದನ್ನು ಮಾಡಲು, ಕೇವಲ ಬದಲಾಯಿಸಲು ಅವಕಾಶ ಕಡಿಮೆ ಸೂಚ್ಯಂಕ ಪ್ರಸಕ್ತ ಅಂಶ
ಕೇವಲ ಗೋಡೆಯ ಬಲಭಾಗದಲ್ಲಿ ಕುಳಿತು.
ಈಗ, ನಾವು ಒಂದು ಸೂಚ್ಯಂಕ ಗೋಡೆಯ ಸರಿಸಲು ಆದ್ದರಿಂದ 1 ಎಡ
ಈಗ ಗೋಡೆಯ ಬದಿಯಲ್ಲಿ.
>> ನಿರೀಕ್ಷಿಸಿ.
ನಾನು ಮೇಲೆ ಅಂಶಗಳನ್ನು ಮಿಶ್ರಣ ಗೋಡೆಯ ಬಲಭಾಗದ, ನಾನು ಮಾಡಲಿಲ್ಲ?
ಚಿಂತಿಸಬೇಡಿ.
ಉತ್ತಮ ಇಲ್ಲಿದೆ.
ನಾವು ಈಗ ಕಾಳಜಿ ಮಾತ್ರ ವಿಷಯ ಎಂದು ಈ ಎಲ್ಲಾ ಅಂಶಗಳನ್ನು
ಗೋಡೆಯ ಬಲ ದೊಡ್ಡದಾಗಿರುತ್ತವೆ ಪಿವೋಟ್ ಹೆಚ್ಚು.
ಯಾವುದೇ ವಾಸ್ತವಿಕ ಸಲುವಾಗಿ ಇನ್ನೂ ಭಾವಿಸಲಾಗಿದೆ.
>> ಈಗ, ಮತ್ತೆ ಬೇರ್ಪಡಿಸುವ.
ಆದ್ದರಿಂದ ನಾವು ನೋಡುವ ಮುಂದುವರೆಯಲು ಅಂಶಗಳನ್ನು ಉಳಿದ.
ಮತ್ತು ಈ ಸಂದರ್ಭದಲ್ಲಿ, ನಾವು ಇವೆ ಎಂದು ನೋಡಿ ಬೇರೆ ಅಂಶಗಳನ್ನು ಕಡಿಮೆ
ಪಿವೋಟ್, ಆದ್ದರಿಂದ ನಾವು ಅವರನ್ನು ಎಲ್ಲಾ ಬಿಟ್ಟು ಗೋಡೆಯ ಬಲಭಾಗದ.
ಅಂತಿಮವಾಗಿ, ನಾವು ಪ್ರಸ್ತುತ ಅಂಶ ಪಡೆಯಲು ಮತ್ತು ಇದು ಪಿವೋಟ್ ಎಂದು ನೋಡಿ.
ಈಗ, ನಾವು ಎರಡು ಎಂದರ್ಥ ರಚನೆಯ ಮೊದಲ ಎಂಬ ವಿಭಾಗಗಳು
ಪಿವೋಟ್ ಮೇಲೆ ಮತ್ತು ಎಡಭಾಗದಲ್ಲಿ ಸಣ್ಣ ಗೋಡೆಯ, ಮತ್ತು ಎರಡನೇ ಅತಿ
ಗೆ ಪಿವೋಟ್ ದೊಡ್ಡದಾಗಿರುತ್ತದೆ ಗೋಡೆಯ ಬಲಭಾಗದ.
ನಾವು ನಡುವಿನ ಪಿವೋಟ್ ಅಂಶ ಹಾಕಲು ಬಯಸುವ ಎರಡು, ಮತ್ತು ನಾವು ತಿಳಿದಿರುವ ಮಾಡುತ್ತೇವೆ
ಪಿವೋಟ್ ಅದರ ಬಲ ಎಂದು ಅಂತಿಮ ಪ್ರತಿಗಳ ಸ್ಥಾನ.
ನಾವು ಮೊದಲ ಅಂಶ ಬದಲಾಯಿಸಲು ಪಿವೋಟ್ ಗೋಡೆಯ ಬಲಭಾಗದ
ಮತ್ತು ನಾವು ತಿಳಿದಿರುವ ಪಿವೋಟ್ ನ ಅದರ ಸರಿಯಾದ ಸ್ಥಾನದಲ್ಲಿ.
>> ನಾವು ಈ ಪ್ರಕ್ರಿಯೆಯನ್ನು ಪುನರಾವರ್ತಿಸುವಂತೆ subarrays ಬಿಟ್ಟು ಪಿವೋಟ್ ಬಲ.
ಕಳೆದ subarray ಒಂದೇ ಕಾರಣ ಅಂಶ ದೀರ್ಘ, ನಾವು ಈಗಾಗಲೇ ಗೊತ್ತು
ಪ್ರತಿಗಳ ಹೇಗೆ ನೀವು ಹೊರಗೆ ಏಕೆಂದರೆ ನೀವು ಕೇವಲ ಒಂದು ಅಂಶ ಇಂತಹ ಆದೇಶ?
Subarray ಬಲಭಾಗದ, ನಾವು ಪಿವೋಟ್ ಗೋಡೆಯ 5, ಮತ್ತು ನೋಡಿ
ಕೇವಲ 6 ಉಳಿದಿದ್ದು.
ಮತ್ತು ಪ್ರಸ್ತುತ ಅಂಶ ಸಹ 6 ಎಂದು ಆರಂಭವಾಗುತ್ತದೆ.
ಆದ್ದರಿಂದ 6 5 ಹೆಚ್ಚಾಗಿದೆ.
ಅದರ ಮೇಲೆ ಅಲ್ಲಿ ನಾವು ಬಿಡುತ್ತಾರೆ ಗೋಡೆಯ ಬಲಭಾಗದ.
ಈಗ, ಮೇಲೆ ಚಲಿಸುವ, 3 5 ಕಡಿಮೆ.
ನಾವು ಮೊದಲ ಅಂಶ ಅದನ್ನು ಬದಲಾಯಿಸಲು ಗೋಡೆಯ ಸರಿಯಾದ.
ಈಗ, ನಾನು ಒಂದು ಗೋಡೆಯ ತೆರಳಿದರು.
ಈಗ, 8 ಸ್ಥಳಾಂತರಗೊಳ್ಳುವ.
8, 5 ಹೆಚ್ಚಾಗಿದೆ ಮತ್ತು ಆದ್ದರಿಂದ ನಾವು ಅದನ್ನು ಬಿಟ್ಟು.
4 ಕಡಿಮೆ 5, ಆದ್ದರಿಂದ ನಾವು ಅದನ್ನು ಬದಲಾಯಿಸಲು.
ಮತ್ತು ಮೇಲೆ.
>> ನಾವು ಮೇಲೆ ಪ್ರಕ್ರಿಯೆಯನ್ನು ಪುನರಾವರ್ತಿಸುವಂತೆ ಪ್ರತಿ ಬಾರಿ ರಚನೆಯ ಎಡ ಮತ್ತು ಬಲ ಭಾಗದಲ್ಲಿರುವ. ನಾವು
ಪಿವೋಟ್ ಆಯ್ಕೆ ಮತ್ತು ಹೋಲಿಕೆಗಳನ್ನು ಮಾಡಲು ಮತ್ತು ಬಿಟ್ಟು ಇನ್ನೊಂದು ಮಟ್ಟದ ರಚಿಸಲು ಮತ್ತು
ಬಲ subarrays.
ಈ ಪುನರಾವರ್ತಿತ ಕರೆಯು ರವರೆಗೆ ಮುಂದುವರಿಯುತ್ತದೆ ನಾವು ಹೇಳುತ್ತಾರೆ ಕೊನೆಯಲ್ಲಿ ತಲುಪಲು
ಒಳಗೆ ಒಟ್ಟಾರೆ ರಚನೆಯ ವಿಂಗಡಿಸಿದರು ಉದ್ದ 1 ಕೇವಲ subarrays.
ಅಲ್ಲಿಂದ ನಾವು ರಚನೆಯ ಪ್ರತ್ಯೇಕಿಸಲ್ಪಡುತ್ತವೆ ತಿಳಿದಿದೆ ಪ್ರತಿ ಅಂಶ ಏಕೆಂದರೆ, ನಲ್ಲಿ
ಹಂತದಲ್ಲಿ, ಪಿವೋಟ್ ಮಾಡಲಾಗಿದೆ.
ಅರ್ಥಾತ್, ಪ್ರತಿ ಅಂಶ, ಎಲ್ಲಾ ಎಡ ಸಂಖ್ಯೆಗಳು ಕಡಿಮೆ ಇವೆ
ಮೌಲ್ಯಗಳು ಮತ್ತು ಎಲ್ಲಾ ಸಂಖ್ಯೆಗಳು ಬಲ ಮೌಲ್ಯಗಳನ್ನು ಹೆಚ್ಚಿನ ಹೊಂದಿವೆ.
>> ಈ ವಿಧಾನವು ಬಹಳ ಚೆನ್ನಾಗಿ ಕೆಲಸ ವೇಳೆ ಆಯ್ಕೆ ಪಿವೋಟ್ ಮೌಲ್ಯವನ್ನು
ಸುಮಾರು ಮಧ್ಯದಲ್ಲಿ ಪಟ್ಟಿ ಮೌಲ್ಯಗಳ ವ್ಯಾಪ್ತಿಯನ್ನು.
ನಾವು ಸರಿಸಲು ನಂತರ ಈ, ಅರ್ಥ ಅನೇಕ ಬಗ್ಗೆ ಸುಮಾರು ಅಂಶಗಳನ್ನು,
ಪಿವೋಟ್ ಎಡ ಅಂಶಗಳನ್ನು ಬಲಕ್ಕೆ ಇರುವುದರಿಂದ.
ಮತ್ತು ಡಿವೈಡ್ ಮತ್ತು ವಶಪಡಿಸಿಕೊಳ್ಳಲು ಪ್ರಕೃತಿ Quicksort ಅಲ್ಗಾರಿದಮ್ ನಂತರ ತೆಗೆದುಕೊಳ್ಳಲಾಗುತ್ತದೆ
ಪೂರ್ಣ ಲಾಭ.
ಈ ಒ ಒಂದು ರನ್ಟೈಮ್ ಸೃಷ್ಟಿಸುತ್ತದೆ (N ಲಾಗ್ N,) ನಾವು ಎನ್ ಮೈನಸ್ 1 ಎನ್ ಏಕೆಂದರೆ
ಪ್ರತಿ ಪೀಳಿಗೆಯ ಮತ್ತು ದಾಖಲೆ ಮೇಲೆ ಹೋಲಿಕೆಗಳು ನಾವು ಪಟ್ಟಿ ವಿಭಾಗಿಸುತ್ತದೆ, N ಏಕೆಂದರೆ
N ಬಾರಿ ದಾಖಲೆ.
ಆದರೆ, ಕೆಟ್ಟ ಸಂದರ್ಭಗಳಲ್ಲಿ, ಈ ಕ್ರಮಾವಳಿಯು O (N ಮಾಡಬಹುದು
ವರ್ಗ.) ಪ್ರತಿ ಪೀಳಿಗೆಯ ಮೇಲೆ ಪಕ್ಷ, ಪಿವೋಟ್ ಕೇವಲ ಎಂದು ಸಂಭವಿಸುತ್ತದೆ
ಚಿಕ್ಕ ಅಥವಾ ದೊಡ್ಡ ನಾವು ವಿಂಗಡಿಸುವ ನೀವು ಸಂಖ್ಯೆಗಳು.
ಈ ಪಟ್ಟಿಯನ್ನು ಒಡೆಯುವ ಅರ್ಥ ಬಾರಿ ಮತ್ತು ತಯಾರಿಕೆ ಎನ್ ಮೈನಸ್ 1 ಎನ್
ಹೋಲಿಕೆಗಳು ಪ್ರತಿಯೊಂದು ಸಮಯ.
ಹೀಗಾಗಿ, n ನ ಒ ವರ್ಗ.
>> ನಾವು ಹೇಗೆ ವಿಧಾನ ಸುಧಾರಿಸಬಹುದು?
ವಿಧಾನ ಸುಧಾರಿಸಲು ಒಂದು ಉತ್ತಮ ದಾರಿ ಸಂಭವನೀಯತೆ ಮೇಲೆ ಕತ್ತರಿಸಿ ಎಂದು
ರನ್ಟೈಮ್ ಇದುವರೆಗೆ ವಾಸ್ತವವಾಗಿ n ನ ಒ ವರ್ಗ.
ಈ ಕೆಟ್ಟ, ಕೆಟ್ಟ ಸಂದರ್ಭಗಳಲ್ಲಿ ನೆನಪಿಡಿ ಮಾತ್ರ ಸಂಭವಿಸಬಹುದು ಮಾಡಿದಾಗ
ಆಯ್ಕೆ ಪಿವೋಟ್ ಯಾವಾಗಲೂ ಅತಿ ಅಥವಾ ರಚನೆಯ ಕಡಿಮೆ ಮೌಲ್ಯ.
ಈ ತೀರುತ್ತದೆ ಕಡಿಮೆ ಖಚಿತಪಡಿಸಿಕೊಳ್ಳಲು, ನಾವು ಅದಕ್ಕೆ ಪಿವೋಟ್ ಕಾಣಬಹುದು
ಅನೇಕ ಅಂಶಗಳನ್ನು ಮತ್ತು ಆಯ್ಕೆ ಸರಾಸರಿ ಮೌಲ್ಯವನ್ನು ತೆಗೆದುಕೊಳ್ಳುವ.
>> ನನ್ನ ಹೆಸರು ಮಾರ್ಕ್ Grozen ಸ್ಮಿತ್ ಆಗಿದೆ ಮತ್ತು ಈ CS50 ಹೊಂದಿದೆ.
>> ಸರಳವಾಗಿ ಹೇಳಬೇಕೆಂದರೆ ಊಹಿಸುತ್ತವೆ ಅವಕಾಶ, ಆ ವಿಷಯಗಳನ್ನು ಕೇವಲ ಪೂರ್ಣಾಂಕಗಳ, ಆದರೆ
ಎಂದು Quicksert ಗೊತ್ತಿಲ್ಲ -
Quicksert?
ಕ್ಷಮಿಸಿ.
>> ಇಲ್ಲಿ ನಾವು ಪೂರ್ಣಾಂಕಗಳ ಹೊಂದಿವೆ 6, 5, 1, 3, 8, 4, 9.
>> ಸ್ಪೀಕರ್ 1: ರಿಯಲಿ?
>> ಸ್ಪೀಕರ್ 2: ನಿಲ್ಲಿಸುವುದಿಲ್ಲ.
>> ಸ್ಪೀಕರ್ 1: ರಿಯಲಿ?