Сложность алгоритма - сортировка слиянием итерацией

 
 
 
Сообщения:31
Всем привет!

Я попытался реализовать сортировку слиянием итерацией, но немного намудрил и не совсем уверен, работает ли моя программа со сложностью nlogn. Может кто-нибудь смог бы также подсказать более лучший способ решения итерацией? Заранее благодарен!

public class MergeSort_iterativ {

	public static int[] merge(int[] A, int left, int middle, int right) {

		int[] B = new int[A.length];
		
		int i = left;
		int j = middle+1;
		int k = 0;
		
		// Уже отсортированные последовательности данной длины
		if(left > 0) {
			while(k < left) {
				B[k] = A[k];
				k++;
			}
		}
		
		// Слияние двух последовательностей
		while(i <= middle && j <= right) {
			if(A[i] < A[j]) {
				B[k] = A[i];
				i++;
			} else {
				B[k] = A[j];
				j++;
			}
			k++;
		}
		// Добавление элементов первой последовательности в конец отсортированной последовательности, 
		// так как они больше остальных элементов
		while(i <= middle) {
			B[k] = A[i];
			i++;
			k++;
		}
		// Добавление элементов второй последовательности в конец отсортированной последовательности, 
		// так как они больше остальных элементов
		while(j <= right) {
			B[k] = A[j];
			j++;
			k++;
		}
		
		// Остаточные элементы в массиве, которые будут отсортированы в следующем проходе
		int rest = right + 1;
		int n = A.length;
		while(rest < n) {
			B[k] = A[rest];
			rest++;
			k++;
		}
		return B;
	}

	public static void printArr(int[] B, int n) {
		for (int i = 0; i < n; i++) {
			System.out.print(B[i] + " ");
		}
		System.out.println(" - " + n + " элементов.");
		System.out.println();
	}

	public static void main(String[] args) {

		int[] A = { 21, 14, 15, 45, 50, 5, 49, 90, 115, 3, 22 };
		int n = A.length;
		System.out.println("Unsorted: ");
		printArr(A, n);
		
		// Начальная длина последовательностей для сортировки и слияния
		int length = 1;
		
		while(length < n) {
			int right = 0;
			// Есть еще минимум одна последовательность данной длины
			while(right + length < n){
				int left = right;
				int middle = (left + length) - 1;
				right = Math.min(middle + length, n-1);
				A = merge(A, left, middle, right);
				right = right + 1;
			}
			length = length * 2;
		}
		System.out.println("Sorted: ");
		printArr(A, n);
	}
}
Изменен:07 фев 2018 21:21
 
 
Сообщения:31
Более лучшее решение.. если кому-то интересно.

public class MergeSort_iterativ {

	public static void merge(int[] A, int left, int middle, int right) {
		int l1 = middle - left + 1;
		int l2 = right - middle;
		int[]L = new int[l1];
		int[]R = new int[l2];
		
		for(int i = 0; i < l1; i++) {
			L[i] = A[left + i];
		}
		for(int j = 0; j < l2; j++) {
			R[j] = A[middle + 1 + j];
		}

		int i = 0;
		int j = 0;
		int k = left;
		
		while(i < l1 && j < l2) {
			if(L[i] < R[j]) {
				A[k] = L[i];
				i++;
			} else {
				A[k] = R[j];
				j++;
			}
			k++;
		}
		while(i < l1) {
			A[k] = L[i];
			i++;
			k++;
		}
		while(j < l2) {
			A[k] = R[j];
			j++;
			k++;
		}
	}

	public static void printArr(int[] B, int n) {
		for (int i = 0; i < n; i++) {
			System.out.print(B[i] + " ");
		}
		System.out.println();
		System.out.println();
	}

	public static void main(String[] args) {

		int[] A = { 21, 14, 15, 45, 50, 5, 49, 90, 115, 3, 22 };
		int n = A.length;
		System.out.println("Unsorted: ");
		printArr(A, n);
		
		int length = 1;
		
		while(length < n) {
			int right = 0;
			while(right + length < n){
				int left = right;
				int middle = (left + length) - 1;
				right = Math.min(middle + length, n-1);
				merge(A, left, middle, right);
				right = right + 1;
			}
			length = length * 2;
		}
		System.out.println("Sorted: ");
		printArr(A, n);
	}
}
 
Модераторы:Нет
Сейчас эту тему просматривают:Нет