Wikiszótár

gyorsrendezés

Magyar

Kiejtés

  • IPA: [ ˈɟorʃrɛndɛzeːʃ]

Főnév

gyorsrendezés

  1. (matematika, algoritmusok) A gyorsrendezés egy oszd meg és uralkodj alapú rendezési algoritmus, amely hatékonyan rendez nagy adathalmazokat. Az algoritmus a bemeneti tömböt kisebb részekre bontja, majd azokat rekurzívan rendezi. A gyorsrendezés az egyik leggyorsabb általános célú rendezési algoritmus.


Algoritmus működése

  1. Pivot kiválasztása:
    • Válasszunk egy elemet (pivot) a tömbből. Ez lehet az első elem, az utolsó elem, egy véletlenszerű elem, vagy a középső elem.
  2. Particionálás:
    • A tömb elemeit két részre osztjuk:
      • Az egyik rész tartalmazza azokat az elemeket, amelyek kisebbek vagy egyenlőek a pivotnál.
      • A másik rész tartalmazza azokat, amelyek nagyobbak.
  3. Rekurzió:
    • A fenti lépést alkalmazzuk mindkét részre (a pivot nélkül), amíg a részek mérete 1 vagy 0.
  4. Összefűzés:
    • A rendezett bal és jobb rész, valamint a pivot összefűzésével kapjuk a teljesen rendezett tömböt.


Tulajdonságok

  • Időkomplexitás:
    • Átlagos eset: (O(n n)).
    • Legrosszabb eset: (O(n^2)) (ha a pivot mindig a legkisebb vagy legnagyobb elem).
  • Térkomplexitás:
    • Helyben működő változat: (O(n)) (rekurzív hívások miatt).
    • Nem helyben működő változat: (O(n)).
  • Stabilitás:
    • Nem stabil, mivel a particionálás során az azonos elemek sorrendje megváltozhat.


Pszeudokód

QuickSort(A, bal, jobb):
    ha bal < jobb:
        p = Particionál(A, bal, jobb)
        QuickSort(A, bal, p - 1)
        QuickSort(A, p + 1, jobb)

Particionál(A, bal, jobb):
    pivot = A[jobb]
    i = bal - 1
    ciklus j = bal-tól jobb-1-ig:
        ha A[j] <= pivot:
            i = i + 1
            cseréljük meg A[i] és A[j] értékét
    cseréljük meg A[i + 1] és A[jobb] értékét
    visszatér i + 1

Python implementáció

Helyben működő gyorsrendezés

def quicksort(arr, low, high):
    if low < high:
        pi = partition(arr, low, high)
        quicksort(arr, low, pi - 1)
        quicksort(arr, pi + 1, high)

def partition(arr, low, high):
    pivot = arr[high]
    i = low - 1
    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

# Példa
data = [10, 7, 8, 9, 1, 5]
quicksort(data, 0, len(data) - 1)
print("Rendezett tömb:", data)
# Kimenet: Rendezett tömb: [1, 5, 7, 8, 9, 10]

Nem helyben működő gyorsrendezés (rekurzív osztással)

def quicksort_recursive(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quicksort_recursive(left) + middle + quicksort_recursive(right)

# Példa
data = [10, 7, 8, 9, 1, 5]
sorted_data = quicksort_recursive(data)
print("Rendezett tömb:", sorted_data)
# Kimenet: Rendezett tömb: [1, 5, 7, 8, 9, 10]

C++ implementáció

#include <iostream>
#include <vector>
using namespace std;

int partition(vector<int>& arr, int low, int high) {
    int pivot = arr[high];
    int i = low - 1;

    for (int j = low; j < high; ++j) {
        if (arr[j] <= pivot) {
            ++i;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]);
    return i + 1;
}

void quicksort(vector<int>& arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quicksort(arr, low, pi - 1);
        quicksort(arr, pi + 1, high);
    }
}

int main() {
    vector<int> data = {10, 7, 8, 9, 1, 5};
    quicksort(data, 0, data.size() - 1);

    cout << "Rendezett tömb: ";
    for (int num : data) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

Optimalizációk

  1. Pivot kiválasztása:
    • A középső elem vagy egy véletlenszerű elem választása csökkenti a legrosszabb eset valószínűségét.
  2. Kis méretű tömbök rendezése:
    • Kis tömböknél ((n < 10)) érdemes buborék- vagy beszúrásos rendezésre váltani.
  3. Tail Recursion:
    • A rekurzió mélységének csökkentése érdekében a kisebb részt mindig rekurzívan dolgozzuk fel először.


Összegzés

A gyorsrendezés az egyik leghatékonyabb és leggyakrabban használt rendezési algoritmus, különösen nagy adathalmazok esetén. Bár a legrosszabb esetben (O(n^2)) időigényű, az átlagos (O(n n)) időkomplexitás és az alacsony memóriaigény miatt széles körben alkalmazzák. Optimalizációkkal és helyes pivotválasztással az algoritmus szinte minden esetben gyors és hatékony.

Fordítások

További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=gyorsrendezés&oldid=3479461”