Tartalomjegyzék
- Bevezetés
- Mi az a Merge Sort a C++ nyelven
- Oszd meg és uralkodj megközelítés
- Egyesítési rendezési algoritmus
- A Merge Sort megvalósítása C++ nyelven
- Következtetés
1. Bemutatkozás
A számítástechnikában a rendezési algoritmusok az adatok növekvő vagy csökkenő sorrendbe rendezésére szolgálnak. Többféle rendezési algoritmus is rendelkezésre áll különböző tulajdonságokkal. Az összevonási rendezés a C++ egyik olyan módszere, amely képes rendezni a tömböket.
2. Mi az a Merge Sort a C++ nyelven
Az összevonási rendezés az oszd meg és uralkodj technikát használja, amely el tudja rendezni egy tömb elemeit. A C++ elemeinek listáját is rendezheti. A bemenetet két részre osztja, mindegyik felét egymástól függetlenül rendezi, majd a megfelelő sorrendben egyesíti.
3. Oszd meg és uralkodj megközelítés
A rendezési algoritmus egy oszd meg és uralkodj stratégiát alkalmaz, amely magában foglalja a bemeneti tömb felosztását kisebb altömbökre, külön-külön megoldja, majd az eredményeket összevonva rendezett kimenetet állít elő. Összevont rendezés esetén a tömb rekurzív módon két felére osztódik, amíg csak egy elem marad mindkét félben.
4. Összevonási rendezési algoritmus
Az összevonási rendezési algoritmus két fő lépésből áll: felosztásból és összevonásból. A lépések a következők:
4.1 Osztás
Az egyesített rendezési algoritmus egy oszd meg és uralkodj stratégiát követ egy tömb elemeinek rendezésére.
- Az algoritmus első lépése a tömbelemeket ellenőrzi. Ha egy elemet tartalmaz, akkor az már rendezettnek minősül, és az algoritmus változtatás nélkül ugyanazt a tömböt adja vissza.
- Ha a tömb egynél több elemet tartalmaz, akkor az algoritmus két részre osztja: a bal és a jobb felére.
- Az összevont rendezési algoritmust ezután rekurzívan alkalmazzák a tömb bal és jobb felére, hatékonyan felosztva azokat kisebb altömbökre, és egyenként rendezve őket.
- Ez a rekurzív folyamat mindaddig folytatódik, amíg az altömbök csak egy-egy elemet tartalmaznak (az 1. lépés szerint), ekkor egyesíthetők egy végső, rendezett kimeneti tömb létrehozásához.
4.2 Egyesítés
Most látni fogjuk a tömbök egyesítésének lépéseit:
- Az összevonási rendezési algoritmus első lépése egy üres tömb létrehozása.
- Az algoritmus ezután összehasonlítja a bemeneti tömb bal és jobb felének első elemeit.
- A két elem közül a kisebbiket hozzáadjuk az új tömbhöz, majd eltávolítjuk a bemeneti tömb megfelelő feléből.
- Ezután a 2-3. lépéseket addig ismételjük, amíg az egyik fél ki nem ürül.
- A nem üres felében megmaradt elemek ezután hozzáadódnak az új tömbhöz.
- Az eredményül kapott tömb most már teljesen rendezve van, és az összevonási rendezési algoritmus végső kimenetét jelenti.
5. A Merge Sort megvalósítása C++ nyelven
Az összevonási rendezés megvalósításához C++-ban két különböző módszert követünk. Mindkét módszer időbeli összetettsége megegyezik, de az ideiglenes alrendszerek használata eltérő.
A C++ összevonási rendezés első módszere két ideiglenes altömböt használ, míg a második csak egyet. Érdemes megjegyezni, hogy az első módszerben a két ideiglenes altömb teljes mérete megegyezik a második módszer eredeti tömbjének méretével, így a tér összetettsége állandó marad.
1. módszer – Két ideiglenes alrendszer használata
Íme egy példaprogram a C++ összevonási rendezésre az 1. módszerrel, amely két ideiglenes altömböt használ:
#includenévtér std használatával ;
üres összeolvad ( int arr [ ] , int l , int m , int r )
{
int n1 = m - l + 1 ;
int n2 = r - m ;
int L [ n1 ] , R [ n2 ] ;
számára ( int én = 0 ; én < n1 ; én ++ )
L [ én ] = arr [ l + én ] ;
számára ( int j = 0 ; j < n2 ; j ++ )
R [ j ] = arr [ m + 1 + j ] ;
int én = 0 , j = 0 , k = l ;
míg ( én < n1 && j < n2 ) {
ha ( L [ én ] <= R [ j ] ) {
arr [ k ] = L [ én ] ;
én ++;
}
más {
arr [ k ] = R [ j ] ;
j ++;
}
k ++;
}
míg ( én < n1 ) {
arr [ k ] = L [ én ] ;
én ++;
k ++;
}
míg ( j < n2 ) {
arr [ k ] = R [ j ] ;
j ++;
k ++;
}
}
üres mergeSort ( int arr [ ] , int l , int r )
{
ha ( l < r ) {
int m = l + ( r - l ) / 2 ;
mergeSort ( arr , l , m ) ;
mergeSort ( arr , m + 1 , r ) ;
összeolvad ( arr , l , m , r ) ;
}
}
int fő- ( )
{
int arr [ ] = { 12 , tizenegy , 13 , 5 , 6 , 7 } ;
int arr_size = mérete ( arr ) / mérete ( arr [ 0 ] ) ;
cout << 'Az adott tömb az \n ' ;
számára ( int én = 0 ; én < arr_size ; én ++ )
cout << arr [ én ] << ' ' ;
mergeSort ( arr , 0 , arr_size - 1 ) ;
cout << ' \n Rendezett tömb van \n ' ;
számára ( int én = 0 ; én < arr_size ; én ++ )
cout << arr [ én ] << ' ' ;
Visszatérés 0 ;
}
Ebben a programban az egyesítő függvény három arr, l és r argumentumot vesz fel, amelyek a rendezendő tömböt jelölik, és megmutatják az egyesítendő altömb indexeit. A függvény először megkeresi az egyesítendő két altömb méretét, majd létrehoz két ideiglenes L és R altömböt, amelyek ezeknek az altömböknek az elemeit tárolják. Ezután összehasonlítja az L és R elemeket, és egyesíti őket az eredeti nevű tömbbe arr növekvő sorrendben.
Az oszd meg és uralkodj technikát a mergeSort függvény használja a tömb rekurzív két felére való felosztására, amíg csak egy elem marad ki az altömbből. Ezután összevonja a két altömböt egy rendezett altömbbe. A függvény továbbra is egyesíti az altömböket, hacsak nem rendezi a teljes tömböt.
A fő függvényben definiálunk egy 6 elemű tömböt és a mergeSort függvényt hívjuk a rendezéshez. A kód végén a rendezett tömb kerül kinyomtatásra.
2. módszer – Egy ideiglenes alrendszer használata
Íme egy példaprogram a C++-ban a 2-es metódussal történő egyesítésre, amely egyetlen ideiglenes altömböt használ:
#includenévtér std használatával ;
üres összeolvad ( int arr [ ] , int l , int m , int r )
{
int én , j , k ;
int n1 = m - l + 1 ;
int n2 = r - m ;
// Ideiglenes altömbök létrehozása
int L [ n1 ] , R [ n2 ] ;
// Adatok másolása altömbökbe
számára ( én = 0 ; én < n1 ; én ++ )
L [ én ] = arr [ l + én ] ;
számára ( j = 0 ; j < n2 ; j ++ )
R [ j ] = arr [ m + 1 + j ] ;
// Az ideiglenes altömbök visszafűzése az eredeti tömbbe
én = 0 ;
j = 0 ;
k = l ;
míg ( én < n1 && j < n2 ) {
ha ( L [ én ] <= R [ j ] ) {
arr [ k ] = L [ én ] ;
én ++;
}
más {
arr [ k ] = R [ j ] ;
j ++;
}
k ++;
}
// L[] többi elemének másolása
míg ( én < n1 ) {
arr [ k ] = L [ én ] ;
én ++;
k ++;
}
// Másolja az R[] többi elemét
míg ( j < n2 ) {
arr [ k ] = R [ j ] ;
j ++;
k ++;
}
}
üres mergeSort ( int arr [ ] , int l , int r )
{
ha ( l < r ) {
int m = l + ( r - l ) / 2 ;
// Rekurzívan rendezi a bal és a jobb oldalt
mergeSort ( arr , l , m ) ;
mergeSort ( arr , m + 1 , r ) ;
// A két rendezett fél egyesítése
összeolvad ( arr , l , m , r ) ;
}
}
int fő- ( )
{
int arr [ ] = { 12 , tizenegy , 13 , 5 , 6 , 7 } ;
int arr_size = mérete ( arr ) / mérete ( arr [ 0 ] ) ;
cout << 'Az adott tömb az \n ' ;
számára ( int én = 0 ; én < arr_size ; én ++ )
cout << arr [ én ] << ' ' ;
mergeSort ( arr , 0 , arr_size - 1 ) ;
cout << ' \n Rendezett tömb van \n ' ;
számára ( int én = 0 ; én < arr_size ; én ++ )
cout << arr [ én ] << ' ' ;
Visszatérés 0 ;
}
Ez a program hasonló az előzőhöz, de ahelyett, hogy két ideiglenes L és R altömböt használna, egyetlen ideiglenes altömb hőmérsékletet használ. Az egyesítési funkció ugyanúgy működik, mint korábban, de ahelyett, hogy az adatokat L és R-re másolja, a temp-ba másolja azokat. Ezután visszaolvasztja a temp tömb elemeit a arr amely az eredeti tömb.
A mergeSort függvény ugyanaz, mint korábban, azzal a különbséggel, hogy az L és R helyett a temp függvényt használja az ideiglenes altömb tárolására.
A fő függvényben definiálunk egy 6 elemű tömböt és a mergeSort függvényt hívjuk a rendezéshez. A kód végrehajtása a rendezett tömb képernyőre történő kinyomtatásával ér véget.
Következtetés
A Merge sort egy olyan algoritmus, amely tömbelemeket rendez, és az oszd meg és uralkodj technikát használ, és összehasonlításokat végez az elemek között. A C++-ban az összevonási rendezés O(n log n) időbonyolítású, és különösen hatékony nagy tömbök rendezésére. Bár további memóriát igényel az egyesített alrendszerek tárolása, stabilitása miatt népszerű választás a rendezéshez.