Quick sort rendezési algoritmus

A Quick Sort algoritmus egy elválasztásos rendezési algoritmus, amely az „oszd meg és uralkodj” (divide and conquer) elvet alkalmazza. A működési elve a következő lépésekből áll:

1. Pivot kiválasztása
A Quick Sort első lépése a pivot elem kiválasztása. A pivot lehet bármi az adott listában, például az első, az utolsó, vagy a középső elem. A pivot elem lesz az alap, amely alapján az elemeket rendezni fogjuk.

2. Particionálás (Elválasztás)
A következő lépésben az algoritmus a pivot elem köré rendezi az elemeket:

Az összes olyan elemet, amely kisebb, mint a pivot, a pivot elé helyezi.
Az összes olyan elemet, amely nagyobb, mint a pivot, a pivot mögé helyezi.
Ezután a pivot helyet cserél a listában, így az véglegesen a megfelelő helyére kerül.

3. Rekurzív rendezés
Miután a pivot a megfelelő helyre került, az algoritmus rekurzívan meghívja magát a pivot bal és jobb oldalán lévő részekre (a pivot nem kerül újra rendezésre, mert már a megfelelő helyen van).

Az algoritmus újra végigmegy a kisebb és nagyobb elemek rendezésén a bal és jobb részekben.
A rekurzió folytatódik, amíg a listák nem tartalmaznak már több, mint egy elemet, ekkor azok rendezettek lesznek.

4. Befejezés
A rekurzió minden egyes szinten befejeződik, amikor minden részlista már rendezett. Az algoritmus végül egy rendezett listát ad vissza a részlisták egyesítésével.

def quick_sort(list):
    if len(list) <= 1:
        return list
    else:
        pivot = list[len(list) // 2]
        left = []
        middle = []
        right = []

        for x in list:
            if x < pivot:
                left.append(x)
            elif x == pivot:
                middle.append(x)
            else:
                right.append(x)

        return quick_sort(left) + middle + quick_sort(right)

# Példa a használatra
list = [10, 15, 4,21, 17,36, 2, 27, 45, 33, 29, 41, 9, 1, 5]
sorted_list = quick_sort(list)
print("Rendezett lista:", sorted_list)