PHP cũng đã cung cấp một số hàm sắp xếp nhanh (quick sort function) được dựng sẵn. Nhưng bạn cũng có thể tự xây dựng các hàm với thuật toán quicksort của riêng mình trong PHP.
Thuật toán Quicksort tự viết NHANH hay CHẬM?
Để so sánh Thuật toán sắp xếp tự dựng có nhanh hơn Thuật toán sắp xếp dựng sẵn thì...
Trước tiên, chúng ta sẽ thử xem
Ví dụ về tự dựng, tự viết một hàm sắp xếp nhanh (Thuật toán Quick sort) bằng PHP
Hàm sắp xếp nhanh bên dưới này đơn giản là tạo ra hai mảng trống để chứa các phần tử nhỏ hơn giá trị được so sánh và các phần tử lớn hơn giá trị so sánh, điều này sẽ yêu cầu thêm không gian lưu trữ.
Điều này sẽ ảnh hưởng đến tốc độ và hiệu quả đặc biệt khi đầu vào lớn.
Dưới đây là một ví dụ về cách triển khai Quick sort (sắp xếp) nhanh đơn giản trong PHP:
function simple_quick_sort($arr)
{
if(count($arr) <= 1){
return $arr;
}
else{
$pivot = $arr[0];
$left = array();
$right = array();
for($i = 1; $i < count($arr); $i++)
{
if($arr[$i] < $pivot){
$left[] = $arr[$i];
}
else{
$right[] = $arr[$i];
}
}
return (
array_merge(simple_quick_sort($left),
array($pivot), simple_quick_sort($right))
);
}
}
$unsorted = array(5,3,8,6,2,7);
echo implode(",",$unsorted)." Chưa sắp xếp<br>";
$sorted = simple_quick_sort($unsorted);
echo implode(",",$sorted)." Đã sắp xếp<br>";
Ví dụ về cách sắp xếp mảng tại chỗ In-Place sử dụng thuật toán Quick sort
Thuật toán sắp xếp nhanh tại chỗ thực hiện sắp xếp mảng bằng cách hoán đổi các thành phần mảng trong mảng đầu vào.
Do đó, nó không yêu cầu không gian lưu trữ nên thuật toán này cải thiện hiệu quả hơn ví dụ trên.
Mẹo ở đây là truyền mảng được sắp xếp là hàm partition và hàm quickSort làm tham chiếu, do đó việc sắp xếp xảy ra bên trong hàm sẽ ảnh hưởng trực tiếp đến mảng đầu vào bên ngoài hàm.
function partition(&$arr, $leftIndex, $rightIndex)
{
$pivot = $arr[($leftIndex + $rightIndex) / 2];
while ($leftIndex <= $rightIndex) {
while ($arr[$leftIndex] < $pivot)
$leftIndex++;
while ($arr[$rightIndex] > $pivot)
$rightIndex--;
if ($leftIndex <= $rightIndex) {
$tmp = $arr[$leftIndex];
$arr[$leftIndex] = $arr[$rightIndex];
$arr[$rightIndex] = $tmp;
$leftIndex++;
$rightIndex--;
}
}
echo implode(",", $arr) . " @pivot $pivot<br>";
return $leftIndex;
}
function quickSort(&$arr, $leftIndex, $rightIndex)
{
$index = partition($arr, $leftIndex, $rightIndex);
if ($leftIndex < $index - 1)
quickSort($arr, $leftIndex, $index - 1);
if ($index < $rightIndex)
quickSort($arr, $index, $rightIndex);
}
$nums = array(5, 3, 8, 6, 2, 7);
echo implode(",", $nums) . " Chưa sắp xếp<br>";
quickSort($nums, 0, count($nums) - 1);
echo implode(",", $nums) . " Đã sắp xếp<br>";
Kết quả chúng ta nhận được sẽ là:
538627 Chưa sắp xếp
537628 @pivot 8
532678 @pivot 7
235678 @pivot 3
235678 @pivot 2
235678 @pivot 5
235678 Đã sắp xếp
Trên đây chúng ta đã thử tự viết hàm sắp xếp nhanh trong PHP (Quicksort in PHP) Vậy thì,...
Tự viết thuật toán quick sort hay sử dụng hàm quick sort dựng sẵn trong PHP sẽ nhanh hơn?
Mình đã sử dụng bài toán sau để test trực tiếp:
-
Bài toán sắp xếp một mảng gồm 250.000 số nguyên bằng cách sử dụng native sort function và thuật toán quicksort tự viết bằng php.
Nội dung của mảng hoàn toàn giống nhau cho cả hai lần chạy, dữ liệu được chọn ngẫu nhiên và thời gian được báo cáo chỉ để thực hiện sắp xếp, không tính thời gian xử lý cần thiết khác để gọi trình thông dịch php.
Kết quả như sau:
Native sort implementation: 1.379 seconds
PHP quicksort implementation: 30.615 seconds
Chắc chắn là sử dụng Native sort chiến thắng.
Điều này là dĩ nhiên đối với bất kỳ phương án nào.
Kết quả cho các ngôn ngữ khác mà mình đã thử nghiệm với cùng điều kiện sử dụng cùng một phương án triển khai trên cùng một phần cứng và hệ điều hành.
Kết quả sẽ rất thú vị và bạn hãy đưa kết quả PHP vào so sánh thử xem nhé:
C: 0.107 seconds
Java: 0.250 seconds
JavaScript (FF3): 4.401 seconds
Điều đáng chú ý, Chrome và Safari đã thực hiện nhanh hơn nhiều khi mình thử nghiệm JavaScript, nhưng mình không tính đến những thử nghiệm đó ở đây, vì những thử nghiệm đó đã được ghi lại trong một môi trường khác.
Như bạn thấy, thực hiện sắp xếp viết bằng C là nhanh nhất.
Khi bạn tự viết thuật toán sắp xếp trong PHP thì có nghĩa là bạn đang sử dụng ngôn ngữ PHP.
Còn việc sử dụng hàm sắp xếp được dựng sẵn trong PHP (Built-in function) thì bạn phải hiểu là:
-
Các hàm cốt lõi của PHP sẽ được triển khai trong C, thay vì PHP, vì vậy chúng thường sẽ nhanh hơn đáng kể so với bất kỳ thứ gì bạn có thể tự viết trong PHP.
> Ghi chú: Và bạn cũng phải biết là những Built-in Function của PHP đều được những lập trình viên tài năng nhất viết và chỉnh sửa.
Vẫn sẽ có trường hợp thuật toán sắp xếp tự viết nhanh hơn của riêng bạn, nhưng mình đoán đây là việc khi bạn có một trường hợp rất cụ thể và bạn có thể tự tối ưu hóa cụ thể cho việc đó.
Kết luận
Trong trường hợp tổng quát: Sử dụng hàm sắp xếp được PHP cung cấp sẵn sẽ nhanh hơn tự viết thuật toán quick sort bằng PHP.
Đôi khi trong trường hợp rất cụ thể: Việc sắp xếp bằng thuật toán tự viết, tự tối ưu sẽ nhanh hơn.
> Lưu ý: Khi bạn mất quá nhiều thời gian để sắp xếp thì hãy nhớ ngoài kia có nhiều giải pháp nhanh hơn là PHP.
Và nếu bạn chưa thuần thục và muốn tìm hiểu nhiều hơn việc sắp xếp với PHP thì.
> Bạn sẽ được học và sử dụng thuần thục công việc sắp xếp trong PHP tại khóa HỌC LẬP TRÌNH PHP của NIIT - ICT Hà Nội. Đăng ký ngay hôm nay để trở thành Pro trong ngày mai.
---
HỌC VIỆN ĐÀO TẠO CNTT NIIT - ICT HÀ NỘI
Học Lập trình chất lượng cao (Since 2002). Học làm Lập trình viên. Hành động ngay!
Đc: Tầng 3, 25T2, N05, Nguyễn Thị Thập, Cầu Giấy, Hà Nội
SĐT: 02435574074 - 0914939543
Email: hello@niithanoi.edu.vn
Fanpage: https://facebook.com/NIIT.ICT/
#niit #niithanoi niiticthanoi #hoclaptrinh #khoahoclaptrinh #hoclaptrinhjava #hoclaptrinhphp