Sorting Algorithms: Insertion Sort (part 1)
Çeşidləmə(Sorting) alqoritmlərindən istifadə etməkdə məqsəd, alqoritmin adından da göründüyü kimi əlimizdə olan məlumatları ən böyüyündən kiçiyinə (və ya kiçiyindən böyüyünə) ən sürətli şəkildə sıralamaqdır. Bunun üçün çox sayda çeşidləmə alqoritmləri istifadə olunur. Bəziləri çox sürətli, lakin yazmaq çətindir, bəziləri az miqdarda məlumat üçün çox sürətlidir, bəzilərini isə yazmaq asandır.
Çeşidləmə (Sorting) alqoritmləri aşağıdakı kimi təsnif edilə bilər :
- Sadə növlər (Simple Sorts)
- Effektiv (səmərəli) növlər (Effective sorts)
Sadə növlər
Bu tip alqoritmlər az miqdarda məlumat üzərində effektivdir, lakin böyük məlumatları idarə edə bilmir. Az məlumat üzərində sürətli və effektivdirlər.Aşağıdakı sadə növ çeşidləmə alqoritmaları göstərilmişdir.
1. Yerləşdirmə növü ( Insertion sort)
2. Seçmə növü (Selection sort)
3. Bubble Sort Alqoritmi
Effektiv (səmərəli) növlər
Bu alqoritmlər böyük siyahılarda və mürəkkəb proqramlarda istifadə edilə bilər. Lakin burada olan çeşidləmə alqoritmlərinin hər birinin öz çatışmazlıqları və üstünlükləri var. Bəziləri əlavə yer və ya daha çox təkrar tələb edə bilir, beləliklə daha mürəkkəb alqoritmlərlə nəticələnə bilir.
1. Merge sort
2. Heap sort
3. Quicksort
Bu məqaləmizdə Insertion sort haqqında danişacayıq.
Insertion Sort nədir?
Insertion sort, elementlərin bir-bir doğru mövqeyə köçürüldüyü bir çeşidləmə alqoritmidir. Insertion sort ilə performansda yüksək nəticə göstərmək olmur, lakin başa düşmək və həyata keçirmək üçün sadə bir çeşidləmə alqoritmidir.
Insertion Sort necə işləyir?
Sıralamaq istədiyimiz massivə nəzər salaq:
Bu siyahını çeşidləməyimizin yolu massivdəki ilk dəyərə baxmaq və sıralanmış hesab etməkdir (əvvəlcədən). İlk element 6-dır, buna görə 6-nı sıralanmış, 6-nın sağındakı hər şeyi sıralanmamış hesab edirik.
Sonra 6-nın sağındakı massivin qalan hissəsinə nəzər salırıq. Hər bir dəyəri təkrarlayaraq “sıralanmış” massivimizə daxil edəcəyik.
Aşağıdakı diaqramda mavi “sıralanmış” , qırmızı isə hazırda üzərində işlədiyimiz cari dəyərimizdir:
Cari dəyərimizə “3”-ə baxırıq və birdə sıralanan hissəyə baxırıq. Görürük ki, cari dəyərimiz siralan hissədəki dəyərdən (6) kiçikdir. Ona görədə bu dəyəri 6-dan yerləşdiririk:
Əla davam edək! Növbəti cari dəyərimiz 9 -dur, 9 6-dan kiçikdir? Xeyr, deməli 9 düzgün mövqedə deyil.
Davam edək. Cari dəyərimiz = 8. 8 9-dan kiçikdir? Bəli. deməli yerlərini dəyişmək lazımdır:
Növbəti cari dəyərimiz = 4. 4 0-dan kiçikdir? Bəli, ozaman yerlərini dəyişək:
4 hələ də qırmızıdır (yəni yuxarida dediyimiz kimi qırmızı hazırda üzərində işlədiyimiz dəyərdir), çünki çeşidlənməsi tamamlanmayıb. 4 8-dən kiçikdir? Bəli, yerin dəyişək.4 6-dan kiçikdir? Bəli, yerini dəyişək.Solunda hər şey ondan kiçik və ya ona bərabər olana qədər 4 ilə işləməyi dayandırmırıq:
Növbəti cari dəyərimiz 6. Yuxarida kimi sol tərəfdə özündən kiçik vəya bərabər dəyər olana kimi davam edirik :
Növbəti cari dəyərimiz 5. Burada yuxarıdakı qaydada davam edirik :
Növbəti cari dəyərimiz 2. Burada yuxarıdakı qaydada davam edirik :
Və beləliklə işimiz bitirdik.Massivimizi kiçikdən böyüyə çeşidləmiş olduq.
Kod üzərində nümunəyə baxaq ( Bu kod Python proqramlaşdırma dilində yazılıb)
İnsertionSort funksiyamızı təyin edirik və funksiyamız int tipində massiv qəbul edir. Daha sonra massivimizi for ilə iterasiyaya salmağımız lazımdır.
Massivimiz for-da 1-dən başlayacaq, çünki massivimizdəki ilk element sıralanmış kimi qeyd olunmuşdu.Buna görə də for loopumuz indeks 1-dən başlayacaq:
def insertionSort(array):
for i in range(1, len(array)):İndi geriyə baxmaq lazımdır. Bunu etmək üçün başqa bir döngüyə ehtiyacımız var. J adlı bir iteratordan istifadə edərək bir while döngüsü əlavə edəcəyik. j başlanğıcda i-yə bərabər olacaq və i-1 qədər geri hərəkət edəcəkdir. Niyə bir əvvələ? Müqayisə etdikdə [j] massivini [j — 1] massivi ilə müqayisə edəcəyik, buna görə j = 0 olduqda təsadüfən [-1] massivini yoxlamaq istəmirik!
[J] massivi [j — 1] massivindəki elementdən kiçikdirsə, onları dəyişdiririk. Daha sonra növbəti müqayisəyə keçmək üçün j-ni azaldırıq. While döngümiz j = 0 olarsa və ya cari elementdən böyük bir element tapsa dayanacaq.Və növbəti element üçün for döngüsü yenidən işləyəcək.
def insertionSort(array):
for i in range(1, len(array)):
j = i
while j > 0 and array[j] < array[j — 1]:
array[j], array[j — 1] = array[j — 1], array[j]
j -= 1
return arrayprint(insertionSort([1,4,3,56,34,121,23,43,7,89]))
# Nəcitə : [1, 3, 4, 7, 23, 34, 43, 56, 89, 121]
Bu da bizim çeşidləmə alqoritmalarımızdan biri olan İnsertion Sort.Sadə və yavaşdır.Ancaq öyrənmək önəmlidir.Növbəti məqalələrdə digər çeşidləmə alqoritmaların öyrəndikdən sonra, digər çeşidləmə alqoritmlərinin nisbətən daha optimal olduğunu anlamağınıza kömək edəcəkdir.
Oxuduğunuz üçün təşəkkür edirəm.
Mənbələr :
