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

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

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 ರಲ್ಲಿ ಪ್ರಕಟಿಸಿದರು. ಇದು ಇನ್ನೂ ವಿಂಗಡಿಸಲು ಸಾಮಾನ್ಯವಾಗಿ ಬಳಸುವ ಅಲ್ಗಾರಿದಮ್ ಆಗಿದೆ. ಒಟ್ಟಾರೆಯಾಗಿ, ಇದು ಯಾದೃಚ್ಛಿಕ ದತ್ತಾಂಶಕ್ಕಾಗಿ, ವಿಶೇಷವಾಗಿ ದೊಡ್ಡ ವಿತರಣೆಗಳಲ್ಲಿ, ವಿಲೀನಗೊಂಡ ವಿಂಗಡಣೆ ಮತ್ತು ಸಂಗ್ರಹಣೆಗಿಂತ ಸ್ವಲ್ಪ ವೇಗವಾಗಿರುತ್ತದೆ.

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

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