Implementacja (część 2)

Lekcja 6 z 9 w kursie Sortowanie szybkie — seria DSA w Coddy.

Teraz połączymy element dzielący, partycjonowanie i rekurencję w pełny algorytm.

Wyzwanie

Łatwy

Teraz połącz to wszystko w pełny algorytm.

Napisz funkcję o nazwie quickSort, która przyjmuje tablicę liczb całkowitych i zwraca ją posortowaną w kolejności rosnącej.

Użyj ostatniego elementu jako pivota, podziel pozostałe elementy na mniejszą i większą grupę, rekurencyjnie zastosuj quickSort do każdej grupy i połącz je jako posortowana-mniejsza + pivot + posortowana-większa. Tablica zawierająca 0 lub 1 element jest już posortowana, więc zwróć ją bez zmian.

Możesz ponownie wykorzystać pomysł na podział z poprzedniej lekcji.

Spróbuj swoich sił

#include <stdlib.h>

int* quickSort(int* arr, int arr_size, int* returnSize) {
    // Napisz kod tutaj
    *returnSize = arr_size;
    return arr;
}

Sprawdź się

Ta lekcja zawiera krótki quiz. Zacznij lekcję, żeby na niego odpowiedzieć i śledzić swoje postępy.

Wszystkie lekcje w sekcji Sortowanie szybkie — seria DSA

1Wprowadzenie

Wprowadzenie Motywacja

2Algorytm

Jak to działa?Pseudokod Implementacja (część 1)Implementacja (część 2) Lekcja projektowa

Złożoność czasowa i pamięciowa

3Wyzwania końcowe

Wyzwanie końcowe nr 1 Wyzwanie końcowe nr 2

Poćwicz samodzielnie: Kompilator C online