Wikiszótár

rendezési algoritmus

Magyar

Kiejtés

  • IPA: [ ˈrɛndɛzeːʃiɒlɡoritmuʃ]

Főnév

rendezési algoritmus

  1. (matematika)

A rendezési algoritmusok alapvetőek az informatika számos területén. Az alábbiakban bemutatok néhány ismert rendezési algoritmust, elméleti leírásukkal, pszeudokóddal, és Python és C++ példákkal.


1. Buborékrendezés (Bubble Sort)

Elmélet

  • Összehasonlítja az egymás melletti elemeket, és ha szükséges, felcseréli őket.
  • Több lépésben végighalad a listán, amíg az teljesen rendezetté nem válik.
  • Időbonyolultság: (O(n^2)).

Pszeudokód

function BubbleSort(arr):
    n = arr hosszúsága
    ismételd n-1 alkalommal:
        az utolsó rendezett elemekig iterálj:
            ha arr[i] > arr[i+1]:
                cseréld meg arr[i] és arr[i+1]

Python

def bubble_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        for j in range(n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

# Példa
print(bubble_sort([64, 34, 25, 12, 22, 11, 90]))

C++

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

void bubbleSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);
            }
        }
    }
}

int main() {
    vector<int> arr = {64, 34, 25, 12, 22, 11, 90};
    bubbleSort(arr);
    for (int x : arr)
        cout << x << " ";
    return 0;
}

2. Kiválasztásos rendezés (Selection Sort)

Elmélet

  • Minden iterációban megkeresi a legkisebb elemet, és a lista elejére helyezi.
  • Időbonyolultság: (O(n^2)).

Pszeudokód

function SelectionSort(arr):
    n = arr hosszúsága
    minden elemre i:
        legkisebb = i
        az i+1-től végig iterálj:
            ha arr[j] < arr[legkisebb]:
                legkisebb = j
        cseréld arr[i] és arr[legkisebb]

Python

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_idx = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

# Példa
print(selection_sort([64, 25, 12, 22, 11]))

C++

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

void selectionSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n - 1; i++) {
        int min_idx = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[min_idx]) {
                min_idx = j;
            }
        }
        swap(arr[i], arr[min_idx]);
    }
}

int main() {
    vector<int> arr = {64, 25, 12, 22, 11};
    selectionSort(arr);
    for (int x : arr)
        cout << x << " ";
    return 0;
}

3. Beszúró rendezés (Insertion Sort)

Elmélet

  • Az elemeket egyenként kiválasztja és a már rendezett részbe beszúrja.
  • Időbonyolultság: (O(n^2)).

Pszeudokód

function InsertionSort(arr):
    n = arr hosszúsága
    minden elemre i = 1-től n-1-ig:
        kulcs = arr[i]
        j = i - 1
        amíg j >= 0 és arr[j] > kulcs:
            arr[j+1] = arr[j]
            j -= 1
        arr[j+1] = kulcs

Python

def insertion_sort(arr):
    n = len(arr)
    for i in range(1, n):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

# Példa
print(insertion_sort([64, 25, 12, 22, 11]))

C++

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

void insertionSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

int main() {
    vector<int> arr = {64, 25, 12, 22, 11};
    insertionSort(arr);
    for (int x : arr)
        cout << x << " ";
    return 0;
}

4. Gyorsrendezés (Quick Sort)

Elmélet

  • Egy elemet (pivot) választ, és az elemeket két részre osztja: kisebbek és nagyobbak, mint a pivot.
  • Rekurzívan folytatja a rendezést.
  • Időbonyolultság: Átlagosan (O(n n)), legrosszabb esetben (O(n^2)).

Pszeudokód

function QuickSort(arr, bal, jobb):
    ha bal < jobb:
        pivot_index = Partition(arr, bal, jobb)
        QuickSort(arr, bal, pivot_index - 1)
        QuickSort(arr, pivot_index + 1, jobb)

Python

def quick_sort(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 quick_sort(left) + middle + quick_sort(right)

# Példa
print(quick_sort([64, 25, 12, 22, 11]))

C++

#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> arr = {64, 25, 12, 22, 11};
    quickSort(arr, 0, arr.size() - 1);
    for (int x : arr)
        cout << x << " ";
    return 0;
}

Összegzés

Az algoritmusok hatékonysága attól függ, hogy milyen környezetben és milyen adatokon futnak: - Egyszerűbb algoritmusok (Buborékrendezés, Kiválasztásos rendezés, Beszúró rendezés): Kis adathalmazra alkalmasak. - Gyorsabb algoritmusok (Gyorsrendezés, Merge Sort): Nagyobb adathalmazok kezelésére ideálisak.

Fordítások

Tartalom

További információk

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