Zadanie z QuickSort

0

Witam,
Dostałem zadanie aby za pomocą QuickSorta wykonać sortowanie i dodatkowo zrobić następujące podpunkty:
Dane przyjmowane na wejściu:

  • n: ilość liczb
  • a1…an: liczby do posortowania
    Dane zwracane:
  • posortowany ciąg liczb
  • ilość operacji wykonanych podczas działania algorytmu
  • operacje zamiany oraz wyniki pośrednie

Pytanie moje brzmi co mam zwrócić na wyjściu gdy treść brzmi -> "ilości operacji wykonanych podczas działania algorytmu".
Chodzi tutaj tylko o ilość wykonanych operacji zamian liczb czy też np.: inkrementacja w pętli for itp.?
Z góry dzięki za odpowiedź.

0

Nie jest to jasno określone, musiałbyś zapytać autora zadania.

0

Strzelałbym że chodzi o ilość porównań albo ilość swapów. Jak nie wiesz które liczyć to licz wszystkie.

0

Ilość operacji w sortowaniu to będzie ilość porównań, quicksort(wikipedia):

algorithm quicksort(A, lo, hi) is
    if lo < hi then
        p := partition(A, lo, hi)
        quicksort(A, lo, p)
        quicksort(A, p + 1, hi)

algorithm partition(A, lo, hi) is
    pivot := A[(hi + lo) / 2]
    i := lo - 1
    j := hi + 1
    loop forever
        do
            i := i + 1
        while A[i] < pivot
        do
            j := j - 1
        while A[j] > pivot
        if i ≥ j then
            return j
        swap A[i] with A[j]

Z tego wynika, że trzeba, przesłany adresem, licznik inkrementować w obydwu pętlach do while. Tutaj:
https://stackoverflow.com/a/42711486
kod w C++ (nie testowałem).

1 użytkowników online, w tym zalogowanych: 0, gości: 1