“tri par fusion” Réponses codées

tri par fusion

function merge(left, right) {
    let arr = []
    // Break out of loop if any one of the array gets empty
    while (left.length && right.length) {
        // Pick the smaller among the smallest element of left and right sub arrays 
        if (left[0] < right[0]) {
            arr.push(left.shift())  
        } else {
            arr.push(right.shift()) 
        }
    }
    
    // Concatenating the leftover elements
    // (in case we didn't go through the entire left or right array)
    return [ ...arr, ...left, ...right ]
}
Sirak Radaa

tri par fusion

//recursive merge sort

	public static void mergeSort(int[] a){
		mergeSort(a, 0, a.length-1);
	}

	private static void mergeSort(int[] a, int i, int j){
		if (i == j)
			return;
		int mid = (i + j)/2;
		mergeSort(a, i, mid);
		mergeSort(a, mid + 1, j);
		merge(a, i, j);
	}

	private static void merge(int[] a, int i, int j){
		int[] temp = new int[j - i + 1];
		int mid = (i + j)/2;
		int left = i, right = mid + 1, k = 0;
		while (left <= mid && right <= j && k < temp.length){
			if (a[left] < a[right])
				temp[k++] = a[left++];
			else
				temp[k++] = a[right++];
		}
		while (left <= mid)
			temp[k++] = a[left++];
		while (right <= j)
			temp[k++] = a[right++];

		for (int m = 0; m < temp.length; m++)
			a[i + m] = temp[m];
	}
Dovi91

Fonction de tri de fusion

def merge_sort(arr):
    """Execute the merge sort algorithm"""
    if len(arr) > 1:
        # recursive case
        mid = len(arr) // 2 # find the midpoint of the array
        l = arr[:mid] # define the left half of the array
        r = arr[mid:] # define the right half of the array

        l = merge_sort(l) # sort the left half by calling this function
        r = merge_sort(r) # sort the right half by calling this function

        # now merge the two lists
        merged = [] # define an empty merged array
        while len(l) > 0 and len(r) > 0:
            # compare the heads of the left and right array
            if l[0] <= r[0]:
                # if the head of the left list is smaller than the head of the right list
                # pop the head of the left list and append it to the merged list
                merged.append(l.pop(0))
            else:
                # otherwise, pop the head of the right list and append that
                merged.append(r.pop(0))

        # add any elements remaining in the left or right list to the merged list
        merged = merged + l + r

        return merged
    else:
        # base case
        return arr
Distinct Dragonfly

tri par fusion

Step 1 − if it is only one element in the list it is already sorted, return.
Step 2 − divide the list recursively into two halves until it can no more be divided.
Step 3 − merge the smaller lists into new list in sorted order.
Successful Swan

Tri par fusion

<script>
  
// JavaScript program for Merge Sort
  
// Merges two subarrays of arr[].
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
function merge(arr, l, m, r)
{
    var n1 = m - l + 1;
    var n2 = r - m;
  
    // Create temp arrays
    var L = new Array(n1); 
    var R = new Array(n2);
  
    // Copy data to temp arrays L[] and R[]
    for (var i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (var j = 0; j < n2; j++)
        R[j] = arr[m + 1 + j];
  
    // Merge the temp arrays back into arr[l..r]
  
    // Initial index of first subarray
    var i = 0;
  
    // Initial index of second subarray
    var j = 0;
  
    // Initial index of merged subarray
    var k = l;
  
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        }
        else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
  
    // Copy the remaining elements of
    // L[], if there are any
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }
  
    // Copy the remaining elements of
    // R[], if there are any
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}
  
// l is for left index and r is
// right index of the sub-array
// of arr to be sorted */
function mergeSort(arr,l, r){
    if(l>=r){
        return;//returns recursively
    }
    var m =l+ parseInt((r-l)/2);
    mergeSort(arr,l,m);
    mergeSort(arr,m+1,r);
    merge(arr,l,m,r);
}
  
// UTILITY FUNCTIONS
// Function to print an array
function printArray( A, size)
{
    for (var i = 0; i < size; i++)
       document.write(  A[i] + " ");
}
  
  
var arr = [ 12, 11, 13, 5, 6, 7 ];
    var arr_size = arr.length;
  
    document.write(  "Given array is <br>");
    printArray(arr, arr_size);
  
    mergeSort(arr, 0, arr_size - 1);
  
    document.write( "<br>Sorted array is <br>");
    printArray(arr, arr_size);
  
// This code is contributed by SoumikMondal
  
</script>
Sayyed Aaman

tri par fusion

/* Java program for Merge Sort */
class MergeSort
{
    // Merges two subarrays of arr[].
    // First subarray is arr[l..m]
    // Second subarray is arr[m+1..r]
    void merge(int arr[], int l, int m, int r)
    {
        // Find sizes of two subarrays to be merged
        int n1 = m - l + 1;
        int n2 = r - m;
 
        /* Create temp arrays */
        int L[] = new int[n1];
        int R[] = new int[n2];
 
        /*Copy data to temp arrays*/
        for (int i = 0; i < n1; ++i)
            L[i] = arr[l + i];
        for (int j = 0; j < n2; ++j)
            R[j] = arr[m + 1 + j];
 
        /* Merge the temp arrays */
 
        // Initial indexes of first and second subarrays
        int i = 0, j = 0;
 
        // Initial index of merged subarray array
        int k = l;
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                arr[k] = L[i];
                i++;
            }
            else {
                arr[k] = R[j];
                j++;
            }
            k++;
        }
 
        /* Copy remaining elements of L[] if any */
        while (i < n1) {
            arr[k] = L[i];
            i++;
            k++;
        }
 
        /* Copy remaining elements of R[] if any */
        while (j < n2) {
            arr[k] = R[j];
            j++;
            k++;
        }
    }
 
    // Main function that sorts arr[l..r] using
    // merge()
    void sort(int arr[], int l, int r)
    {
        if (l < r) {
            // Find the middle point
            int m =l+ (r-l)/2;
 
            // Sort first and second halves
            sort(arr, l, m);
            sort(arr, m + 1, r);
 
            // Merge the sorted halves
            merge(arr, l, m, r);
        }
    }
 
    /* A utility function to print array of size n */
    static void printArray(int arr[])
    {
        int n = arr.length;
        for (int i = 0; i < n; ++i)
            System.out.print(arr[i] + " ");
        System.out.println();
    }
 
    // Driver code
    public static void main(String args[])
    {
        int arr[] = { 12, 11, 13, 5, 6, 7 };
 
        System.out.println("Given Array");
        printArray(arr);
 
        MergeSort ob = new MergeSort();
        ob.sort(arr, 0, arr.length - 1);
 
        System.out.println("\nSorted array");
        printArray(arr);
    }
}
/* This code is contributed by Rajat Mishra */
Pankaj Kumar Prasad

Réponses similaires à “tri par fusion”

Questions similaires à “tri par fusion”

Plus de réponses similaires à “tri par fusion” dans Java

Parcourir les réponses de code populaires par langue

Parcourir d'autres langages de code