rendezési algoritmus

• IPA:

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.

• Ö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)).

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

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

# Példa
print(bubble_sort())

#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 > arr) {
                swap(arr, arr);
            }
        }
    }
}

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

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

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

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

# Példa
print(selection_sort())

#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 < arr) {
                min_idx = j;
            }
        }
        swap(arr, arr);
    }
}

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

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

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

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

# Példa
print(insertion_sort())

#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;
        int j = i - 1;
        while (j >= 0 && arr > key) {
            arr = arr;
            j--;
        }
        arr = key;
    }
}

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

• 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)).

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)

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr
    left = 
    middle = 
    right = 
    return quick_sort(left) + middle + quick_sort(right)

# Példa
print(quick_sort())

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

int partition(vector<int>& arr, int low, int high) {
    int pivot = arr;
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (arr < pivot) {
            i++;
            swap(arr, arr);
        }
    }
    swap(arr, arr);
    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;
}

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.

• rendezési algoritmus - Értelmező szótár (MEK)
• rendezési algoritmus - Etimológiai szótár (UMIL)
• rendezési algoritmus - Szótár.net (hu-hu)
• rendezési algoritmus - DeepL (hu-de)
• rendezési algoritmus - Яндекс (hu-ru)
• rendezési algoritmus - Google (hu-en)
• rendezési algoritmus - Helyesírási szótár (MTA)
• rendezési algoritmus - Wikidata
• rendezési algoritmus - Wikipédia (magyar)