Merge Sort Akış Şeması ve QBasic dilinde uygulanışı

Merge Sort (Birleştirme Sıralaması) Böl ve Yönet ( Divide and conq.) mantığı ile çalışan bir sıralama algoritmasıdır. Düşük sayıda karşılaştırma yaptığından bu yönden verimlidir. Ancak bunun dezavantajı ise ihtiyaç duyduğundan fazla alan gereklidir.

Merge Sort Özellikleri Avantajları

  • Böl ve fethet tekniğini kullanır
  • Zaman karmaşıklığı: O (n * log (n))
  • Uzay karmaşıklığı O (n).
  • Kararlı
  • Uyarlanabilir uygulama mümkündür.
  • Düşük karşılaştırma sayısı
  • Sıralı erişim verileriyle hızlı çalışır.
  • Paralel uygulama için uygun
  • Uygulamada birçok uygulamayı bulur

Böl ve Yönet

Böl ve yönet fikrine , karmaşık problemleri alt problemlere bölme ilkesine diyebiliriz. Bütün olan bir problem alt problemlere bölünür. Alt problemler de daha basit problemlere bölünür. Bu işlem döngüsü problemimiz çözülene kadar yada çözümü önemsiz derecede küçük olana kadar devam eder. Bu mantık , günümüzde kullanılan en verimli algoritmalardan bazılarını ortaya koyar.

Birleştirme Sıralaması Çalışma Mantığı

Böl ve Fethet mantığını uygulayarak elimizde bulunan bir problemi aşağıdaki adımlarla çözelim ;

Merge Sort
merge-flow-chart
  1. Elimizde bulunan sayı dizisini sağ ve sol taraf olmak üzere ikiye böldük. Daha sonra , her yarım kısım tekrar bölünerek eleman sayısı 1 veya sıfır olana kadar tekrar ederek devam ettik.
  2. 1 parça kaldığında ki kalan parçanın sıralanmış olması önemsizdir.
  3. Daha sonra, elimizde bulunan tüm öğeleri dizi sıralanana kadar birleştiriyoruz.

Merge Sort Birleştirme Tekrarı ve Akış Şeması

Diziyi önemsiz seviyeye kadar böldükten sonra yapılan birleştirme işin asıl yapıldığı yerdir. İki Dizi alır ve bu iki diziyi en verimli şekilde birleştirir. Buradaki önemli kilit nokta dizinin birleştirilmeden önce sıralanması gerektiğidir.

Birleştirme işlemi nasıl yapılır ;

Örnek için sol(left) ve sağ(right) adlı iki dizimizin olduğunu varsayalım ve bu iki diziyi birleştirme işlemi ile sıralayalım;

sol = 0, 2, 5, 10
sağ = -6, 2, 7, 20

Daha sonra ;

“Sol” ve “sağ” daki bulunduğumuz derinliği gösteren iki değişken oluşturuyoruz;

leftIndex = 0;
rightIndex = 0;

Şimdi iki dizideki tüm elemanları karşılaştırıp en küçüğünü alalım. Buradaki en küçük değerimiz -6’dır. İlk sonucumuz -6 yı bir sonuc dizisine aktaralım.

sonuc[0] = -6

-6 değerini sağ taraftaki diziden aldığımızdan dolayı rightIndex’imizi 1 artıralım .

rightIndex++

Daha sonra ikinci bulacağımız sonuç ise sol dizideki 0 rakamıdır.

sonuc[1] = 0 ve leftIndex’i bir artıralım leftIndex++

Bu adımlar iki dizideki tüm sayılar sonuç dizisine doluncaya kadar devam eder.

Birleştirme için Akış Şeması :

Merge Sort Akış Şeması 1
merge-flow-chart-1

Merge Sort özyineleme(recursive) çalışan bir algoritmadır. Yukarıda da bahsettiğimiz gibi , diziyi tüm alt diziler 1 veya 0 boyutuna gelinceye kadar yenileyerek böler. Sonra eldeki dizileri ikişer ikişer sıralayarak birleştirir.

Eğer daha önce özyinelemenin ne olduğunu görmediyseniz ve bilmiyorsanız biraz kafa karıştırıcı görünebilir. Özyineleme , kendisini çağıran bir yöntemdir. Her özyineleme, çağrıları kesen ve önceki çağrı için bir sonuç döndüren bir temel duruma sahip olmalıdır.

Akış Şeması

Merge Sort Akış Şeması 2
merge-sort-flow-chart-2

Alan Karmaşıklığı Analizi

Algoritmamıza baktığımızda algoritma hızının , ayırdığımız ekstra alana karşılık geldiğini farketmişsinizdir.

Bu alan , ekstradan sağ ve sol diziler oluşturmak için ihtiyaç duyduğumuz alan. Orjinal dizinin yarısı büyüklüğünde olduğu için 2*N/2 ekstra alana ihtiyacımız olacak.

Zaman Karmaşıklığı Analizi

Merge Sort Çalışma Mantığı
merge-visual-1

Diziyi 8 öğeyle sıraladığımız yukarıdaki resmi düşünün. Grafiğin üst yarısı sadece diziyi böler. Gerçek çalışmanın birleştirme rutininde yapıldığına dikkat edin. Grafiğin yalnızca alt yarısında çağrılır. Bu nedenle zamanın büyük kısmı bu yarıda harcanır. Bu nedenle asimtotik hesaplamalarda bölünme süresini (resmin üst yarısı) göz ardı edebiliriz.

Burada bazı sorular doğar ;

  1. İkinci yarının derinliği kaçtır ? Cevap log (n). Çünkü her bir sonraki seviyede birleştirilecek dizilerin sayısı yarıya indirilir.
  2. Her birleştirme seviyesinde ne kadar iş yapılır? Cevap n. Aslında n/2’ye daha yakındır, ancak asimptotik hesaplamalarda sabit faktörler göz ardı edilir. 
  3. Eğer ağacın log (n) seviyeleri varsa ve her seviye O (n) çalışıyorsa, algoritmanın karmaşıklığı nedir? Cevap O (n * log (n)).

QBasic Dilinde Merge Sort Uygulanışı

 1000 REM Quite BASIC Algorithm Project
1010 REM Merge Sort program
1100 REM Initialize the arrays
1100 LET N = 10
1110 LET C = 0
1120 ARRAY A
1131 ARRAY B
1140 GOSUB 3000
1150 REM Print the random array
1160 PRINT "Random list:"
1170 GOSUB 4000
1180 REM Sort the array
1190 GOSUB 2000
1200 PRINT "Sorted list:"
1210 REM Print the sorted array
1220 GOSUB 4000
1230 PRINT "Number of Iterations: ";
1240 PRINT C
1250 END
2000 REM Merge sort the list A of length N
2010 REM Using the array B for temporary storage
2020 REM
2030 REM === Split phase ===
2040 REM C counts the number of split/merge iterations
2050 LET C = C + 1
2060 LET X = 1
2070 LET Y = 1
2080 LET Z = N
2090 GOTO 2110
2100 IF A[X] < A[X-1] THEN GOTO 2170
2110 LET B[Y] = A[X]
2120 LET Y = Y + 1
2130 LET X = X + 1
2140 IF Z < Y THEN GOTO 2200
2150 GOTO 2100
2160 IF A[X] < A[X-1] THEN GOTO 2110
2170 LET B[Z] = A[X]
2180 LET Z = Z - 1
2190 LET X = X + 1
2200 IF Z < Y THEN GOTO 2300
2210 GOTO 2160
2220 REM
2300 REM === Merge Phase ===
2310 REM Q means "we're done" (or "quit")
2320 REM Q is 1 until we know that this is not the last iteration
2330 LET Q = 1
2340 LET X = 1
2350 LET Y = 1
2360 LET Z = N
2370 REM First select the smaller item
2380 IF B[Y] < B[Z] THEN GOTO 2480 ELSE GOTO 2520
2390 REM Check if the loop is done
2400 IF Z < Y THEN GOTO 2560
2410 REM If both items are smaller then start over with the smallest
2420 IF B[Y] >= A[X-1] OR B[Z] >= A[X-1] THEN GOTO 2450
2430 LET Q = 0
2440 GOTO 2370
2450 REM Pick the smallest item that represents an increase
2460 IF B[Z] < B[Y] AND B[Z] >= A[X-1] THEN GOTO 2520
2470 IF B[Z] > B[Y] AND B[Y] < A[X-1] THEN GOTO 2520
2480 LET A[X] = B[Y]
2490 LET Y = Y + 1
2500 LET X = X + 1
2510 GOTO 2390
2520 LET A[X] = B[Z]
2530 LET Z = Z - 1
2540 LET X = X + 1
2550 GOTO 2390
2560 IF Q = 0 THEN GOTO 2030
2570 RETURN
3000 REM Create a random list of N integers
3030 FOR I = 1 TO N
3040 LET A[I] = FLOOR(RAND(100))
3070 NEXT I
3090 RETURN
4000 REM PRINT the list A
4010 FOR I = 1 TO N
4020 PRINT A[I];
4030 PRINT ", ";
4040 NEXT I
4050 PRINT
4060 RETURN

Sıralama algoritmaları ile ilgili daha fazla yazımızı okumak için http://kodlar.net/ ‘ i takip edebilirsiniz. Merge Sort hakkında soru bölümümüze soru sorabilirsiniz. Merge Sort hakkında daha fazla bilgi ve daha fazla dökümana sahip olmak için burayı ziyaret edebilirsiniz.

Emre Sualp

Kocaeli Üniversitesi Bilgisayar Mühendisliği 4. sınıf öğrencisiyim .Java , Javascript ve Android programlama ile ilgileniyorum.Bildiklerimi aktarmak ve yeni öğrendiğim konuları pekiştirmek için yazılarımı sizlerle paylaşacağım.

Bir cevap yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir