Adaptivity
Coddy'nin Kabarcık Sıralaması kursunda ders 6 / 11.
Kabarcık sıralama (bubble sort) algoritmamız için zaman karmaşıklığının O(n2) olduğunu tartıştık. Ancak, dizimiz zaten sıralıysa ne olur? Bu durumda da çalışma süresi O(n2) olacaktır.
Uyarlanabilirlik (Adaptivity) nedir?
Uyarlanabilir bir algoritma, verilen girdi dizisine göre davranışını değiştiren bir algoritmadır.
Peki, kabarcık sıralama uyarlanabilir mi?
Evet, kabarcık sıralama algoritmamızı uyarlanabilir hale getirebiliriz. Kabarcık Sıralama algoritmasını, uyarlanabilir olması için en kötü durum çalışma süresi O(n2) ve en iyi durum çalışma süresi O(n) olacak şekilde yazmalıyalız. Burada en iyi durum, dizinin zaten sıralı olduğu durumu ifade eder.
Algoritmanın daha önce sıralanmış olması durumunda erken durmasını sağlamak için while döngüsünü kontrol eden bir boolean bayrak (flag) değişkeni kullanacağız.
while(flag)
{
//code
}
Dizi sıralanana kadar geçişi (pass) tekrarlamalıyız. Takas (swap) sayısını nasıl sayacağımızı zaten öğrendik, bu nedenle bir bayrak uygulayabiliriz ve geçişte herhangi bir takas gerekip gerekmediğini kontrol edebiliriz; eğer gerekmiyorsa döngüyü kırabiliriz.
Görev
OrtaBir dizi ve dizinin boyutunu alan ad_bubblesort adında bir fonksiyon oluşturun. Uyarlamalı kabarcık sıralama (adaptive bubble sort) algoritmasını uygulayın. Yer değiştirmeleri kontrol etmek için flag adında bir değişken kullanmayı unutmayın.
Kendin dene
#include <stdio.h>
#include <stdlib.h>
int* ad_bubblesort(int* arr, int arr_size, int n, int* returnSize) {
// Buraya kod yazın
*returnSize = n;
return arr;
}
Kabarcık Sıralaması bölümündeki tüm dersler
1Basics of Bubble Sort
IntroductionWorking of the Bubble SortSwap adjacent elementsBubble Sort Algorithm