Triển khai (phần 1)

Bài học 5 trên 9 trong khóa học Sắp xếp nhanh: chuỗi DSA của Coddy.

Chúng ta sẽ xây dựng Quick Sort từ thao tác cốt lõi trở lên.

Thử thách

Dễ

Trọng tâm của Quick Sort là bước phân hoạch. Trước tiên, hãy xây dựng bước này.

Viết một hàm (function) có tên partition, dùng phần tử cuối cùng của arr làm chốt và trả về một mảng mới gồm:

tất cả phần tử nhỏ hơn chốt, theo thứ tự ban đầu,
tiếp theo là chốt,
cuối cùng là tất cả phần tử còn lại, tức những phần tử lớn hơn hoặc bằng chốt, theo thứ tự ban đầu.

Ví dụ, [3, 7, 1, 8, 5] trở thành [3, 1, 5, 7, 8] (chốt 5).

Tự làm thử

#include <stdlib.h>

int* partition(int* arr, int arr_size, int* returnSize) {
    // Viết code ở đây
    *returnSize = arr_size;
    return arr;
}

Tự kiểm tra

Bài học này có một bài trắc nghiệm ngắn. Bắt đầu bài học để trả lời và theo dõi tiến độ.

Tất cả bài học trong Sắp xếp nhanh: chuỗi DSA

1Giới thiệu

2Thuật toán

3Thử thách cuối cùng