დელეგატები (3/5) - BubbleSorter ალგორითმი

დღეს მე მინდა ყურადღება გავამახვილო ერთ-ერთ ძლიერ და პოპულარულ ალგორითმზე, რომელიც ჩემი აზრით საჭიროა, რომ ყველამ იცოდეს და ესმოდეს მისი მუშაობის პრინციპი ამ სფეროში. ამ ალგორითმს ეწოდება BubbleSorter ალგორითმი და ვაპირებ მის გარჩევას და შემდეგ უკვე მოდიფიცირებას დელეგატებისა და ზოგადი ტიპის გამოყენებით. ვფიქრობ, რომ საკმაოდ საინტერესო გაკვეთილი უნდა გამოვიდეს და მაშინ დავიწყებ.

მე შევქმენი კლასი BubbleSorter.cs, რომელიც შეიცავს ორ ძირითად მეთოდს, Sort და Sort<T>. ამ ორიდან პირველი თავისი ყველაზე პრიმიტიული გაგებით ალაგებს int ტიპის მასივს. მაგალითისთვის, რომ ავიღოთ ამ ტიპის მნიშვნელობები და მივაწოდოთ ალგორითმს - 0, 5, 6, 2, 1, ჩემს მიერ დაწერილი ეს ალგორითმი გადაალაგებს წევრებს და მოგვცემს მასივს, რომელშიც წევრების მიმდევრობა იქნება - { 0, 1, 2, 5, 6 }.

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

public static void Sort(List<int> sortArray)

        {

            bool swapped = true;

            do

            {

                swapped = false;

                for (int i = 0; i < sortArray.Count - 1; i++)

                {

                    if (sortArray[i] < sortArray[i+1])

                    {

                        int temp = sortArray[i];

                        sortArray[i] = sortArray[i + 1];

                        sortArray[i + 1] = temp;

                        swapped = true;

                    }

                }

            }while(swapped);

        }

ეს მეთოდი არის კლას BubbleSorter ის წევრი. ამ მეთოდის გამოყენებით საკმაოდ მარტივია ციფრების დალაგება. მაგრამ რა ვქმნათ, როდესაც გვაქვს ისეთი მასივი, რომელშიც თავმოყრილია არა მარტო int ტიპი, არამედ მომხმარებლის მიერ განსაზღვრული არასტანდარტული ტიპი. მაშინ ჩემს მიერ შემოთავაზებული ალგორითმი თავის ძალას პირველივე გაშვებაზე დაკარგავს და შეცდომასაც ამოაგდებს. ამისთვის არსებობს, გამოსავალი და ეს გამოსავალი დევს დელეგატისა და ზოგადი (Generic Type) ტიპის გამოყენებაზე.

მე შემიძლია შევქმნა მეთოდი Sort<T>, რომლისთვისაც მისაღები იქნება T ტიპი. მათთვის ვინც ვერ ხვდება ამჟამად რა არის T ტიპი, ვიტყვი, რომ T ტიპი არის ისეთივე ცვლადი, როგორიც int x დან x. ანუ <T> ასეთ ფრჩხილებში ნიშნავს, რომ T ს მაგივრად შეიძლება „ჩაჯდეს“ int, string, bool, Person (რომელსაც ქვემოთ განვსაზღვრავ) და ნებისმიერი სტანდარტული თ მომხმარებლის მიერ შექმნილი ტიპი. ეს თვისება C# ძალიან მოქნილს ხდის.

შედარებისთვის საჭიროა ისეთი მეთოდი, რომელიც იღებს ორ T ტიპის არგუმენტს და აბრუნებს bool ტიპის ცვლადს. ამისთვის კი გამოვიყენებ დელეგატს, რომელიც რაღაც მნიშვნელობას აბრუნებს -> Func<T1, T2, bool>. რახან T1 = T2, მათ ერთი და იმავე ასოთი აღვნიშნავ T(T ს ნაცვლად შეიძლება გამოვიყენოთ A, B, C, D და ასე შემდეგ).

ჩემი ზოგადი ტიპის მეთოდის სახე კი ასეთი იქნება

public static void Sort<T>(List<T> SortArray, Func<T, T, bool> comparison)

        {

            bool swapped = true;

            do

            {

                swapped = false;

                for (int i = 0; i < SortArray.Count - 1; i++)

                {

                    if (comparison(SortArray[i + 1], SortArray[i]))

                    {

                        T temp = SortArray[i];

                        SortArray[i] = SortArray[i + 1];

                        SortArray[i + 1] = temp;

                        swapped = true;

                    }

                }

            } while (swapped);

        }

ამ მეთოდის გამოსაყენებლად საჭიროა განვსაზღვროთ სხვა კლასი, რომელიც საშუალებას მოგვცემს დავასახლოთ მასივი ამ კლასის ტიპის ობიექტებით და შემდეგ დავალაგოთ ისინი რაიმე პარამეტრის მიხედვით.

public class Person

    {

        public string Name { get; private set; }

        public int Wage { get; private set; }

        public Person(string pName, int pWage)

        {

            this.Name = pName;

            this.Wage = pWage;

        }

        public override string ToString()

        {

            return string.Format("{0}, {1}", Name, Wage);

        }

        public static bool WageComparison(Person p1, Person p2)

        {

            return p1.Wage < p2.Wage;

        }

    }

ეს არის კლასი Person, რომელსაც გააჩნია სახელი და ანაზღაურება. მასში ვაკეთებ ToString() მეთოდის ოვერრაიდინგს, რაც იმას ნიშნავს, რომ ToString() მეთოდის გამოძახებისას, ნებისმიერ მის ობიექტზე, ის დააბრუნებს სახელს + ანაზღაურებას. ასევე მაქვს სტატიკური მეთოდი, რომელიც ანაზღაურებას ადარებს, თავისივე ტიპის ობიექტებისათვის.

static void Main(string[] args)

        {

            List<Person> persons = new List<Person>();

            persons.Add(new Person("Bugs Bunny", 20000));

            persons.Add(new Person("Elmer Fudd", 10000));

            persons.Add(new Person("Daffy Duck", 25000));

            persons.Add(new Person("Wile Coyote", 1000000));

            persons.Add(new Person("Foghorn Leghorn", 23000));

            persons.Add(new Person("RoadRunner", 50000));

            BubbleSorter.Sort(persons, Person.WageComparison);

            foreach (var person in persons)

                Console.WriteLine(person.ToString());

            Console.ReadKey();

        }

ამ კოდის საშუალებით კი პირველ ნაწილში ვქმნით სიას, რომელიც არის Person ტიპის და შემდეგ ამ სიას ვატარებთ Sort მეთოდის არგუმენტად. დაყოფის შემდეგ გამოგვაქვს შედეგები.

Sort<T> ალგორითმს კიდევ ერთი მოდიფიკაცია აქვს, რაც იმაში მდგომარეობს, რომ შეგვიძლია List<T> ის ნაცვლად რეალური მასივი გავატაროთ არგუმენტად, როგორიცაა

Person[] persons =

            {

                new Person("Bugs Bunny", 20000),

                new Person("Elmer Fudd", 10000),

                new Person("Daffy Duck", 25000),

                new Person("Wile Coyote", 1000000),

                new Person("Foghorn Leghorn", 23000),

                new Person("RoadRunner", 50000)

            };

მხოლოდ უნდა შევცვალოთ Sort<T> ალგორითმის განსაზღვრის ფორმაც შემდეგნაირად

public static void Sort<T>(IList<T> SortArray, Func<T, T, bool> comparison)

სადაც List<T> კლასის ნაცვლად გამოვიყენებ IList<T> ინტერფეისს.

ჩემს მიერ განსაზღვრული დამხმარე კლასები.