QuickSort

QuickSort, to algorytm sortowania używający podejścia "dziel i zwyciężaj". Jest to jeden z najbardziej popularnych algorytmów sortowania i często używany w praktyce ze względu na swoją wydajność. Algorytm został opracowany przez Tony'ego Hoare'a w 1960 roku.

Podstawowa idea QuickSorta to wybieranie elementu z tablicy, zwanej "pivotem", a następnie dzielenie tablicy na dwie części - elementy mniejsze od pivota i elementy większe od pivota. Proces ten jest powtarzany rekurencyjnie dla obu podtablic, aż cała tablica zostanie posortowana.

Kod algorytmu QuickSort może wyglądać tak:

def quicksort(tablica):
    if len(tablica) <= 1:
        return tablica
    else:
        pivot = tablica.pop()
        mniejsze = []
        wieksze = []

        for element in tablica:
            if element <= pivot:
                mniejsze.append(element)
            else:
                wieksze.append(element)

        return quicksort(mniejsze) + [pivot] + quicksort(wieksze)

# Przykład użycia
nieposortowana_tablica = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
posortowana_tablica = quicksort(nieposortowana_tablica)

print("Nieposortowana tablica:", nieposortowana_tablica)
print("Posortowana tablica:", posortowana_tablica)

Kod algorytmu QuickSort bez listy pomocniczej może wyglądać tak:

def quicksort(tablica, lewy, prawy):
    if lewy < prawy:
        pivot_index = partition(tablica, lewy, prawy)
        quicksort(tablica, lewy, pivot_index - 1)
        quicksort(tablica, pivot_index + 1, prawy)

def partition(tablica, lewy, prawy):
    pivot = tablica[prawy]
    i = lewy - 1

    for j in range(lewy, prawy):
        if tablica[j] <= pivot:
            i = i + 1
            tablica[i], tablica[j] = tablica[j], tablica[i]

    tablica[i + 1], tablica[prawy] = tablica[prawy], tablica[i + 1]
    return i + 1

# Przykład użycia
nieposortowana_tablica = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
quicksort(nieposortowana_tablica, 0, len(nieposortowana_tablica) - 1)

print("Posortowana tablica:", nieposortowana_tablica)