Seçmə ilə çeşidləmə

7.1 Seçimlə Sıralama Təklifi

Seçimlə Sıralama (Selection Sort) — bu, bir array-dən sıralanmamış hissədən ən kiçik elementi tapıb, onu o hissənin ilk elementi ilə dəyişən bir sıralama alqoritmidir. Bu proses bütün array sıralanana qədər təkrarlanır.

İşləmə Prinsipi:

1. Array-ın ilk elementindən başlayırıq.
2. Sıralanmamış hissənin qalanında ən kiçik elementi tapırıq.
3. Ən kiçik elementi və sıralanmamış hissənin ilk elementini dəyişirik.
4. Bütün array sıralanana qədər bu prosesi növbəti element üçün təkrar edirik.

Addım-addım proses

1. Array-ın ən kiçik elementini tapıb, onu ilk elementlə dəyişdiririk.
2. Qalan array üçün prosesi təkrar edirik (ikinci elementdən başlayaraq).
3. Bütün array sıralanana qədər prosesi davam etdiririk.

Seçimlə Sıralamanın Zaman və Məkan Çətinliyi

Zaman Çətinliyi:

• Ən pis halda: O(n^2) — elementlər əks ardıcıllıqda və ya təsadüfi yerləşdirilibsə baş verir.
• Orta halda: O(n^2) — elementlər təsadüfi ardıcıllıqla yerləşdirilibsə baş verir.
• Ən yaxşı halda: O(n^2) — array artıq sıralanmış olsa belə, alqoritm yenə də eyni müqayisələri yerinə yetirir.

Məkan Çətinliyi:

O(1) — çünki alqoritm əlavə yaddaş üçün sabit sayda dəyişənlərdən istifadə edir (yalnız müvəqqəti dəyərləri saxlamaq üçün bir neçə dəyişən).

7.2 Seçimləmə ilə çeşidləmə alqoritminin realizasiyası

Alqoritmin realizasiyası çox sadədir:

Addım 1: bütün elementlər arasında ən kiçik elementi tapıb onun yerini birinci ilə dəyişirik.

Addım 2: birinci elementdən başqa bütün elementlər arasında ən kiçik elementi tapıb onun yerini ikincil ilə dəyişirik.

Addım 3: birinci və ikinci elementdən başqa bütün elementlər arasında ən kiçik elementi tapıb onun yerini üçüncü ilə dəyişirik.

Python-da realizasiya:

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        # Çeşidlənməmiş hissədə ən kiçik elementi tapırıq min_idx = i for j in range(i + 1, n): if arr[j] < arr[min_idx]: min_idx = j
        # Tapılmış ən kiçik elementi çeşidlənməmiş hissənin ilk elementi ilə dəyişirik arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr  # Çeşidlənmiş array-i qaytarırıq

# İstifadə nümunəsi:
arr = [64, 25, 12, 22, 11]
sorted_arr = selection_sort(arr)
print("Çeşidlənmiş array:", sorted_arr)
# Çıxış: Çeşidlənmiş array: [11, 12, 22, 25, 64]

Alqoritmin iş nümunəsi:

1. Birinci keçid (i = 0):
   1. Çeşidlənməmiş hissədə minimal elementi (11) tapırıq [64, 25, 12, 22, 11].
   2. 11 ilə 64-ü dəyişirik.
   3. Array: [11, 25, 12, 22, 64]
2. İkinci keçid (i = 1):
   1. Çeşidlənməmiş hissədə minimal elementi (12) tapırıq [25, 12, 22, 64].
   2. 12 ilə 25-i dəyişirik.
   3. Array: [11, 12, 25, 22, 64]
3. Üçüncü keçid (i = 2):
   1. Çeşidlənməmiş hissədə minimal elementi (22) tapırıq [25, 22, 64].
   2. 22 ilə 25-i dəyişirik.
   3. Array: [11, 12, 22, 25, 64]
4. Dördüncü keçid (i = 3):
   1. Çeşidlənməmiş hissədə minimal elementi (25) tapırıq [25, 64].
   2. 25 artıq yerindədir, dəyişiklik lazım deyil.
   3. Array: [11, 12, 22, 25, 64]

Alqoritm tamamlanır, çünki bütün elementlər çeşidlənmişdir.