Merge Sort Algorithm

Kategori: Popular Algorithms , 19 Kasım 2019 , JanFranco


Problem:

Problemimiz klasik, diziyi sıralama problemi.

Yaklaşım:

Klasik sıralama yaklaşımımızdan farklı olarak, böl ve fethet yöntemini kullanacağız. Merge sort olarak bilinen bu algoritmayı detaylıca Algoritma Dizayn ve Tasarım bölümünde anlattım ve analizini de yaptım, inceleyebilirsiniz.

Çözüm:

 




import java.util.Random;

public class MergeSort {
	
	static void sort(int arr[], int l, int r) {
		if(l < r) {
			int m = (l + r) / 2;
			sort(arr, l, m);
			sort(arr, m + 1, r);
			merge(arr, l, m, r);
		}
	}
	
	static void merge(int[] arr, int l, int m, int r) {
		int n1 = m - l + 1;
		int n2 = r - m;
		
		int[] L = new int[n1];
		int[] R = new int[n2];
		
		for(int i=0; i<n1; i++) {
			L[i] = arr[l + i];
		}
		
		for(int i=0; i<n2; i++) {
			R[i] = arr[m + i + 1];
		}
		
		int i = 0, j = 0, k = l;
		while(i < n1 && j < n2) {
			if(L[i] <= R[j]) {
				arr[k] = L[i];
				i++;
			}
			else {
				arr[k] = R[j];
				j++;
			}
			k++;
		}
		
		while(i < n1) {
			arr[k] = L[i];
			i++;
			k++;
		}
		
		while(j < n2) {
			arr[k] = R[j];
			j++;
			k++;
		}
	}
	
	static void printArr(int[] arr) {
		for(int i=0; i<arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
	}
	
	static int[] randomArr(int n) {
		Random random = new Random();
		int[] arr = new int[n];
		for(int i=0; i<n; i++) {
			arr[i] = random.nextInt(100);
		}
		return arr;
	}

	public static void main(String[] args) {
		int[] arr = randomArr(20);
		sort(arr, 0, arr.length - 1);
		printArr(arr);
	}

}


Sonraki Yazı: Quick Sort Algorithm
Yorumlar

Henüz bir yorum bulunmuyor.