Implementation (Part 1)

Урок 5 из 9 курса Быстрая сортировка — серия DSA на Coddy.

Мы построим быструю сортировку, начиная с её основной операции.

Задание

Легко

Сердцем быстрой сортировки (Quick Sort) является этап разделения (partition). Давайте сначала реализуем его.

Напишите функцию с именем partition, которая использует последний элемент массива arr в качестве опорного (pivot) и возвращает новый массив, содержащий:

все элементы меньше опорного (в их исходном порядке),
затем сам опорный элемент,
затем все остальные элементы, которые больше или равны опорному (в их исходном порядке).

Например, [3, 7, 1, 8, 5] превращается в [3, 1, 5, 7, 8] (опорный элемент 5).

Попробуйте сами

#include <stdlib.h>

int* partition(int* arr, int arr_size, int* returnSize) {
    // Напишите код здесь
    *returnSize = arr_size;
    return arr;
}

Проверьте себя

В этом уроке есть небольшой тест. Начните урок, чтобы ответить на вопросы и сохранить прогресс.

Все уроки раздела Быстрая сортировка — серия DSA

1Introduction

Introduction Motivation

2The Algorithm

How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)

Time and Space Complexity

3Final Challenges

Final Challenge #1 Final Challenge #2