title: Birleştirmeli Sıralama (Merge Sort) Algoritma Appleti link: http://orhanbalci.net/tr/?p=503 author: Orhan Balci description: post_id: 503 created: 2009/12/13 18:57:06 created_gmt: 2009/12/13 15:57:06 comment_status: open post_name: birlestirmeli-siralama-merge-sort-algoritma-appleti status: publish post_type: post

Birleştirmeli Sıralama (Merge Sort) Algoritma Appleti

Algoritma Adı: Birleştirmeli Sıralama Algoritması (Merge Sort) Algoritma Türü: Sıralama Algoritması Açıklama: Parçala yönet mantığıyla geliştirilmiş özyinelemeli (recursive) sıralama algoritmasıdır. Temel olarak üç aşamadan oluşur. Algoritma kendine verilen diziye ikiye böler. Birinci ve ikinci parçaların sıralanmasını sağlar. Son olarak da sıralı iki altdiziyi birleştirir. Örnek olarak 6 elemanlı 6 5 4 3 2 1 dizisini sıralayalım. 1. Adım : Dizi 6 5 4 ve 3 2 1 olmak üzere ikik alt diziye ayrılır. 2. Adım : 6 5 4 alt dizisi 6 ve 5 4 olmak üzere ikiye ayrılır. 3. Adım : 6 tek elemanlı olduğu için sıralanmış kabul edilir. 4. Adım : 5 4 dizisi 5 ve 4 olmak üzere ikiye ayrılır. 5. Adım : 5 ve 4 tek elemanlı olduklarından sıralanmış kabul edilir. 6. Adım : 5 ve 4 birleştirilir. Sıralama 4 5 şeklinde olur. 7. Adım : 6 ve 4 5 dizisi birleştirilir. Sıralama 4 5 6 şeklinde olur. İlk dizimizin ilk alt dizisi sıralanmış olur. 2 8. Adım : 3 2 1 dizisi 3 ve 2 1 olarak ikiye ayrılır. 9. Adım : 3 tek elemanlı olduğundan sıralı kabul edilir. 10. Adım : 2 1 dizisi 2 ve 1 olmak üzere ikiye ayrılır. 11. Adım : 2 ve 1 tek elemanlı olduklarından sıralanmış kabul edilir. 12. Adım : 2 ve 1 birleştirilir. Sıralama 1 2 olur. 13. Adım : 3 ve 2 1 dizileri birleştirilir. Sıralama 1 2 3 şeklinde olur. İlk dizimizin ikinci alt dizisi de sıralanmış olur. 14. Adım : 4 5 6 ve 1 2 3 alt dizileri birleştirilerek 1 2 3 4 5 6 sıralı dizisi oluşur. Algoritma sonlanır.

Algoritma Java Kodu : [java] int[] mergeSort(int[] siralanacakArray) { //eğer sıralanacak dizi uzunluğu 2’den küçükse //dizi sıralı sayılır if (siralanacakArray.length < 2) { return siralanacakArray; } //ikiye bölünen dizi boyutlarını hesaplıyoruz int ilkArrayBoyutu = siralanacakArray.length / 2; int ikinciArrayBoyutu = siralanacakArray.length - ilkArrayBoyutu; //iki alt diziyi ilklendiriyoruz int[] ilkArray = new int[ilkArrayBoyutu]; int[] ikinciArray = new int[ikinciArrayBoyutu]; //dizinin ilk parçasını bölüyoruz for (int i = 0; i < ilkArrayBoyutu; i++) { ilkArray[i] = siralanacakArray[i]; } //Dizinin geri kalanını ikinci diziye atıyoruz int j = 0; for (int k = ilkArrayBoyutu; k < siralanacakArray.length && j < ikinciArrayBoyutu; k++, j++) { ikinciArray[j] = siralanacakArray[k]; } //Böldüğümüz ilk diziyi sıralıyoruz int[] siraliIlkArray = mergeSort(ilkArray); //Böldüğümüz ikinci diziyi sıralıyoruz int[] siraliIkinciArray = mergeSort(ikinciArray); int m = 0, n = 0, y = 0; //Sıralı iki diziyi tekrar birleştiriyoruz. //Sırasıyla bütün elemanları karşılaştırarak küçük olanı önce //olmak kaydıyla ilk dizide birleştiriyoruz while (m < ilkArrayBoyutu && n < ikinciArrayBoyutu) { if (siraliIlkArray[m] <= siraliIkinciArray[n]) { siralanacakArray[y] = siraliIlkArray[m]; m++; y++; } else if (siraliIlkArray[m] > siraliIkinciArray[n]) { siralanacakArray[y] = siraliIkinciArray[n]; n++; y++; } } //Eğer ilk dizide eleman kalmışsa bunları listenin sonuna ekliyoruz while (m < ilkArrayBoyutu) { siralanacakArray[y] = siraliIlkArray[m]; y++; m++; } //Eğer ikinci dizide eleman kalmışsa bunları listenin sonuna ekliyoruz while (n < ikinciArrayBoyutu) { siralanacakArray[y] = siraliIkinciArray[n]; y++; n++; } //Sıralanmış diziyi dışarı veriyoruz. return siralanacakArray; } [/java] Javascript implementasyonu memory kullanimi daha iyi olan bir cozum : [javascript] fs = require(‘fs’) fs.readFile(‘./merge_sort.txt’, ‘utf8’, function (err, unsorted_array_data) { if (err) { return console.log(err); } var array_data = unsorted_array_data.split(”\r\n”); var input= array_data[1].split(” “).map(function (item) { return parseInt(item); }) merge_sort(input, 0, input.length); console.log(input.join(” “)); }); function merge(unsorted_array, begin_index, middle_point, end_index) { var i = begin_index; var j = middle_point; var merge_result = new Array(end_index-begin_index); var result_counter = 0; while (i < middle_point && j < end_index) { if(unsorted_array[i] <= unsorted_array[j]){ merge_result[result_counter] = unsorted_array[i]; i++; result_counter++; }else if(unsorted_array[j] < unsorted_array[i]){ merge_result[result_counter] = unsorted_array[j]; j++; result_counter++; } } while(i < middle_point){ merge_result[result_counter] = unsorted_array[i]; i++; result_counter++; } while(j < end_index){ merge_result[result_counter] = unsorted_array[j]; j++; result_counter++; } for (var k = begin_index; k < end_index; k++) { unsorted_array[k] = merge_result[k-begin_index]; } } var merge_sort = function (unsorted_array, begin_index, end_index) { if(end_index - begin_index == 1){ return; } var middle_point = Math.floor((begin_index + end_index) / 2); arguments.callee(unsorted_array, begin_index, middle_point); arguments.callee(unsorted_array, middle_point, end_index); merge(unsorted_array, begin_index, middle_point, end_index); } [/javascript]

Comments

admin: O dizi tersten sıralı. Burada kastettiğim sıralama artan bir sıralamadır. Verilen algoritma herhangi bir diziyi sıralamakta kullanılır. Yani senin verdiğin dizi de aynı algoritma kullanarak sıralanabilir.

komagine: iyide o dizi zaten sıralı karambol bi diziyi nasıl sıralıyo meselam 34 56 4 10 77 51 93 30 52 ?????? bi anlatırsan sevinirim :roll:

emre: admin rica etsem yukarıdakı gifi indirebilme şansımız varmı bitirme sunum ıcın lazım da???

admin: hacı abi o gif değil applet :)