Wikiszótár

beszúrásos rendezés

Magyar

Kiejtés

  • IPA: [ ˈbɛsuːraːʃoʃrɛndɛzeːʃ]

Főnév

beszúrásos rendezés

  1. (matematika, algoritmusok) A beszúrásos rendezés egy egyszerű, de hatékony rendezési algoritmus, amely kis méretű adathalmazok esetén jól működik. Az algoritmus úgy működik, hogy az elemeket egyenként veszi fel egy rendezett részhalmazba, miközben minden új elemet a megfelelő helyre szúr be, hogy az aktuális részhalmaz mindig rendezett maradjon.


Elméleti működés

Algoritmus lépései:

  1. Kezdjük a lista második elemével, mivel az első elem önmagában rendezettnek tekinthető.
  2. Vegyük az aktuális elemet (kulcs), és hasonlítsuk össze a bal oldali elemekkel.
  3. Mozgassuk azokat az elemeket, amelyek nagyobbak a kulcsnál, egy pozícióval jobbra.
  4. Helyezzük be a kulcsot a megfelelő pozícióba.
  5. Ismételjük a folyamatot a lista végéig.


Tulajdonságok

  • Időkomplexitás:
    • Legrosszabb eset: (O(n^2)) (ha a lista fordított sorrendű).
    • Legjobb eset: (O(n)) (ha a lista már rendezett).
  • Térkomplexitás: (O(1)) (helyben működik, nincs szükség extra memóriára).
  • Stabilitás: Stabil (azonos értékek sorrendje nem változik).


Pszeudokód

InsertionSort(A):
    n = A hossz
    ciklus i = 1-től n-1-ig:
        kulcs = A[i]
        j = i - 1
        amíg j >= 0 és A[j] > kulcs:
            A[j+1] = A[j]
            j = j - 1
        A[j+1] = kulcs

Python implementáció

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        # Mozgassuk a nagyobb elemeket jobbra
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        # Helyezzük be a kulcsot a megfelelő helyre
        arr[j + 1] = key

# Példa
data = [12, 11, 13, 5, 6]
insertion_sort(data)
print("Rendezett tömb:", data)
# Kimenet: Rendezett tömb: [5, 6, 11, 12, 13]

C++ implementáció

#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;

        // Mozgassuk a nagyobb elemeket jobbra
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            --j;
        }
        // Helyezzük be a kulcsot a megfelelő helyre
        arr[j + 1] = key;
    }
}

int main() {
    vector<int> data = {12, 11, 13, 5, 6};
    insertionSort(data);

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

    return 0;
}

Összegzés

A beszúrásos rendezés egyszerűsége miatt népszerű, különösen oktatási célokra. Kis adathalmazokon hatékony, és mivel helyben működik, memóriahasználata minimális. Nagyobb adathalmazokon azonban más rendezési algoritmusok, például a gyorsrendezés vagy a merge sort, hatékonyabbak.

Fordítások

További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=beszúrásos_rendezés&oldid=3479442”