Jump to content
IT-პროგრამირების ფორუმი
Sign in to follow this  
samuraisxmali

სწრაფი დახარისხების ალგორითმი

Recommended Posts

სწრაფი დახარისხების ალგორითმი აგებულია "დაყავი და იბატონე"-ს პრინციპზე. ეს ალგორითმი შემდეგნაირად მუშაობს, პირველ რიგში აირჩევა საყრდენი წერტილი (pivot), შემდეგ იწყება დაყოფა, რიცხვები რომლებიც მეტია მასზე, ლაგდება მის მარჯვნივ, ხოლო ნაკლები რიცხვები მარცხნივ, შემდეგ იგივე ხორციელდება დაყოფილ ნაწილებზე, მანამ, სანამ ბოლომდე არ დალაგდება. ეს სი შარპში კოდის სახით შეგვიძლია ასე ჩავწეროთ:

 public static void Quicksort(IComparable[] elements, int left, int right)        {            int i = left, j = right;            IComparable pivot = elements[(left + right) / 2];             while (i <= j)            {                while (elements[i].CompareTo(pivot) < 0)                {                    i++;                }                 while (elements[j].CompareTo(pivot) > 0)                {                    j--;                }                 if (i <= j)                {                    // Swap                    IComparable tmp = elements[i];                    elements[i] = elements[j];                    elements[j] = tmp;                     i++;                    j--;                }            }             // Recursive calls            if (left < j)            {                Quicksort(elements, left, j);            }             if (i < right)            {                Quicksort(elements, i, right);            }        }     }
IComparable არის ინტერფეისი, რომელსაც უნარი აქვს შეადაროს ნებისმიერი ერთი და იგივე ტიპის ობიექტები, CompareTo() მეთოდის საშუალებით, რის შემდეგაც შეგვიძლია მათი სორტირება მოვახდინოთ. მეთოდს, როგორც ხედავთ, პარამეტრებად აქვს IComparable ელემენტების მასივი და ინტ ტიპის, მარცხენა და მარჯვენა მხარე. შემდეგ აირჩევა საყრდენი წერტილი, ჩვენ გვინდა, რომ ის იყოს შუაში, ამიტომ ელემენტთა მარცხენა და მარჯვენა ნაწილები ჯამდება და იყოფა ორზე. სანამ მარცხენა მხარეს განლაგებული ელემენტები ნაკლებია ან ტოლი მარჯვენაზე, ისინი მატულობენ, მანამ, სანამ საყრდენ წერტილს არ გაუტოლდებიან. იგივე ხდება მარჯვენა მხარესაც, მაგრამ ამ შემთხვევაში ისინი კლებულობენ სანამ საყრდენ წერტილს არ გაუტოლდებიან. შემდეგ, თუ მარცხენა ნაკლებია მარჯვენაზე მასინ ხდება ელემენტთა გაცვლა ისე, რომ მარცხენა ნაწილები მატულობენ, ხოლო მარჯვენა ნაწილები იკლებენ. შემდეგ კი უკვე ხდება რეკურსიული მეთოდის გამოყენება. თუ მარცხენა მხარის ელემენტები ნაკლებია მარჯვენაზე, ამავე მეთოდის გამოყენებით ისინი დალაგდებიან საყრდენი წერტილის მარცხნივ, დანარჩენი მარჯვნივ. ამ ალგორითმის გამოყენება შეგვიძლია სტრიქონების მიმართაც (მე სწორედ ამ მაგალითს მოვიყვან). აი ისიც:
static void Main(string[] args)        {            // შემოგვაქვს დაულაგებელი ასოების მასივი            string[] unsorted = { "z","e","x","c","m","q","a"};             // გამოგვაქვს ისინი კონსოლში            for (int i = 0; i < unsorted.Length; i++)            {                Console.Write(unsorted[i] + " ");            }             Console.WriteLine();             // შემდეგ ვახდენთ სორტირებას ჩვენი მეთოდით            Quicksort(unsorted, 0, unsorted.Length - 1);             // საბოლოოდ კონსოლში ვაწერინებთ დალაგებულ მასივს            for (int i = 0; i < unsorted.Length; i++)            {                Console.Write(unsorted[i] + " ");            }             Console.WriteLine();             Console.ReadLine();        }

შედეგად კონსოლში უნდა დაიწეროს ეს:

z e x c m q a

a c e m q x z

  • Upvote 1

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this  

×