streamalism.org

1. Inleiding

In deze zelfstudie leren we hoe we twee gesorteerde arrays kunnen samenvoegen tot één gesorteerde array.

2. Probleem

Laten we het probleem begrijpen. We hebben twee gesorteerde arrays en we willen ze graag samenvoegen tot één.

3. Algoritme

Als we het probleem analyseren, Het is vrij eenvoudig om te zien dat we dit probleem kunnen oplossen door de samenvoegbewerking van Merge Sort te gebruiken.

Laten we zeggen dat we twee gesorteerde arrays hebben foo en bar van lengte fooLength en barLength, respectievelijk. Vervolgens kunnen we een andere array declareren samengevoegd van grootte fooLength + barLength.

We moeten dan beide arrays in dezelfde lus doorlopen. We behouden een huidige indexwaarde voor elk, fooPosition en barPosition. Op een gegeven iteratie van onze lus, we nemen de array met het element met de kleinere waarde in hun index en verhogen die index. Dit element zal de volgende positie in de samengevoegd array.

Als we ten slotte alle elementen van de ene array hebben overgebracht, kopiëren we de resterende van de andere naar de samengevoegd array.

Laten we nu het proces in afbeeldingen bekijken om het algoritme beter te begrijpen.

Stap 1:

We beginnen met het vergelijken van de elementen in beide arrays, en we kiezen de kleinere.

Vervolgens verhogen we de positie in de eerste array.

Stap 2:

Hier verhogen we de positie in de tweede array en ga verder met het volgende element dat 8 is.

Stap 3:

Aan het einde van deze iteratie hebben we alle elementen van het eerste array.

Stap 4:

In deze stap kopiëren we alle resterende elementen van het tweede array naar resultaat.

4. Implementatie

Laten we nu eens kijken hoe we het kunnen implementeren:

openbare statische int [] merge (int [] foo, int [] balk) {int fooLength = foo.length; int barLength = bar.length; int [] merged = nieuwe int [fooLength + barLength]; int fooPosition, barPosition, mergedPosition; fooPosition = barPosition = mergedPosition = 0; while (fooPosition <fooLength && barPosition <barLength) {if (foo [fooPosition] <bar [barPosition]) {merged [mergedPosition ++] = foo [fooPosition ++]; } else {merged [mergedPosition ++] = bar [barPosition ++]; }} while (fooPosition <fooLength) {merged [mergedPosition ++] = foo [fooPosition ++]; } while (barPosition <barLength) {merged [mergedPosition ++] = bar [barPosition ++]; } terugkeer samengevoegd; }

En laten we doorgaan met een korte test:

@Test openbare leegte gegevenTwoSortedArrays_whenMerged_thenReturnMergedSortedArray () {int [] foo = {3, 7}; int [] bar = {4, 8, 11}; int [] samengevoegd = {3, 4, 7, 8, 11}; assertArrayEquals (samengevoegd, SortedArrays.merge (foo, bar)); }

5. Complexiteit

We doorlopen beide arrays en kiezen het kleinere element. Uiteindelijk kopiëren we de rest van de elementen uit het foo of de bar array. Dus de tijdcomplexiteit wordt O (fooLength + barLength). We hebben een hulparray gebruikt om het resultaat te verkrijgen. Dus de complexiteit van de ruimte is dat ook O (fooLength + barLength).

6. Conclusie

In deze tutorial hebben we geleerd hoe we twee gesorteerde arrays kunnen samenvoegen tot één.

Zoals gewoonlijk is de broncode voor deze tutorial te vinden op GitHub.