სწრაფი სორტირება

სწრაფი სორტირება — დახარისხების ეფექტიანი ალგორითმი, რომელიც 1959 წელს შეიმუშავა ბრიტანელმა კომპიუტერულმა მეცნიერმა ტონი ჰოარმა. ეს ალგორითმი დღესდღეობით ყველაზე გამოყენებადი ალგორითმია. მიჩნეულია, რომ კარგად იმპლემენტირებული სწრაფი სორტირების ალგორითმი 2-3-ჯერ სწრაფია მის მთავარ კონკურენტებზე,შერწყმით სორტირებასა და გროვის სორტირებაზე.

ალგორითმის ანიმაციური ვიზუალიზაცია.

სწრაფი სორტირების მათემატიკური ანალიზი აჩვენებს, რომ საშუალოდ, ეს ალგორითმი $O(n\log n)$ შედარებას აკეთებს. თუმცა, უარეს შემთხვევას თუ განვიხილავთ, ის თითქოს არაფრითაა განსაკუთრებული, რადგან $O(n^{2})$-ში შედარებას აკეთებს. უნდა აღვნიშნოთ, რომ ეს მომენტი ძალიან იშვიათია, სწორედ ამიტომაა ის ყველაზე ეფექტიანი.

ალგორითმი

სწრაფი დახარისხების ალგორითმი „დაჰყავი და იბატონეს“ პრინციპით მუშაობს. ის ჯერ აირჩევს კონკრეტულ ელემენტს მოცემულ სიმრავლეში, შემდეგ სიმრავლეს სამ ნაწილად დაჰყოფს, არჩეულ ელემენტებზე ნაკლებ, ტოლ და მეტ ელემენტებად. ალგორითმი რეკურსიულად მოქმედებს ამ პრინციპით.

რესურსები ინტერნეტში

• Animated Sorting Algorithms: Quick Sort. ციტირების თარიღი: 25 November 2008 – graphical demonstration
• Animated Sorting Algorithms: Quick Sort (3-way partition). ციტირების თარიღი: 25 November 2008
• Open Data Structures – Section 11.1.2 – Quicksort, Pat Morin
• Interactive illustration of Quicksort, with code walkthrough