AP Computer Science A sınavı, Java programlama dilinde sağlam bir temel oluşturmayı hedefleyen öğrenciler için tasarlanmıştır. Bu sınavda başarılı olabilmek için yalnızca temel programlama kavramlarını bilmek yeterli değildir; aynı zamanda veri yapıları ve algoritmalar konusunda derinlemesine bir anlayışa sahip olmak gerekir. Sorting algoritmaları, bu beceri setinin merkezinde yer alır ve sınavın hem çoktan seçmeli hem de free-response sorularında sıklıkla karşınıza çıkar. Bu makalede, AP Computer Science A müfredatında yer alan temel sıralama algoritmalarını detaylı Java kod örnekleriyle inceleyecek, her birinin zaman ve alan karmaşıklığını analiz edecek ve sınavda bu bilgileri nasıl kullanacağınızı açıklayacağız.
Sorting Algoritmalarının AP CS A İçindeki Yeri
College Board'un AP Computer Science A kurriculum çerçevesinde, öğrencilerin temel sıralama algoritmalarını anlaması ve bunları Java'da uygulayabilmesi beklenmektedir. Sınavda genellikle bir algoritmanın nasıl çalıştığını açıklamanız, verilen bir kod parçasının çıktısını tahmin etmeniz veya iki farklı algoritmayı performans açısından karşılaştırmanız istenir. Bu nedenle, yalnızca kod ezberlemek yerine, her algoritmanın altında yatan mantığı kavramak kritik öneme sahiptir.
Sorting algoritmalarını anlamak, yalnızca sınav başarısı için değil, genel olarak iyi bir yazılımcı olabilmek için de temel bir gerekliliktir. Bir algoritmanın zaman karmaşıklığını analiz edebilmek, gerçek dünya problemlerinde en verimli çözümü seçmenizi sağlar. AP Computer Science A, bu analitik düşünce yapısını geliştirmeniz için mükemmel bir başlangıç noktası sunar.
Bubble Sort: En Temel Sıralama Algoritması
Bubble Sort, sıralama algoritmaları arasında en basit ve anlaşılması kolay olanıdır. Algoritmanın çalışma prensibi son derece sezgiseldir: dizideki bitişik elemanları karşılaştırır, eğer sırasızlarsa yerlerini değiştirir ve bu işlemi dizi sıralanana kadar tekrarlar. Algoritmanın adı, büyük elemanların dizinin sonuna "kabarcık" gibi yükselmesi metaforundan gelmektedir.
Bubble Sort'un çalışma adımlarını bir örnekle açıklayalım. Diyelim ki elimizde [5, 3, 8, 1, 2] dizisi var ve bunu küçükten büyüğe sıralamak istiyoruz. İlk geçişte, 5 ve 3 karşılaştırılır; 5 > 3 olduğu için yer değiştirirler ve dizi [3, 5, 8, 1, 2] olur. Sonra 5 ve 8 karşılaştırılır; zaten sıralı oldukları için değişiklik olmaz. Devamında 8 ve 1 karşılaştırılır ve yer değiştirirler: [3, 5, 1, 8, 2]. Son olarak 8 ve 2 yer değiştirir: [3, 5, 1, 2, 8]. Birinci geçiş tamamlandığında en büyük eleman (8) dizinin sonuna ulaşmıştır. Bu işlem, tüm dizi sıralanana kadar tekrarlanır.
Java'da Bubble Sort implementasyonu şu şekildedir:
public static void bubbleSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// Elemanları değiştir
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
Bubble Sort'un zaman karmaşıklığı en kötü ve ortalama durumda O(n²)'dir. En iyi durumda, yani dizi zaten sıralıysa ve hiç değişiklik yapılmazsa, optimize edilmiş bir versiyon O(n) karmaşıklığa ulaşabilir. Ancak pratikte Bubble Sort, büyük veri setleri için oldukça yavaş kalır ve nadiren tercih edilir.
Selection Sort: Minimum Değeri Bularak Sıralama
Selection Sort algoritması, her geçişte dizinin sıralanmamış kısmındaki en küçük (veya en büyük) elemanı bulur ve bu elemanı sıralanmamış kısmın başına yerleştirir. Algoritma, tüm dizi taranana kadar bu işleme devam eder. Bubble Sort'tan farklı olarak, Selection Sort her geçişte yalnızca bir kez değiş tokuş yapar, bu da bazı durumlarda daha az yazma işlemi gerçekleştirmesi anlamına gelir.
Selection Sort'un adımlarını [64, 25, 12, 22, 11] dizisiyle açıklayalım. İlk geçişte, minimum değer (11) bulunur ve ilk pozisyondaki 64 ile yer değiştirir: [11, 25, 12, 22, 64]. İkinci geçişte, kalan sıralanmamış kısımdaki minimum (12) bulunur ve 25 ile değiştirilir: [11, 12, 25, 22, 64]. Bu süreç devam eder ve sonunda [11, 12, 22, 25, 64] elde edilir.
Java implementasyonu:
public static void selectionSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
int minIdx = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIdx]) {
minIdx = j;
}
}
// Minimum elemanı bulunan pozisyona taşı
int temp = arr[minIdx];
arr[minIdx] = arr[i];
arr[i] = temp;
}
}
Selection Sort'un zaman karmaşıklığı her durumda O(n²)'dir. Dizi ne kadar sıralı olursa olsun, algoritma yine de tüm karşılaştırmaları yapmak zorundadır. Ancak avantajı, her geçişte yalnızca bir kez değiştirme yapmasıdır; bu da özellikle bellek yazma maliyetinin yüksek olduğu sistemlerde değerli olabilir. AP Computer Science A sınavında Selection Sort, genellikle "kaç karşılaştırma yapılır?" veya "hangi adımda hangi eleman seçilir?" gibi sorularla test edilir.
Insertion Sort: Kart Destesi Gibi Çalışan Algoritma
Insertion Sort, iskambil kartlarını sıralarken izlediğimiz yönteme benzer şekilde çalışır. Dizinin ilk elemanını sıralı kabul eder, ardından her yeni elemanı, sıralanmış kısmın doğru pozisyonuna yerleştirir. Bu algoritma, özellikle hemen hemen sıralı veya küçük boyutlu diziler için oldukça verimlidir.
[12, 11, 13, 5, 6] dizisiyle çalışmasını inceleyelim. İlk iki eleman (12 ve 11) karşılaştırılır; 11 < 12 olduğu için yer değiştirirler ve [11, 12, 13, 5, 6] olur. Üçüncü eleman olan 13, sıralı kısımdaki elemanlarla karşılaştırılır ve doğru pozisyonda olduğu için değişiklik olmaz: [11, 12, 13, 5, 6]. Dördüncü eleman olan 5, sıralı kısımdaki tüm elemanlarla karşılaştırılır ve 11, 12, 13'ün önüne yerleştirilir: [5, 11, 12, 13, 6]. Son olarak 6, sıralı kısma eklenir ve [5, 6, 11, 12, 13] elde edilir.
Java'da Insertion Sort kodu:
public static void insertionSort(int[] arr) {
int n = arr.length;
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
Insertion Sort'un zaman karmaşıklığı en iyi durumda O(n), ortalama ve en kötü durumda O(n²)'dir. En iyi durum, zaten sıralı bir dizi için geçerlidir; bu durumda algoritma her elemanı yalnızca bir kez karşılaştırır. Bu özellik, Insertion Sort'u diğer O(n²) algoritmalarına göre daha avantajlı kılar, özellikle nispeten küçük veya neredeyse sıralı veri setleri için.
Merge Sort: Böl ve Fethet Paradigması
Merge Sort, "divide and conquer" (böl ve fethet) paradigmını kullanan etkili bir sıralama algoritmasıdır. Algoritma, diziyi önce eşit boyutlu iki alt diziye böler, bu alt dizileri özyinelemeli olarak sıralar ve ardından sıralanmış alt dizileri birleştirir. Bu yaklaşım, büyük veri setlerinde yüksek performans sağlar.
Merge Sort'un çalışma prensibini [38, 27, 43, 3, 9, 82, 10] dizisiyle açıklayalım. Önce dizi ortadan ikiye bölünür: [38, 27, 43, 3] ve [9, 82, 10]. Her alt dizi tekrar bölünür ta ki her biri tek eleman kalana dek. Ardından, alt diziler ikişer ikişer birleştirilirken sıralama yapılır: [27, 38, 3, 43] ve [9, 10, 82]. Son olarak bu iki sıralı dizi birleştirilerek [3, 9, 10, 27, 38, 43, 82] elde edilir.
AP Computer Science A müfredatında genellikle iki bölüme ayrılmış bir Merge Sort implementasyonu gösterilir: birleştirme (merge) işlemini gerçekleştiren metod ve diziyi bölen ana metod. Bu ayrım, sınavda "verilen kodun çıktısı nedir?" veya "algoritmanın hangi aşamasında hangi işlemler yapılır?" gibi soruların temelini oluşturur.
// İki sıralı diziyi birleştiren metod
public static void merge(int[] arr, int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
int[] leftArray = new int[n1];
int[] rightArray = new int[n2];
for (int i = 0; i < n1; i++) leftArray[i] = arr[left + i];
for (int j = 0; j < n2; j++) rightArray[j] = arr[mid + 1 + j];
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (leftArray[i] <= rightArray[j]) {
arr[k] = leftArray[i];
i++;
} else {
arr[k] = rightArray[j];
j++;
}
k++;
}
while (i < n1) { arr[k] = leftArray[i]; i++; k++; }
while (j < n2) { arr[k] = rightArray[j]; j++; k++; }
}