Implementacja (część 1)

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

Zbudujemy Quick Sort, zaczynając od jego podstawowej operacji.

Wyzwanie

Łatwy

Sercem Quick Sort jest etap podziału. Zacznijmy właśnie od niego.

Napisz funkcję o nazwie partition, która używa ostatniego elementu tablicy arr jako elementu osiowego i zwraca nową tablicę zawierającą:

wszystkie elementy mniejsze od elementu osiowego (w pierwotnej kolejności),
następnie element osiowy,
a potem wszystkie pozostałe elementy, czyli te większe od lub równe elementowi osiowemu (w pierwotnej kolejności).

Na przykład [3, 7, 1, 8, 5] staje się [3, 1, 5, 7, 8] (element osiowy 5).

Spróbuj swoich sił

#include <stdlib.h>

int* partition(int* arr, int arr_size, int* returnSize) {
    // Wpisz 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

2Algorytm

3Wyzwania końcowe

Poćwicz samodzielnie: Kompilator C online