Phân loại nhanh như một phương pháp lập trình

Năm 1960, K. A. Hoare đã phát triển một phương pháp phân loại nhanh chóng thông tin, trở thành nổi tiếng nhất. Ngày nay nó được sử dụng rộng rãi trong lập trình, vì nó có rất nhiều tính chất tích cực: nó có thể được sử dụng cho các trường hợp nói chung, đòi hỏi một sự gia tăng nhỏ trong bộ nhớ bổ sung, tương thích với các loại danh sách và thuận tiện cho việc triển khai. Nhưng cũng có những bất lợi khi phân loại nhanh: khi sử dụng trong công việc cho phép có nhiều lỗi và nó không ổn định.

Tuy nhiên, đây là phiên bản được nghiên cứu nhiều nhất. Sau sự xuất hiện của tính toán đầu tiên của Hoar, nhiều người tham gia vào nghiên cứu dày đặc của cô. Một cơ sở lớn đã được tạo ra trên các câu hỏi lý thuyết về việc tìm thời gian dành cho công việc, được hỗ trợ bởi dữ liệu thực nghiệm. Có những đề xuất thực sự để cải thiện thuật toán chính và tăng tốc độ làm việc.

Phân loại nhanh là rất phổ biến, nó có thể được tìm thấy ở khắp mọi nơi. Nó dựa trên phương pháp TList.Sort, tồn tại trong tất cả các phiên bản (ngoại trừ 1) của Delphi, chức năng thư viện của thời gian thực hiện, qsort trong C ++.

Nguyên tắc cơ bản của công việc có thể được hình thành như là "phân chia và chinh phục". Có một phân tích của danh sách thành hai nhóm và phân loại được thực hiện cho từng phần của chính nó. Sau đó, cần phải chú ý nhiều hơn đến quá trình tách, trong thời gian đó xảy ra những sự kiện sau: phần tử cơ sở được xác định và toàn bộ danh sách đã được chuyển đổi liên quan đến nó. Một nhóm các ứng cử viên được hình thành bên trái, các giá trị nhỏ hơn, tất cả những người khác được chuyển sang bên phải. Nó chỉ ra rằng các yếu tố chính trong danh sách được sắp xếp nằm ở vị trí chính xác của nó. Bước tiếp theo là gọi hàm sắp xếp đệ quy cho cả hai mặt của các phần tử liên quan đến cơ sở. Quá trình làm việc chỉ kết thúc khi danh sách chỉ chứa một phần tử, nghĩa là nó sẽ được sắp xếp. Do đó, để nắm vững chức năng lập trình như phân loại nhanh, cần phải biết các hoạt động của các thuật toán cấp thấp hơn: a) Lựa chọn phần tử cơ sở; B) hoán vị hiệu quả nhất của danh sách để có được hai bộ có giá trị nhỏ hơn và lớn hơn.

Chúng ta sẽ làm quen với nguyên tắc thứ nhất. Khi chọn một phần tử cơ sở, lý tưởng là nên chọn một trong số trung tâm từ danh sách. Sau đó, khi bị gãy, nó được chia thành hai nửa bằng nhau. Chỉ tính giá trị trung bình trong danh sách là rất khó, vì vậy ngay cả việc phân loại nhanh nhất cũng bỏ qua tính toán này ở bên cạnh. Nhưng việc chọn yếu tố chính với giá trị tối đa hoặc tối thiểu cũng không phải là lựa chọn tốt nhất. Trong trường hợp định nghĩa như vậy, một trong các danh sách được tạo sẽ được đảm bảo là rỗng, và cột thứ hai bị tràn. Do đó kết luận rằng như là một yếu tố cơ bản nên chọn một trong đó là gần với mức trung bình, nhưng xa hơn từ tối đa và tối thiểu.

Một khi bạn đã quyết định về sự lựa chọn, bạn có thể tiến hành các hoạt động của thuật toán phân vùng. Đây là những chu kỳ được gọi là nhanh chóng nội bộ. Tất cả mọi thứ được xây dựng trên hai chỉ số hoạt động nhanh: thứ nhất sẽ đi theo các yếu tố từ trái sang phải, thứ hai, ngược lại, từ phải sang trái. Các hoạt động thực hiện ở bên phải bắt đầu: chỉ số đi qua danh sách và so sánh tất cả các giá trị với một chính. Một chu kỳ được coi là hoàn chỉnh nếu có một phần tử nhỏ hơn hoặc bằng một cơ sở. Tức là, giá trị của chỉ số được so sánh và giảm. Ở phía bên trái, tác phẩm kết thúc khi một giá trị lớn hơn hoặc bằng được tìm thấy. Và ở đây giá trị của việc so sánh tăng lên.

Ở giai đoạn này của thuật toán phân vùng, có chứa một phân loại nhanh chóng, hai tình huống có thể phát sinh. Thứ nhất là chỉ số bên trái sẽ thấp hơn bên phải. Điều này cho biết lỗi, nghĩa là các mục đã được chỉ định nằm sai trật tự trong danh sách. Cách ra thay đổi địa điểm. Tình huống thứ hai là khi cả hai cột đều bằng nhau hoặc giao cắt. Điều này cho thấy sự tách biệt thành công của danh sách, nghĩa là công việc có thể được coi là hoàn chỉnh.