Əlavə etməklə nizamlama

Vikipediya, azad ensiklopediya
(Əlavə etməklə sıralama səhifəsindən istiqamətləndirilmişdir)
Naviqasiyaya keçin Axtarışa keçin
Əlavə etməklə sıralama

Artırmalı nizamlama (ing. insertion sort ~ ru. сортировка вставкой ~ tr. eklemeli sıralama) – siyahıda bir elementdən başlayıb, yeni elementləri bir-bir lazım olan yerlərə qoymaqla siyahının yenidən qurulmasından ibarət nizamlama alqoritmi. Artırmalı nizamlama massivlərlə işlərkən səmərəli olmur (elementlərin daim yerlərini dəyişdirilməsi səbəbindən), ancaq əlaqəli siyahıların çeşidlənməsi üçün ideal uyğun gəlir. Proqramlaşdırması olduqca sadə olan ancaq performans baxımından digər sıralama alqoritmlərindən zəifdir.

Alqoritmin adı seçilən elementin sıralanmış massivdə uyğun yerə əlavə edilməsindən gəlir.

İşləməsinə aşağıdakı nümunə üzərində baxaq.

3 4 2 8

ilk rəqəmdən başlayaq.(3)

Birinci gedişdə sadəcə 3 sıralanır yəni heç nə etmirik.

3* 4 2 8(* simvolu O ana qədər sıraladığımız rəqmləri göstərir. Yəni * solundakı rəqəmlər sıralanmışdır.)

İkinci gedişdə seçdiyimiz ədəd 4-dür. 3 ilə 4-ü qarşılaşdırırığ 3 kiçik olduğu üçün yer dəyişdirmirlər.

3 4* 2 8

Üçüncü gedişdə sıradakı rəqəm 2-dir və 4 ilə qarşılaşdırırığ Və 2 kiçik olduğu üçün 4-ilə yer dəyişdirirlər.

3 2 4* 8(Sıralama hələ bitməyib çünki, 2 3-dən kiçikdir) 2 3 4* 8(3. gediş tamamlandı)

Dördüncü gedişdə Növbəti ədəd 8-dir və burda heç bir əməliyyat yerinə yetirilmir ,çünki 8 hamısında böyükdür

insertionSort (array A)

for i = 1 to length[A-1] do

value = A[i]

j = i-1

while j >= 0 and A[j] > value

A[j + 1] = A[j]

j = j-1

A[j+1] = value

Java Dilində Təsviri[redaktə | mənbəni redaktə et]

public static void insertionSort(int[] A){

for(int i = 1; i < A.length; i++){int value = A[i];

int j = i - 1;

while(j >= 0 && A[j] > value){

A[j + 1] = A[j];

j = j - 1;

   }

A[j + 1] = value;

}}

Bu Sıralamanın performansı O(n2)-dır. Bunun səbəbi massivdəki element sayı qədər gediş edilməsi və hər gedişdə ən pis ehtimalla element sayı qədər yerdəyişmə edilməsidir. Yəni bu sıralamada ən pis vəziyyət tərsdən sıralamaqdır.

Ədəbiyyat[redaktə | mənbəni redaktə et]

Həmçinin bax[redaktə | mənbəni redaktə et]

Xarici keçidlər[redaktə | mənbəni redaktə et]