# Zwei sortierte Listen zusammenfassen



## jLn (12. Dez 2008)

Hallo,

ich möchte zwei sortierte Listen zu einer Liste zusammenfassen, jedoch soll danach die eine Liste dann auch sortiert sein.
Ich habe mir ein paar Sortieralgorithmen angeschaut und kam bei meinem Problem auf folgendes Ergebnis:

Sorted Set1[1000] + Sorted Set2[1000] = Sorted Set3[2000]

(Vergleiche; Zuweisungen)
Bubble Sort: 1.499.500; 1.517.934
Insertion Sort: 500.380; 1.495.143
Heap Sort: 37.498; 59.118
Merge Sort: 16.294; 499.094
Quick Sort: 567.680; 14.763
Shell Sort: 12.371; 30.912

Was ist wichtiger, um mehr Performance zu erreichen? Niedrige Anzahl von Vergleichen oder Zuweisungen?
Z.B.: QuickSort hat zwar ca. 15.000 Zuweisungen weniger als ShellSort, aber dafür auch ungefähr 555.000 Vergleiche mehr! 
Oder gibt es andere Techniken, die man für das Problem anwenden könnte?


----------



## didjitalist (12. Dez 2008)

klar gibs andere techniken. wenn du zwei sortierte listen zusammenfügen willst. du musst im grunde immer nur das aktuell nächste element jeder liste vergleichen


```
Comparable o1, o2;
int n = 0;
for( int i = 0, m = Math.max( set1.length, set2.length ); i < m; ++i )
{
  o1 = o2 = null;
  if( i < set1.length )
    o1 = set1[ i ];
  if( i < set2.length )
    o2 = set2[ i ];
  if( o2 == null )
    sorted[ n++ ] = o1;
  else if( o1 == null )
    sorted[ n++ ] = o2;
  else
  {
    if( o1.compareTo( o2 ) < 0 )
    {
     sorted[ n++ ] = o1;
     sorted[ n++ ] = o2;
    }
    else
    {
      sorted[ n++ ]  = o2;
      sorted[ n++ ]  = o1;
    }
  }
}
```
komplett ungetester pseudocode.


----------



## SlaterB (12. Dez 2008)

mit nicht mehr als 2000 Vergleichen und 2000 Zuweisungen


----------



## musiKk (12. Dez 2008)

Also einfach das Merge von Mergesort.


----------



## jLn (13. Dez 2008)

okay, scheint ganz gut zu funktionieren =)
danke schön


----------



## jLn (13. Dez 2008)

nagut, funktioniert doch nicht so toll, z.B.:

set1 = [-923, -869, -861, -215, -67, -52, 151, 460, 717, 916]
set2 = [-634, -582, -411, -314, -100, 235, 418, 735, 927, 941]

sorted = [-923, -634, -869, -582, -861, -411, -314, -215, -100, -67, -52, 235, 151, 418, 460, 735, 717, 927, 916, 941]

Wenn ich wüßte was der Merge beim MergeSort ist, dann würde ich gerne das verwenden!
Jedoch ist der in meinem Fall nur in einer Methode gepackt ...
Könnt Ihr mir diesen Teil aus dem Source-Code rausziehen, ich hab nähmlich keine Ahnung welcher part das ist:


```
private void sort(int a[],int lo0,int hi0) {
		int lo = lo0;
		int hi = hi0;
		int mid = (lo + hi) / 2;
		int end_lo = mid;
		int start_hi = mid + 1;

		if(lo>=hi) {
			super.comparisions++;
		    return;
		}
		super.comparisions++;

		sort(a,lo,mid);
		sort(a,mid+1,hi);

		while ((lo<=end_lo) && (start_hi<=hi)) {
			if (a[lo]<a[start_hi]) {
				lo++;
			} else {
				int T = a[start_hi];

				super.copyOperations++;

				for (int k=start_hi-1;k>=lo;k--) {
					a[k+1] = a[k];
					super.copyOperations++;
				}

				a[lo] = T;
				lo++;
				end_lo++;
				start_hi++;
				super.copyOperations++;
			}
			super.comparisions++;
		}
	}
```


----------



## musiKk (13. Dez 2008)

Die Struktur von Mergesort ist:
- Teilen
- rekursives Aufrufen mit beiden Hälften
- Merge

So ist das auch in deinem Beispiel.


----------



## SebiB90 (14. Dez 2008)

Schreib doch ein eigenes Merge. Ist doch eigentlich ganz einfach.
Als Pseudocode

```
Erzeuge Set3 mit größe Set1.length + Set2.length
i = 0 //index für Set1
j = 0 //index für Set2
Für k = 0 bis Set3.length-1
    Wenn Set1[i] < Set2[j] 
        Set3[k] = Set1[i]
        i++
    Sonst
        Set3[k] = Set2[j]
        j++
```
Code ungetestet


----------



## jLn (14. Dez 2008)

ok stimmt eigentlich, war net schwer ... hätte ich trotzdem mal von alleine drauf kommen können
danke für die Hilfe, hier ist jetzt meine Lösung, die auch prima funktioniert:


```
public int[] merge(int[] set1,int[] set2) {
		int[] set = new int[set1.length + set2.length];
		int j = 0;
		int k = 0;

		for(int i=0;i<set.length;i++) {
			if(set1.length > j && set2.length == k) {
				set[i] = set1[j++];
			} else if(set2.length > k && set1.length == j) {
				set[i] = set2[k++];
			} else {
				if(set1[j] < set2[k]) {
					set[i] = set1[j++];
				} else {
					set[i] = set2[k++];
				}
			}
		}

		return set;
	}
```


----------

