Zwei sortierte Subarrays mit gleicher Länge zusammenfügen

Diskutiere Zwei sortierte Subarrays mit gleicher Länge zusammenfügen im Java Basics - Anfänger-Themen Bereich.
L

lennero

Hi.

Gibt es einen einfachen Weg, wie man zwei sortierte Subarrays gleicher Länge M (die sich in einem nicht sortierten Array befinden) in ein sortiertes Array überführt mit der Beeinträchtigung dass nur ein Hilfsarray der Länge M genutzt werden kann?

Code:
aus a = [2, 4, 6, 1, 3, 5] soll werden
a = [1, 2, 3, 4, 5, 6]

wobei nur aux = [0, 0, 0] als Hilfsarray genutzt werden darf
Hierbei soll die Länge der Subarrays der Methode als Parameter übergeben werden.

Folgender Code funktioniert zwar, aber ist ziemlich umständlich (meiner Meinung nach)

Hierbei wird zuerst die gesamte linke Teilhälfte ins Hilfarray gepackt, anschließend werden alle Werte der rechten Teilhälfte mit den Werten im Hilfsarray verglichen. Was am Ende im Hilfsarray übrig bleibt wird dann ans Ende des Arrays gepackt.
Java:
private static void merge(Comparable[] a, int lo, int hi, Comparable[] aux, int m)
    {
        int mid = lo + m - 1;
        int i = lo;
        int j = mid + 1;

        //fill the auxiliary array with values of left subarray
        int auxIndex = 0;
        for(int k = i; k <= mid ; k++)
        {
            aux[auxIndex++] = a[k];
        }

        auxIndex = 0;
        //merge both left and right subarrays
        for(int k = lo; k <= hi; k++)
        {
            if(aux[auxIndex].compareTo(a[j]) >= 0)
            {
                a[k] = a[j++];
            }
            else
            {
                a[k] = aux[auxIndex++];
            }
            
            if(j > hi) break;
            if(auxIndex > aux.length - 1) break;
        }
        
        //put the remaining items inside the array (if there are any)
        for(int k = auxIndex + m; k < a.length && auxIndex <= aux.length - 1; k++)
        {
            a[k] = aux[auxIndex++];
        }
    }

    public static void main(String[] args)
    {
        //Integer[] test = new Integer[]{9, 8, 4, 6, 1, 0, 4, 2};
        //System.out.println(Arrays.toString(test));
        //sortByBlock(test, 4);
        //System.out.println(Arrays.toString(test));
        
        int m = 3;
        Integer[] a = new Integer[]{2, 4, 6, 1, 3, 5};
        Integer[] aux = new Integer[m];
        System.out.println(Arrays.toString(a));
        merge(a, 0, 5, aux, m);
        System.out.println("Nach sortierung:\n" + Arrays.toString(a));
    }
}
 
H

httpdigest

Es geht sogar ohne ein Hilfsarray. Die Idee ist, dass man abwechselnd Arrayelemente vom linken oder rechten Teilarray "zieht" und entsprechend zwei Indizes verwaltet und weiterzählt. Wenn man zwei Elemente tauschen muss, dann shiftet man einfach alle Elemente zwischen dem aktuellen "linken" und "rechten" Index eins nach rechts und reduziert die Größe des rechten Teilarrays, indem man die "Mitte" nach rechts verschiebt.
Java:
public class MergeInPlace {
  public static <T extends Comparable<T>> void merge(T[] a, int m) {
    for (int i = 0, j = m; i < m && j < a.length;)
      if (a[i].compareTo(a[j]) < 0)
        i++;
      else if (a[i].compareTo(a[j]) > 0) {
        T v = a[j];
        for (int k = j++; k > i; k--)
          a[k] = a[k - 1];
        a[i++] = v;
        m++;
      }
  }
  public static void main(String[] args) {
    Integer[] a = { 2, 4, 6, 1, 3, 5 };
    merge(a, 3);
    System.out.println(java.util.Arrays.toString(a));
  }
}
 
J

JustNobody

@httpdigest wenn zwei Werte gleich sind, dann dürftest Du in einer Endlosschleife hängen, da i nicht verändert wird? Ich hätte daher im if auf <= geprüft und dann nur ein else ohne ein angehängtes if benutzt.
 
Thema: 

Zwei sortierte Subarrays mit gleicher Länge zusammenfügen

Passende Stellenanzeigen aus deiner Region:
Anzeige

Neue Themen

Anzeige

Anzeige
Oben