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


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



Yüklə 0,95 Mb.
səhifə38/44
tarix29.04.2023
ölçüsü0,95 Mb.
#104595
növüMühazirə
1   ...   34   35   36   37   38   39   40   41   ...   44
C fakepathmu hazir struktur

Ç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: О(n2).
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ə О(n2) 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 n2 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 .



Yüklə 0,95 Mb.

Dostları ilə paylaş:
1   ...   34   35   36   37   38   39   40   41   ...   44




Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©azkurs.org 2024
rəhbərliyinə müraciət

gir | qeydiyyatdan keç
    Ana səhifə


yükləyin