Mühazirə 1 Giriş Əsas anlayışlar. "Məlumat"

Çeşidləmənin düz üsulları

Yuxarıda baxdığımız düz qoşulma çeşidləmə üsullarından başqa, daha 2 düz çeşidləmə üsulları vardır.

Düz seçim üsulu ilə çeşidləmə

Bu üsuı aşağıdakı prinsiplərə əsaslanmışdır:

1. Ən kiçik açarlı element seçilir.

2. O, öz yerini birinci element olan a1-lə dəyişdirir.

3. Sonra bu proses yerdə qalan (n-1) elementləri, (n-2) elementləri və s. ilə o vaxta qədər təkrar olunur ki, ən axırda bir dənə ən “böyük” element qalmış olsun.

Düz seçim çeşidləmə alqoritminin effektivliyi

C açarlarının müqayisələr sayı aydındır ki, açarların başlanğıc düzülüşündən asılı olmur. Belə demək olar ki, bu mənada bu üsulun davranışı düz qoşulmadakı davranışla müqayisədə daha az dərəcədə təbii olur. C üçün açarların istənilən yerləşməsində aşağıdakı ifadəni yaza bilərik:

  C = n(n-1)/2

Beləliklə, müqayisələrin sayı belə olacaqdır:  О(n²).

Başlanğıcda açarlar nizamlanmış olan zaman yerdəyişmələrin minimal sayı М_min = 3(n - 1), başlanğıcda açarlar əks isiqamətdə yerləşmiş olduqda, maksimal sayı isə М_max = 3(n - 1) + С, yəni, tərtib isə О(n²) olacaqdır.

Ən pis halda düz seçimli çeşidləmədə tərtib həm müqayisələr sayı, həm də yerdəyişmələr sayı üçün n² olacaqdır.
Düz mübadilə köməkliyi ilə çeşidləmə (qabarcıqlı çeşidləmə)

Bu üsula qədər nəzərdən keçirilən hər iki üsulu da, həmçinin, “mübadilə” çeşidləmələri kimi nəzərdən keçirtmək olar. Baxacağımız bu bölmədə təsvir olunan üsulda iki elementlərin yerlərinin dəyişdirilməsi özlüyündə prosesin ən xarakterik xüsusiyyətini göstərir. Aşağıda veriləcək düz mübadilə alqoritmi qonşu elementlər cütlüyü üçün müqayisəyə və yerlərinin əvəz olunmasına əsaslanmış və həmin proses o vaxta qədər davam edir ki, bütün elementlər nizamlanmış olsunlar.

Düz seçim üsulunda olduğu kimi, biz massiv üzrə keçidləri təkrar edirik, hər dəfə qalan ardıcıllığın ən kiçik elementini massivin sol sonuna sürüşdürürük. Massivi üfüqi qurulma kimi deyil, şaqili qurulma kimi nəzərdən keçirtsək, o zaman elementləri içərisində su olan çəndəki qabarcıqlar kimi interpretasiya etmək olar və bu halda onların hər birinin çəkisi onun açarına uyğun olacaqdır. Bu halda hər bir keçiddə bir qabarcıq elə bil ki, onun çəkisinə uyğun olan səviyyəyə qədər qalxır