Koktélrendezés
Koktélrendezés | |
A koktélrendezésre egy példa | |
Kategória | rendezési algoritmus |
Adatstruktúra | tömb |
Legrosszabb időbonyolultság | |
Legjobb időbonyolultság | |
Átlagos idő bonyolultság | |
Legrosszabb tár bonyolultság | |
Optimális | nem |
A koktélrendezés (cocktail sort) algoritmus egy tömb elemeinek sorba rendezésére. A buborékrendezés tökéletesített változata, mely két irányból megy végig a tömbön. Minimálisan bonyolultabb a buborékrendezésnél, de stabil marad, ugyanakkor kiküszöböli annak egyik problémáját, miszerint a nagy elemek gyorsan felemelkednek a helyükre (innen a „buborék” név), de a rossz helyen lévő kicsi elemek csak lassan süllyednek a helyükre.
A legrosszabb esetben itt is O(n²) műveletre van szükség, de ha a lista majdnem rendezett az elején, a műveletek száma közelebb van O(n)-hez mint a buborékrendezés esetén.
Példakód
C#
C# forráskód koktélrendezésre:
static void CocktailSort(int[] a, int n) { int begin = 0; int end = n - 1; bool swapped; do { swapped = false; for (int i = begin; i < end; i++) { if (a[i] > a[i + 1]) { Swap(ref a[i], ref a[i + 1]); swapped = true; } } end--; if (!swapped) break; swapped = false; for (int i = end; i > begin; i--) { if (a[i] < a[i - 1]) { Swap(ref a[i], ref a[i - 1]); swapped = true; } } begin++; } while (swapped); }
Python
Python forráskód koktélrendezésre:
def koktél(lista): #Pythonban használhatóak ékezetes változónevek és függvénynevek lenn = len(lista) start = 0 vég = lenn-1 for i in range(0, lenn): for j in range(start, vég): if lista[j] > lista[j+1]: temp = lista[j] lista[j] = lista[j+1] lista[j+1] = temp vég-=1 for k in range(vég, start,-1): if lista[k] < lista[k-1]: temp = lista[k] lista[k] = lista[k-1] lista[k-1] = temp start+=1 return lista
Kapcsolódó szócikkek
- Rendezés (programozás)
- Fésűs rendezés
- Gyorsrendezés
- Kupacrendezés
- Beszúrásos rendezés
- Informatikai portál • összefoglaló, színes tartalomajánló lap