Flashcards on Összefésülő rendezés (merge sort)
Összefésülő rendezés (Merge Sort): Teljes elemzés és példák
Tap to flip · Swipe to navigate
Összefésülő rendezés
44 cards
Card 1
Question: Ki fejlesztette ki az összefésülő rendezést és mikor?
Answer: John von Neumann fejlesztette ki 1945-ben.
Card 2
Question: Mi az összefésülő rendezés célja?
Answer: Egy elemekből álló lista vagy tömb rendezése növekvő vagy csökkenő sorrendbe.
Card 3
Question: Milyen algoritmikus paradigmát követ az összefésülő rendezés?
Answer: Az „oszd meg és uralkodj” (divide and conquer) paradigmát.
Card 4
Question: Miért népszerű az összefésülő rendezés?
Answer: Stabilitása és kiszámítható teljesítménye miatt.
Card 5
Question: Milyen az összefésülő rendezés időkomplexitása és mit jelent ez?
Answer: O(n log n) minden esetben, ami azt jelenti, hogy a rendezés sebessége nem függ az adatok kezdeti elrendezésétől.
Card 6
Question: Mi az „oszd meg és uralkodj” paradigma első lépése?
Answer: Felosztás (Divide): A rendezendő listát felosztjuk két vagy több, azonos típusú, de kisebb alproblémára.
Card 7
Question: Hogyan történik a felosztás az összefésülő rendezésben?
Answer: A listát a középpontjánál kettévágjuk két nagyjából egyenlő méretű részre.
Card 8
Question: Mi az „oszd meg és uralkodj” paradigma második lépése?
Answer: Uralkodás (Conquer): Az alproblémákat rekurzívan megoldjuk, amíg azok olyan kicsik nem lesznek, hogy triviálisan megoldhatók.
Card 9
Question: Mi az összefésülő rendezés alapesete (base case) az „uralkodás” fázisban?
Answer: Egy egyelemű lista, amely definíció szerint már rendezett.
Card 10
Question: Mi az „oszd meg és uralkodj” paradigma harmadik lépése?
Answer: Összefésülés (Combine): Az alproblémák megoldásait egyesítjük, hogy megkapjuk az eredeti probléma megoldását.