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

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

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

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

ალგორითმი

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

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

• თარგი:Cite web – graphical demonstration
• თარგი:Cite web
• Open Data Structures – Section 11.1.2 – Quicksort, Pat Morin
• Interactive illustration of Quicksort, with code walkthrough