Birləşdirməli çeşidləmə
Birləşdirməli nizamlama(ing. merge sort, ru. сортировка слиянием) -bir neçə çeşidlənən (giriş) siyahının bir (çıxış) siyahıda birləşdirilməsindən ibarət çeşidləmə üsulu. Birinci siyahının ilk elementi götürülür və ikinci siyahının birinci elementi ilə müqayisə olunur; seçim edildikdən sonra elementin seçildiyi siyahının başlanğıcının göstəricisi növbəti elementə keçir və beləliklə, siyahılardan birinin sonunadək hərəkət edilir. Bu metod bir neçə siyahıya tətbiq edilə bilər. Maraqlıdır ki, iş yalnız siyahıların birinci elementləri ilə aparılır. Birləşdirməli çeşidləmə alqoritmi 1945-ci ildə Con fon Neyman tərəfindən icad olunub.
Birləşdirməklə nizamlama alqoritmi Con fon Neyman tərəfindən 1945 -ci ildə ixtira edilmiş, parçala və idarə etmə mexanizminə əsaslanan nizamlama alqoritmidir. Alqoritm ən pis, ən yaxşı və orta halda eyni sayda əməliyyat yerinə yetirir, O(n log n). Ən pis halda tutduğu yer isə O(n).
Daxili çeşidləmə
Daxili çeşidləmə ( ing. internal sort ~ ru. внутренняя сортировка ~ tr. iç sıralama) – yalnız operativ yaddaşda yerinə yetirilən və müvəqqəti fayllar üçün maqnit disklərindən, yaxud başqa qurğulardan istifadə etməyən çeşidləmə proseduru. Daxili çeşidləmə alqoritmlərinin 7 növü vardır: qabarcıqlı çeşidləmə (BUBBLE SORT), artırmalı çeşidləmə (INSERTION SORT), sürətli çeşidləmə (QUICK SORT), qalaq çeşidləməsi (HEAP SORT), birləşdirməli çeşidləmə (MERGE SORT), mərtəbəli çeşidləmə (RADIX SORT), seçməli çeşidləmə (SELECTION SORT).
== Ədəbiyyat ==
İsmayıl Calallı (Sadıqov), “İnformatika terminlərinin izahlı lüğəti”, 2017, “Bakı” nəşriyyatı, 996 s.
Leksikoqrafik çeşidləmə
Leksikoqrafik çeşidləmə (en. lexicographic sort) – hərflərin əlifbadakı ardıcıllığına görə sıralama. Leksikoqrafik çeşidləmədə ədədlər, onların sözlə yazılışında hərflərin əlifbadakı yerinə uyğun olaraq düzülür; məsələn, 567 ədədi B hərfinə uyğun bölmədə yerləşir (B – "beş").
== Ədəbiyyat ==
İsmayıl Calallı (Sadıqov), "İnformatika terminlərinin izahlı lüğəti", 2017, "Bakı" nəşriyyatı, 996 s.
Mərtəbəli çeşidləmə alqoritmi
Mərtəbəli çeşidləmə alqoritmi (en. radix sorting algorithm) - çeşidləməni qruplaşdırılan elementlərlə, onların açarlarının ardıcıl komponentlərinə görə gerçəkləşdirən çeşidləmə alqoritmi. Məsələn, 0-dan 999-dək ədədlərin çeşidlənməsinə baxaq: birinci siyahı yüzlük mərtəbələrinə görə çeşidlənərək 10 siyahıya ayrılır, sonra bu siyahıların hər biri eyni zamanda onluq mərtəbələrinə görə çeşidlənərək 10 siyahıya ayrılır, və nəhayət, bu siyahıların hər biri təklik mərtəbəsinə görə çeşidlənir. Bu alqoritm, adətən, ikilik ədədlərin çeşidlənməsində daha səmərəli olur, çünki siyahılara ayırma, sadəcə, ədədlərin böyük bitlərinin müəyyənləşdirilməsiylə aparılır, siyahıların sayı isə heç vaxt ikidən artıq olmur.
Mərtəbəli çeşidləmə alqoritmi (C dilində):
include <stdio.h>
define MAX 5
define SHOWPASS
void print(int *a, int n)
{
int i;
for (i = 0; i < n; i++)
printf("%d\t", a[i]);
}
void radixsort(int *a, int n)
{
int i, b[MAX], m = a[0], exp = 1;
for (i = 0; i < n; i++)
{
if (a[i] > m)
m = a[i];
}
while (m / exp > 0)
{
int bucket[10] =
{ 0 };
for (i = 0; i < n; i++)
bucket[(a[i] / exp) % 10]++;
for (i = 1; i < 10; i++)
bucket[i] += bucket[i - 1];
for (i = n - 1; i >= 0; i--)
b[--bucket[(a[i] / exp) % 10]] = a[i];
for (i = 0; i < n; i++)
a[i] = b[i];
exp *= 10;
#ifdef SHOWPASS
printf("\nPASS : ");
print(a, n);
#endif
}
}
int main()
{
int arr[MAX];
int i, n;
printf("Enter total elements (n < %d) : ", MAX);
scanf("%d", &n);
n = n < MAX ? n : MAX;
printf("Enter %d Elements : ", n);
for (i = 0; i < n; i++)
scanf("%d", &arr[i]);
printf("\nARRAY : ");
print(&arr[0], n);
radixsort(&arr[0], n);
printf("\nSORTED : ");
print(&arr[0], n);
printf("\n");
return 0;
}
İsmayıl Calallı (Sadıqov), “İnformatika terminlərinin izahlı lüğəti”, 2017, “Bakı” nəşriyyatı, 996 s.
Qabarcıqlı çeşidləmə
Qabarcıqlı nizamlama və ya qabarcıqlı sıralama (ing. Bubble sort) — iki qonşu elementi müqayisə etməklə və əgər onlar səhv nizamda isə onların yerini dəyişməklə verilən siyahını təkrarla yoxlayaraq, sıralayan alqoritmdir. Alqoritmin performansı aşağıdakı kimidir:
ən yaxşı vaxt =
O
(
n
)
{\displaystyle O(n)}
orta vaxt =
O
(
n
2
)
{\displaystyle O(n^{2})}
"5 1 4 2 8" şəklində bir massiv götürək, və massivi artma sırasına görə sıralayaq. Hər bir addımda müqayisə olunan elementlər tünd qara ilə göstərilib.
Sona qədər sıralama üçün 3 keçid lazımdır.
Birinci keçid:
( 5 1 4 2 8 )
→
{\displaystyle \to }
( 1 5 4 2 8 ), Burada alqoritm ilk iki elementi müqayisə edir və 5>1 olduğu üçün 5 ilə 1-in yerini dəyişir.
( 1 5 4 2 8 )
→
{\displaystyle \to }
( 1 4 5 2 8 ), 5 > 4 olduğu üçün
( 1 4 5 2 8 )
→
{\displaystyle \to }
( 1 4 2 5 8 ), 5 > 2 olduğu
( 1 4 2 5 8 )
→
{\displaystyle \to }
( 1 4 2 5 8 ), 5 < 8, heç bir dəyişiklik olmur.
İkinci keçid:
( 1 4 2 5 8 )
→
{\displaystyle \to }
( 1 4 2 5 8 )
( 1 4 2 5 8 )
→
{\displaystyle \to }
( 1 2 4 5 8 ), 4 > 2 olduğu üçün
( 1 2 4 5 8 )
→
{\displaystyle \to }
( 1 2 4 5 8 )
( 1 2 4 5 8 )
→
{\displaystyle \to }
( 1 2 4 5 8 )
Hal - hazırda massiv artma sırasına görə sıralanıb (nizamlanıb). Amma alqoritm bunun belə olduğunu bilmədiyi üçün elementlərin yerini dəyişmədən birdaha elementləri müqayisə edəcək.
Üçüncü keçid:
( 1 2 4 5 8 )
→
{\displaystyle \to }
( 1 2 4 5 8 )
( 1 2 4 5 8 )
→
{\displaystyle \to }
( 1 2 4 5 8 )
( 1 2 4 5 8 )
→
{\displaystyle \to }
( 1 2 4 5 8 )
( 1 2 4 5 8 )
→
{\displaystyle \to }
( 1 2 4 5 8 )
Python dilində implementasiya aşağıdakı kimi olar.
Seçməli çeşidləmə
Seçməli çeşidləmə (selection sort, rus. сортировка выбором, seçmeli sıralama – çeşidləmə alqoritmi; bu alqoritmə görə öncə massivin qiyməti ən kiçik olan elementi seçilir, sonra növbəti ən kiçik element seçilir və s. Təcrübədə, ən kiçik qiymətli element massivin axtarış aparılan hissəsinin birinci elementi ilə yerini dəyişir və bundan sonra axtarış massivin yerdə qalan hissəsində davam etdirilir.
public static int[] selectionsort(int[] numbers){
for (int i = 0; i < numbers.length-1; i++)
{
int index = i;
for (int j = i+1; j < numbers.length; j++)
if (numbers[j] < numbers[index]) //Finds smallest number
index = j;
int smallerNumber = numbers[index]; //Swap
numbers[index] = numbers[i];
numbers[i] = smallerNumber;
}
return numbers;
}
İsmayıl Calallı (Sadıqov), “İnformatika terminlərinin izahlı lüğəti”, 2017, “Bakı” nəşriyyatı, 761 s.
Şell çeşidləməsi
Şell çeşidləməsi — verilənləri nizamlamaq üçün istifadə olunan qabarcıqlı çeşidləmə və artırmalı çeşidləmədən (İNSERTİON SORT) daha sürətli proqramlaşdırma alqoritmi; 1959-cu ildə Donald Şell tərəfindən təklif olunub. Şell çeşidləməsində ədədi massivin bir-birindən müəyyən məsafədə yerləşən cüt-cüt elementləri düzgün ardıcıllıqla yerləşməyibsə, onların yeri dəyişdirilir. Hər keçiddə Şell çeşidləməsi yoxlanılan elementlər arasındakı intervalı kiçildir. Məsələn, 10 elementdən ibarət siyahı üçün Şell çeşidləməsi öncə siyahıda bir-birindən beş element (1 və 6, 2 və 7, 3 və 8 və s. nömrəli) aralı olan element cütlərini çeşidləyir. Sonra o, bir-birindən iki element (1 və 3, 2 və 4, 3 və 5 və s. nömrəli) aralı olan elementləri yoxlamaqla siyahını çeşidləyir. Sonda Şell çeşidləməsi siyahıda ard-arda yerləşmiş elementləri cüt-cüt yoxlayır, nəticədə son siyahı tamamilə nizamlanmış olur.
İsmayıl Calallı (Sadıqov), “İnformatika terminlərinin izahlı lüğəti”, 2017, “Bakı” nəşriyyatı, 996 s.
