Algoritma ve Programlamaya Giriş Ünite -7 (Güz)

Arama Algoritmaları

Arama algoritmaları, bir veri kümesi (genellikle bir dizi) içinde belirli bir elemanın bulunup bulunmadığını ve eğer bulunuyorsa yerini tespit etmek için kullanılır.

• Doğrusal Arama (Linear Search): En basit arama algoritmasıdır. Dizideki elemanlar döngü yardımıyla baştan sona (sırayla) tek tek kontrol edilir. Aranan eleman bulunursa, o elemanın indisi döndürülür. Bu algoritma için dizinin sıralı olmasına gerek yoktur. Tüm elemanların tek tek kontrol edilmesi gerektiğinden (en kötü durum, elemanın sonda olması veya hiç olmamasıdır), tek bir döngü kullanılır ve zaman karmaşıklığı **O(n)**’dir.
• İkili Arama (Binary Search): Doğrusal aramadan çok daha verimli bir arama algoritmasıdır. Ancak çalışabilmesi için temel bir **ön şartı vardır: Dizi mutlaka sıralanmış olmalıdır**. Algoritma, diziyi sürekli ortadan ikiye böler; aranan değeri ortadaki elemanla karşılaştırır. Aranan değer küçükse dizinin sol yarısında, büyükse sağ yarısında aramaya devam eder. Bu bölme işlemi sayesinde zaman karmaşıklığı **O(log n)**’dir (PDF’teki $O(log \ log \ n)$ baskı hatasıdır).

Sıralama Algoritmaları

Sıralama algoritmaları, bir veri kümesindeki elemanları belirli bir düzene (genellikle artan veya azalan) göre yeniden düzenler. Farklı çalışma mantıklarına ve performanslara sahiptirler.

1. Karşılaştırma Temelli Algoritmalar

Bu algoritmalar, elemanları tek tek birbiriyle karşılaştırarak ve yerlerini değiştirerek çalışır.

• Kabarcık Sıralaması (Bubble Sort): Dizi üzerinde sürekli olarak yan yana bulunan iki elemanı karşılaştırır. Eğer yanlış sıradalarsa yerlerini değiştirir. Bu işlem, en büyük eleman “kabarcık gibi” sona çıkana kadar tekrar edilir. İç içe iki döngü gerektirdiği için zaman karmaşıklığı **O(n²)**’dir.
• Yerleştirmeli Sıralama (Insertion Sort): Diziyi sıralanmış ve sıralanmamış olarak iki bölüme ayırır. Sıralanmamış kısımdaki her elemanı tek tek alır ve sıralanmış kısımdaki doğru yerine “yerleştirir” (iskambil kağıtlarını sıralamaya benzer). En kötü durumda (dizi tersten sıralıysa) zaman karmaşıklığı **O(n²)**’dir.

2. Böl ve Fethet Temelli Algoritmalar

Bu algoritmalar, ana problemi daha küçük alt problemlere ayırır, bu alt problemleri çözer ve sonuçları birleştirir. Genellikle özyinelemeli (recursive) olarak çalışırlar.

• Hızlı Sıralama (Quick Sort): Bir **pivot eleman** seçer. Dizideki diğer elemanları pivottan küçükler (sola) ve büyükler (sağa) olarak iki alt diziye ayırır. Bu işlemi alt diziler için **özyinelemeli** olarak tekrar eder. Ortalama zaman karmaşıklığı **O(n log n)**’dir ve en hızlı sıralama algoritmalarından biridir.
• Birleştirmeli Sıralama (Merge Sort): Diziyi özyinelemeli olarak sürekli ikiye böler, ta ki her alt dizide tek bir eleman kalana kadar. Ardından bu küçük dizileri sıralı bir şekilde tekrar “birleştirir”. Zaman karmaşıklığı **O(n log n)**’dir.

Algoritma Karşılaştırması

Algoritmalar hızlarına (zaman karmaşıklığına) göre karşılaştırıldığında, $O(log n)$ (İkili Arama) en hızlılardan biridir. Sıralama algoritmaları arasında $O(n \ log \ n)$ (Hızlı Sıralama, **Birleştirmeli Sıralama**) karmaşıklığına sahip olanlar, $O(n^2)$ (Kabarcık, Yerleştirmeli) karmaşıklığına sahip olanlardan **daha hızlıdır** (daha yüksek performanslıdır).

1. Aşağıdakilerden hangisi kullanılan bir arama algoritmasıdır?

A) Çapraz arama
B) İkili arama
C) Rassal arama
D) Eleman arama
E) Karşılaştırmalı arama

Cevap : B) İkili arama

Açıklama : Bu ünitede ele alınan iki temel arama algoritması “Doğrusal Arama (Linear Search)” ve “İkili Arama (Binary Search)”dır.

2. Doğrusal arama algoritması ile bir dizi içerisinde bir eleman aranmaktadır. Bu arama işlemi ile ilgili olarak aşağıdakilerden hangisi yanlıştır?

A) Hedef eleman döngü yardımıyla dizi içinde aranır.
B) İşlem yapmanın zaman karmaşıklığı O(n) ile ifade edilir.
C) Döngüdeki her bir eleman aranan değer bulunana dek bu değer ile karşılaştırılır.
D) Aranan değerin dizide bulunmaması performans açısından olabilecek en kötü durumdur.
E) Hedef değeri aramak için iki adet for döngüsü kullanılır.

Cevap : E) Hedef değeri aramak için iki adet for döngüsü kullanılır.

Açıklama : Doğrusal arama (Linear Search), dizideki elemanları baştan sona tek tek kontrol eder. Bu işlem için iç içe iki döngüye değil, sadece **tek bir** döngüye ihtiyaç vardır. Bu nedenle E şıkkı yanlıştır.

3. Aşağıdakilerden hangisi karşılaştırma temelli olarak çalışan bir sıralama algoritmasıdır?

A) Hızlı sıralama
B) Birleştirmeli sıralama
C) İkili sıralama
D) Kabarcık sıralama
E) Lineer sıralama

Cevap : D) Kabarcık sıralama

Açıklama : Metinde sıralama algoritmaları iki grupta incelenmiştir: “Karşılaştırma Temelli Algoritmalar” (Kabarcık Sıralaması, Yerleştirmeli Sıralama) ve “Böl ve Fethet Temelli Algoritmalar” (Hızlı Sıralama, Birleştirmeli Sıralama).

4. Aşağıdakilerden hangi algoritmalarda işlem yapmanın zaman karmaşıklığı O(n²) ile ifade edilir?

A) Hızlı sıralama – Kova sıralaması
B) Yerleştirmeli sıralama – Kabarcık sıralama
C) Hızlı sıralama – Birleştirmeli sıralama
D) Yerleştirmeli sıralama – Hızlı sıralama
E) Birleştirmeli sıralama – Kabarcık sıralama

Cevap : B) Yerleştirmeli sıralama – Kabarcık sıralama

Açıklama : Metne göre “Kabarcık sıralamasının zaman karmaşıklığı O(n²)” ve “Yerleştirmeli sıralamanın zaman karmaşıklığı… tamamen sırasız bir yapıdaysa O(n²)” olarak ifade edilmiştir. Hızlı sıralama ve Birleştirmeli sıralama ise O(n log n) karmaşıklığındadır.

5. Aşağıdaki algoritmalardan hangisinde sıralama yaparken bir pivot eleman seçilir?

A) Lineer sıralama
B) Yerleştirmeli sıralama
C) Birleştirmeli sıralama
D) Hızlı sıralama
E) Doğrusal sıralama

Cevap : D) Hızlı sıralama

Açıklama : **Hızlı Sıralama (Quick Sort)** algoritması, “böl ve fethet” mantığını uygularken diziyi ikiye ayırmak için bir **pivot eleman** seçer ve diğer elemanları bu pivot elemana göre gruplar.

6. Hızlı sıralama algoritması ile ilgili olarak aşağıdakilerden hangisi doğrudur?

A) Böl ve fethet mantığına göre çalışır.
B) Sıralama için dizide bir pivot eleman seçilir.
C) Bu algoritmada işlem yapmanın zaman karmaşıklığı O(n log n) ile ifade edilir.
D) Özyinelemeli olarak çalışan bir algoritmadır.
E) Hepsi

Cevap : E) Hepsi

Açıklama : Metne göre Hızlı Sıralama; “böl ve fethet” mantığına dayanır (A doğru), bir “pivot eleman” seçer (B doğru), zaman karmaşıklığı O(n log n)’dir (C doğru) ve “özyinelemeli (recursive) olarak çözülür” (D doğru). Dolayısıyla tüm ifadeler doğrudur.

7. İkili arama algoritmasının ön şartı nedir?

A) Dizinin string değerlerden oluşması gerekir.
B) Dizide aranan elemanın olması gerekir.
C) Herhangi bir ön şartı yoktur.
D) Dizinin sıralanmış olması gerekir.
E) Dizinin sayısal değerlerden oluşması gerekir.

Cevap : D) Dizinin sıralanmış olması gerekir.

Açıklama : **İkili Arama (Binary Search)** algoritması, diziyi ortadan ikiye bölerek çalıştığı için, bu işlemin anlamlı olabilmesinin tek ön şartı dizinin **sıralanmış (sorted)** olmasıdır.

8. Böl ve fethet algoritmaları ile ilgili hangisi yanlıştır?

A) Problem küçük alt problemlere bölünerek çözülür.
B) Genelde özyinelemeli olarak çalışan algoritmalardır.
C) Sıralama tek seferde yapılır.
D) Bu aileye ait birden fazla algoritma vardır.
E) Sıralanan dizi alt dizilere ayrılır.

Cevap : C) Sıralama tek seferde yapılır.

Açıklama : “Böl ve fethet” mantığının temeli, ana problemi çözülebilir en küçük parçalara (alt problemlere) ayırmak ve bu parçaları çözüp sonra birleştirmektir. İşlem “tek seferde” yapılmaz, özyinelemeli olarak bölünerek yapılır. Bu nedenle C şıkkı yanlıştır.

9. Aşağıdaki dizide bulunan elemanlar kabarcık sıralama algoritması kullanılarak küçükten büyüğe sıralanmak isteniyor. İlk aşamada, tüm dizi elemanlarının birbiri ile karşılaştırılması sonucu elde edilen sıralama cevap şıklarının hangisinde doğru verilmiştir?
6 2 5 3 9

A) 2 6 5 3 9
B) 2 5 6 3 9
C) 2 5 3 6 9
D) 2 5 3 9 6
E) 2 3 5 9 6

Cevap : C) 2 5 3 6 9

Açıklama : Kabarcık sıralamada ilk aşama (pass 1) en büyük elemanı en sona taşır:
1. (6 2 5 3 9) -> 6 > 2 mi? Evet. Değiştir. -> (2 6 5 3 9)
2. (2 6 5 3 9) -> 6 > 5 mi? Evet. Değiştir. -> (2 5 6 3 9)
3. (2 5 6 3 9) -> 6 > 3 mü? Evet. Değiştir. -> (2 5 3 6 9)
4. (2 5 3 6 9) -> 6 > 9 mu? Hayır.
İlk aşama sonunda dizi: 2 5 3 6 9 olur.

10. Aşağıdaki sıralama algoritmaları birbiri ile karşılaştırıldığında hangisi daha hızlıdır?

A) Kabuk sıralama
B) Birleştirmeli sıralama
C) Seçmeli sıralama
D) Kabarcık sıralama
E) Yerleştirmeli sıralama

Cevap : B) Birleştirmeli sıralama

Açıklama : Tablo 10’a göre Kabuk, Seçmeli, Kabarcık ve Yerleştirmeli sıralamaların hepsi O(n²) (Kuadratik) zaman karmaşıklığına sahiptir. **Birleştirmeli sıralama** ise O(n log n) karmaşıklığına sahiptir. O(n log n), O(n²)’den daha hızlı (daha yüksek performanslı) olduğu için cevap B’dir.