Ankara Üniversitesi Mühendislik Fakültesi
Bilgisayar Mühendisliği Bölümü
BLM-367 Đleri Veri Yapıları ve Algoritmalar
Lab2
1. Aşağıdaki denklemi özyinelemeli ağaç (recursion tree) yöntemi ile
çözmeniz için 15 dakika süreniz var.
T (n) = T (n / 9) + T (n / 3) + n
T (1) = θ (1)
Çözümünüzü boş bir kâğıda, üzerine adınızı soyadınızı ve öğrenci
numarasını yazarak lab asistanına teslim ediniz.
2. Heap-Sort algoritmasının C kodunu yazınız. Sizden derste anlatılan ve 2.
sayfada verilen algoritmanın uygulanması istenmektedir (başka
kaynaklardan alınan benzer algoritmaların kodu değerlendirme dışı
tutulacaktır). Heap-Sort algoritmasının gerekli fonksiyonlarının kodunu
yazdıktan sonra algoritmanın nasıl çalıştığını test etmek için bir ana
(main) fonksiyon yazınız. Bu fonksiyonda kullanıcıya algoritmayı test
edebilmesi için 2 seçenek sununuz:
a) değerleri 1 le 100 arasında değişen rastgele tamsayılar dizisi ile
b) kendisinin gireceği tamsayı sayı dizisi ile.
Sayı dizisinin uzunluğunu da kullanıcı girecektir. Ana fonksiyonunuz bu
sayıları max-heap özellikli neredeyse tam ikili ağaca yerleştirecektir ve
heap-sort algoritmasını uygulayacaktır. Kodunuzun çıkış değişkenleri
aşağıdakiler olmalıdır:
a) sıralanması gereken sayı dizisi
b)bu sayılardan oluşan ilk ikili ağaç
c) max-heap özellikli ilk ve sonraki ağaçlar (her adımda heap-sayısı bir
azalmış)
d) sıralama süresi
Kodunuzun çalıştığını lab saatinde asistana gösteriniz. Kaynak kodunuzun
nasıl sunulması gerektiğini asistanınız anlatacaktır.
MAX-HEAPIFY(A, i, n)
1. l← LEFT(i)
2. r← RIGHT(i)
3. if l ≤ n and A[l] > A[i]
4. then largest ←l
5. else largest ←i
6. if r ≤ n and A[r] > A[largest]
7. then largest ←r
8. if largest ≠ i
9. then exchange A[i] ↔A[largest]
10. MAX-HEAPIFY(A, largest, n)
BUILD-MAX-HEAP(A)
1. n= length[A]
2. for i ← n / 2 downto1
3. do MAX-HEAPIFY(A, i, n)
HEAPSORT(A)
1. BUILD-MAX-HEAP(A)
2. for i ←length[A] downto 2
3. do exchange A[1] ↔A[i]
4. MAX-HEAPIFY(A, 1, i -1)
Download

Ankara Üniversitesi Mühendislik Fakültesi Bilgisayar Mühendisliği