Untitled

 avatar
sangngoc
plain_text
a month ago
2.2 kB
1
Indexable
Never
public class MergeSort {
	
	public static int[] megre(int[] arrLeft, int[] arrRight) {
		int[] result = new int [arrLeft.length + arrRight.length];
		int left = 0;
		int right = 0;
		int index = 0;
		while(left < arrLeft.length && right<arrRight.length){
			if(arrLeft[left] < arrRight[right]){
				result[index++] = arrLeft[left++];
			}else {
				result[index++] = arrRight[right++];
			}
		}
		while (left < arrLeft.length) {
			result[index++] = arrLeft[left++];
		}
		while (right < arrRight.length) {
			result[index++] = arrRight[right++];
		}
		return result;
	}
	
	public static int[] mergeSort(int[] arr) {
		if(arr.length == 1) return arr;
		
		int midle = arr.length/2;
		int[] arrLeft = new int[midle];
		int[] arrRight = new int[arr.length - midle];
		for(int i = 0; i<midle;i++){
			arrLeft[i] = arr[i];
		}
		for(int i = midle;i<arr.length;i++){
			arrRight[i-midle] = arr[i];
		}
		int[] arr1 = mergeSort(arrLeft);
		int[] arr2 = mergeSort(arrRight);
		return megre(arr1, arr2);
	}
	
	
	
	public static void main(String[] args) {
		int[] arr = {10, 9, 11, 3, 1, 6, 2, 1, 3, 1};
		
		int[] a = mergeSort(arr);
		for (int i = 0; i < a.length; i++) {
			System.out.print(a[i] + " ");
		}
	}
}



public class QuickSort {
	
	public static void swap(int[] arr,int i,int j) {
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}
	
	private static int pivot(int[] arr, int low, int high) {
		int pivot = arr[high];
		
		int i = low - 1;
		for(int j = low; j<=high-1;j++){
			if(arr[j] < pivot){
				i++;
				swap(arr, i, j);
			}
		}
		swap(arr, i+1, high);
		return i+1;
	}
	
	public static void quickSort(int[] arr, int low, int high){
		if(low < high){
			
			int p = pivot(arr, low, high);
			
			quickSort(arr, low, p-1);
			quickSort(arr, p+1, high);
		}
	}
	
	public static void main(String[] args) {
		
		int[] arr = { 10, 7, 8, 9, 1, 5 };
        int N = arr.length;
 
        // Function call
        quickSort(arr, 0, N - 1);
        System.out.println("Sorted array:");
        for(int i = 0; i < arr.length;i++){
        	System.out.print(arr[i] + " ");
        }
	}
}
Leave a Comment