Hoe stap voor stap het proces in MergeSort uit te printen

Ik heb problemen met het afdrukken van een MergeSort. Ik heb hulp nodig bij het afdrukken van elk stap voor stap proces, omdat het een ArrayList sorteert.

Het volgende voorbeeld is afkomstig van een InsertionSort, omdat ik deze altijd heb laten afdrukken bij het vervangen van twee elementen in de ArrayList:

11 79 60 45 START

11 79 60 45

11 60 79 45

11 45 60 79 FINISH

Is er hoe dan ook om dit te doen voor MergeSort terwijl de hele array van start tot finish wordt weergegeven (zoals hierboven?)

Code:

import java.util.ArrayList;

public class Merge 
{
    public static void main (String [] args) 
    {
        Merge run = new Merge();
        run.test();
    }

    public void test ( )
    {
        ArrayList numbers = new ArrayList();
        for (int i = 0; i < 16; i++)
        {
            numbers.add(new Integer(1 + (int)(Math.random() * 100)));
        }
        printArray(numbers);
        mergeSort(numbers);
        printArray(numbers);
    }

    public void printArray (ArrayList array)
    {
        System.out.println("\n\n");
        for (int i = 0; i < array.size(); i++)
        {
            System.out.printf("%-5d",array.get(i).intValue());
        }
        System.out.println("\n\n");
    }

    public void mergeSort (ArrayList array) 
    {   
        int length = array.size();
        if (length < 2)
        {
            return; //the array is already sorted in this case
        }
       //divide
        ArrayList array1 = new ArrayList(); 
        ArrayList array2 = new ArrayList(); 
        int i = 0;

        while (i < length/2)
        {
            array1.add(array.remove(0));//move the first n/2 elements to array1
            i++;
        }
        while (!array.isEmpty())
        {
            array2.add(array.remove(0));//move the rest to array2
        }

        mergeSort(array1);
        mergeSort(array2);
        merge(array1,array2,array); 
    }

    public void merge (ArrayList array1, ArrayList array2, ArrayList array)
    {   
        while (!array1.isEmpty() && !array2.isEmpty())
        {
            if ((array1.get(0).compareTo(array2.get(0)) <= 0))
            {
                array.add(array1.remove(0));
            }
            else
            {
                array.add(array2.remove(0));
            }
        }
        while(!array1.isEmpty())//move the remaining elements of array1
        {
            array.add(array1.remove(0));
        }
        while(!array2.isEmpty())//move the remaining elements of array2
        {
            array.add(array2.remove(0));
        }
    }
}
1
Prefix elke regel van uw code met 4 spaties om deze correct weer te geven in uw bericht.
toegevoegd de auteur Jon Lin, de bron
Wat betekent "mij steeds weer ontzeggen om de code te plaatsen"? Krijgt u een foutmelding? Zo ja, wat is het?
toegevoegd de auteur Ken White, de bron
Post de code die je tot nu toe hebt, en we kunnen helpen om van daaruit uit te breiden.
toegevoegd de auteur Beau Grantham, de bron
Het spijt mij van de vertraging; heb het opgelost.
toegevoegd de auteur yuritsuki, de bron

3 antwoord

Als u een of andere offset hebt doorgegeven aan mergeSort , kunt u mogelijk de subarray ingesprongen naar waar deze zich in de volledige array bevindt, terwijl u swaps maakt, maar omdat u alleen gedeelten van de array doorgeeft array down, kunt u de volledige array niet op deze manier weergeven. Er is echter een snellere manier om dit te doen.

In plaats van nieuwe arrays te maken en deze door te geven, geeft u de array en 2 indices door, het begin- en eindpunt. Dus je zegt mergeSort (array, 0, n) voor de eerste, dan mergeSort (array, 0, n/2) en mergeSort (array, n/2, n) voor de recursieve oproepen. Je doet je splijten en samenvoegen alleen binnen die grenzen. Vervolgens kunt u tijdens het samenvoegen de gehele samengevoegde array afdrukken. Dit zou de stap bij elke samenvoeging tonen. Op het onderste niveau zou het de 1-1 swap laten zien (als het voorkomt). Dat is de enige stap-voor-stap die je kon zien in een merge sortering.

2
toegevoegd

Hier is een klein algoritme Programma voor samenvoegen van sorteerbewerkingen. Ik heb het algoritme gekopieerd van http://en.wikipedia.org/wiki/Merge_sort . Je kunt het gewoon uitvoeren als JUnittest of de hoofdmethode uitvoeren.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import junit.framework.TestCase;

/**
 * Simple MergeSortTest
 */

public class MergeSortTest extends TestCase {


private static int FIRST_ENTRY = 0;

public static void main(String[] args) {
    MergeSortTest mergesorttest = new MergeSortTest();
    Integer [] unsortedInt = {1,38, 27, 110, 9, 82, 10, 100, 299, 13};
    List unsorted = Arrays.asList(unsortedInt);
    List sorted = mergesorttest.mergeSort(unsorted);
    System.out.println(sorted.toString());
}

public void testMergeSort() {
    Integer [] unsortedInt = {1,38, 27, 110, 9, 82, 10, 100, 299, 13};
    List unsorted = Arrays.asList(unsortedInt);
    List sorted = mergeSort(unsorted);
    assertEquals("[1, 9, 10, 13, 27, 38, 82, 100, 110, 299]", sorted.toString());
}

private List mergeSort(List list) {
    List result;
    List left = new ArrayList();
    List right = new ArrayList();;
    int middle;
    int counter;
    if (list.size() <= 1) {
        return list;
    }
    middle = list.size()/2;

    for (counter = 0; counter < middle; counter++)  {
        left.add(list.get(counter));
    }

    for (counter = middle; counter < list.size(); counter++)  {
        right.add(list.get(counter));
    }   

    left = mergeSort(left);
    right = mergeSort(right);
    result = merge(left, right);
    System.out.println(result);
    return result;
}

private List merge(List left, List right) {
    List result = new ArrayList();
    while (!left.isEmpty() || !right.isEmpty()) {
        if (!left.isEmpty() && !right.isEmpty()) {
            if (left.get(FIRST_ENTRY) <= right.get(FIRST_ENTRY)) {
                handle(left, result);
            } else {
                handle(right, result);
            }
        } else if (!left.isEmpty()) {
            handle(left, result);
        } else if (!right.isEmpty()) {
            handle(right, result);
        }
    }
    return result;  
}

private void handle(List list, List result) {
    if (!list.isEmpty()) {
        result.add(list.get(FIRST_ENTRY));
        list.remove(FIRST_ENTRY);
    }
}

}

1
toegevoegd

Zonder uw code te zien, is het moeilijk om precies te weten, maar ik heb hier een Mergesort-implementatie gepakt: http: //www.vogella.de/articles/JavaAlgorithmsMergesort/article.html .
Ik heb het bijgewerkt om af te drukken zoals je wilt.

public class Mergesort 
{
    private int[] numbers;
    private int[] helper;

    private int number;

    public void sort(int[] values) 
    {
        this.numbers = values;
        number = values.length;
        this.helper = new int[number];

        System.out.println("START");

        mergesort(0, number - 1);

        System.out.println("END");
    }

    private void mergesort(int low, int high) 
    {
       //Check if low is smaller then high, if not then the array is sorted
        if (low < high) 
        {
           //Get the index of the element which is in the middle
            int middle = (low + high)/2;
           //Sort the left side of the array
            mergesort(low, middle);
           //Sort the right side of the array
            mergesort(middle + 1, high);
           //Combine them both
            merge(low, middle, high);
        }
    }

    private void merge(int low, int middle, int high) 
    {

       //Copy both parts into the helper array
        for (int i = low; i <= high; i++) 
        {
            helper[i] = numbers[i];
        }

        int i = low;
        int j = middle + 1;
        int k = low;

       //Copy the smallest values from either the left or the right side back
       //to the original array
        while (i <= middle && j <= high) 
        {
            if (helper[i] <= helper[j]) 
            {
                numbers[k] = helper[i];
                i++;
            } 
            else 
            {
                numbers[k] = helper[j];
                j++;
            }
            k++;
        }

       //Copy the rest of the left side of the array into the target array
        while (i <= middle) 
        {
            numbers[k] = helper[i];
            k++;
            i++;
        }

    }

    private void printArray()
    {
        for(int x : numbers)
            System.out.print(x + " ");

        System.out.println(" ");
    }
}

Als u niet naar de console wilt afdrukken, kunt u de uitvoer naar een tekenreeks van de uitvoer bouwen en deze terugsturen als u klaar bent.

1
toegevoegd