ಕ್ವಿಕ್ ಸಾರ್ಟ್

ಕ್ವಿಕ್ ಸಾರ್ಟ್

Animated visualization of the quicksort algorithm. The horizontal lines are pivot values.
ಕ್ಲಾಸ್	Sorting algorithm
ಪ್ರತಿಕೂಲ ಸ್ಥಿತಿ ವಿಶ್ಲೇಷಣೆ	$O(n^{2})$
ಆಪ್ಟಿಮಲ್ ಷರತ್ತು ವಿಶ್ಲೇಷಣೆ	$O(n\log n)$ (simple partition) or $O(n)$ (three-way partition and equal keys)
ಸರಾಸರಿ ಸಾಧನೆ	$O(n\log n)$
ಕೆಟ್ಟ-ಸ್ಥಳದ ಸಂಕೀರ್ಣತೆ	$O(n)$ auxiliary (naive) $O(\log n)$ auxiliary (Hoare 1962)

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

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

ಕ್ವಿಕ್‌ಸೋರ್ಟ್ ಒಂದು ಹೋಲಿಕೆ ವಿಂಗಡಣೆಯಾಗಿದೆ, ಅಂದರೆ "ಕಡಿಮೆ" ಸಂಬಂಧವನ್ನು (ಔಪಚಾರಿಕವಾಗಿ, ಒಟ್ಟು ಕ್ರಮ ) ವ್ಯಾಖ್ಯಾನಿಸಲಾದ ಯಾವುದೇ ಪ್ರಕಾರದ ವಸ್ತುಗಳನ್ನು ಇದು ವಿಂಗಡಿಸಬಹುದು. ಇದು ಹೋಲಿಕೆ ಆಧಾರಿತ ವಿಂಗಡಣೆಯಾಗಿದೆ ಏಕೆಂದರೆ a ಮತ್ತು b ಅಂಶಗಳನ್ನು ಹಿಂದಿನ ಹೋಲಿಕೆ-ಫಲಿತಾಂಶಗಳ ಟ್ರಾನ್ಸಿಟಿವ್ ಕ್ಲೋಸರ್‌ನಲ್ಲಿ ಅವುಗಳ ಸಾಪೇಕ್ಷ ಕ್ರಮವನ್ನು ಪಡೆದಿದ್ದರೆ ಮಾತ್ರ ಬದಲಾಯಿಸಲಾಗುತ್ತದೆ. ಕ್ವಿಕ್‌ಸೋರ್ಟ್‌ನ ಹೆಚ್ಚಿನ ಅನುಷ್ಠಾನಗಳು ಸ್ಥಿರವಾಗಿರುವುದಿಲ್ಲ, ಅಂದರೆ ಸಮಾನ ವಿಂಗಡಣೆಯ ಐಟಂಗಳ ಸಾಪೇಕ್ಷ ಕ್ರಮವನ್ನು ಸಂರಕ್ಷಿಸಲಾಗಿಲ್ಲ.