Sắp xếp nhanh là gì?
Thuật toán Sắp xếp nhanh theo cách tiếp cận Chia và Chinh phục. Nó chia các phần tử thành các phần nhỏ hơn dựa trên một số điều kiện và thực hiện các thao tác sắp xếp trên các phần nhỏ hơn được chia đó.
Thuật toán Sắp xếp nhanh là một trong những thuật toán được sử dụng nhiều nhất và phổ biến trong bất kỳ ngôn ngữ lập trình nào. Tuy nhiên, nếu bạn là một nhà phát triển JavaScript, thì bạn có thể đã nghe nói đến sort () đã có sẵn trong JavaScript. Sau đó, bạn có thể đã nghĩ nhu cầu của thuật toán Sắp xếp nhanh này là gì. Để hiểu điều này, trước tiên chúng ta cần sắp xếp là gì và sắp xếp mặc định trong JavaScript là gì.
Sắp xếp là gì?
Sắp xếp không có gì khác ngoài việc sắp xếp các phần tử theo thứ tự chúng ta muốn. Bạn có thể đã gặp điều này trong những ngày đi học hoặc đại học của bạn. Giống như sắp xếp các số từ nhỏ hơn đến lớn hơn (tăng dần) hoặc từ lớn hơn đến nhỏ hơn (giảm dần) là những gì chúng ta đã thấy cho đến bây giờ và được gọi là sắp xếp.
Sắp xếp mặc định trong JavaScript
Như đã đề cập trước đó, JavaScript có sort () . Chúng ta hãy lấy một ví dụ với một vài mảng phần tử như [5,3,7,6,2,9] và muốn sắp xếp các phần tử mảng này theo thứ tự tăng dần. Chỉ cần gọi sort () trên mảng các mục và nó sắp xếp các phần tử của mảng theo thứ tự tăng dần.
Mã:
var items = [5,3,7,6,2,9];console.log(items.sort());//prints [2, 3, 5, 6, 7, 9]
Lý do để chọn Sắp xếp nhanh thay vì sắp xếp mặc định () trong JavaScript là gì
Mặc dù sort () cho kết quả mà chúng ta muốn, vấn đề nằm ở cách nó sắp xếp các phần tử mảng. Sắp xếp mặc định () trong JavaScript sử dụng sắp xếp chèn theo V8 Engine của Chrome và sắp xếp hợp nhất của Mozilla Firefox và Safari .
Tuy nhiên, điều này không phù hợp nếu bạn cần sắp xếp số lượng lớn các phần tử. Vì vậy, giải pháp là sử dụng Quick sort cho tập dữ liệu lớn.
Vì vậy, để hiểu hoàn toàn, bạn cần biết Quick sort hoạt động như thế nào và hãy cùng chúng tôi xem chi tiết điều đó ngay bây giờ.
Sắp xếp nhanh là gì?
Sắp xếp nhanh theo thuật toán Chia và Chinh phục . Nó đang chia các phần tử thành các phần nhỏ hơn dựa trên một số điều kiện và thực hiện các thao tác sắp xếp trên các phần nhỏ hơn được chia đó. Do đó, nó hoạt động tốt cho các bộ dữ liệu lớn. Vì vậy, đây là các bước cách sắp xếp nhanh hoạt động bằng những từ đơn giản.
- Đầu tiên hãy chọn một phần tử được gọi là phần tử xoay .
- Tiếp theo, so sánh tất cả các phần tử mảng với phần tử pivot đã chọn và sắp xếp chúng theo cách sao cho các phần tử nhỏ hơn phần tử pivot ở bên trái và lớn hơn pivot ở bên phải.
- Cuối cùng, thực hiện các thao tác tương tự trên các phần tử bên trái và bên phải cho phần tử trục.
Vì vậy, đó là phác thảo cơ bản của Sắp xếp nhanh. Dưới đây là các bước cần được làm theo từng bước một để thực hiện Sắp xếp nhanh.
QuickSort hoạt động như thế nào
- Đầu tiên hãy tìm phần tử "pivot" trong mảng.
- Bắt đầu con trỏ bên trái tại phần tử đầu tiên của mảng.
- Bắt đầu con trỏ bên phải ở phần tử cuối cùng của mảng.
- So sánh phần tử trỏ với con trỏ trái và nếu nó nhỏ hơn phần tử xoay, thì hãy di chuyển con trỏ trái sang phải (thêm 1 vào chỉ mục bên trái). Tiếp tục điều này cho đến khi phần tử bên trái lớn hơn hoặc bằng phần tử xoay.
- So sánh phần tử trỏ với con trỏ phải và nếu nó lớn hơn phần tử pivot, thì hãy di chuyển con trỏ phải sang trái (trừ 1 vào chỉ số bên phải). Tiếp tục điều này cho đến khi phần tử bên phải nhỏ hơn hoặc bằng phần tử xoay.
- Kiểm tra xem con trỏ bên trái có nhỏ hơn hoặc bằng con trỏ bên phải hay không, sau đó xem các phần tử ở vị trí của các con trỏ này.
- Tăng con trỏ bên trái và giảm con trỏ bên phải.
- Nếu chỉ số của con trỏ bên trái vẫn nhỏ hơn chỉ số của con trỏ bên phải, thì hãy lặp lại quá trình; khác trả về chỉ mục của con trỏ bên trái.
Vì vậy, chúng ta hãy xem các bước này với một ví dụ. Chúng ta hãy xem xét mảng các phần tử mà chúng ta cần sắp xếp là [5,3,7,6,2,9].
Xác định phần tử Pivot
Nhưng trước khi tiếp tục với Sắp xếp nhanh, việc chọn phần tử xoay đóng một vai trò quan trọng. Nếu bạn chọn phần tử đầu tiên làm phần tử xoay vòng, thì phần tử đó sẽ cho hiệu suất kém nhất trong mảng đã sắp xếp. Vì vậy, bạn nên chọn phần tử ở giữa (độ dài của mảng chia cho 2) làm phần tử pivot và chúng ta cũng làm như vậy.
Dưới đây là các bước để thực hiện Sắp xếp nhanh đang được hiển thị với ví dụ [5,3,7,6,2,9].
BƯỚC 1: Xác định trục là phần tử giữa. Vì vậy, 7 là phần tử xoay.
BƯỚC 2: Bắt đầu con trỏ trái và phải lần lượt là phần tử đầu tiên và cuối cùng của mảng. Vì vậy, con trỏ trái đang trỏ đến 5 tại chỉ số 0 và con trỏ phải chỉ đến 9 tại chỉ mục 5.
BƯỚC 3: So sánh phần tử ở con trỏ bên trái với phần tử xoay. Vì, 5 <6 dịch chuyển con trỏ trái sang phải thành chỉ mục 1.
BƯỚC 4: Bây giờ, vẫn là 3 <6, vì vậy hãy dịch chuyển con trỏ bên trái sang một chỉ mục khác ở bên phải. Vì vậy, bây giờ 7> 6 ngừng tăng con trỏ trái và bây giờ con trỏ trái đang ở chỉ số 2.
BƯỚC 5: Bây giờ, so sánh giá trị tại con trỏ bên phải với phần tử pivot. Vì 9> 6 di chuyển con trỏ phải sang trái. Bây giờ khi 2 <6 dừng di chuyển con trỏ bên phải.
BƯỚC 6: Hoán đổi cả hai giá trị hiện tại ở con trỏ trái và phải với nhau.
BƯỚC 7: Di chuyển cả hai con trỏ thêm một bước nữa.
BƯỚC 8: Vì 6 = 6, di chuyển con trỏ đến một bước nữa và dừng lại khi con trỏ bên trái vượt qua con trỏ bên phải và trả về chỉ số của con trỏ bên trái.
Vì vậy, ở đây dựa trên cách tiếp cận trên, chúng ta cần viết mã hoán đổi các phần tử và phân vùng mảng như đã đề cập ở các bước trên.
Mã hoán đổi hai số trong JavaScript:
function swap(items, leftIndex, rightIndex){var temp = items[leftIndex];items[leftIndex] = items[rightIndex];items[rightIndex] = temp;}
Mã để thực hiện phân vùng như đã đề cập trong các bước trên:
function partition(items, left, right) {var pivot = items[Math.floor((right + left) / 2)], //middle elementi = left, //left pointerj = right; //right pointerwhile (i <= j) {while (items[i] < pivot) {i++;}while (items[j]> pivot) {j--;}if (i <= j) {swap(items, i, j); //swap two elementsi++;j--;}}return i;}
Thực hiện phép toán đệ quy
Khi bạn thực hiện các bước trên, chỉ mục của con trỏ bên trái sẽ được trả về và chúng ta cần sử dụng chỉ mục đó để chia mảng và thực hiện Sắp xếp nhanh trên phần đó. Do đó, nó được gọi là thuật toán Chia và Chinh phục.
Vì vậy, sắp xếp nhanh được thực hiện cho đến khi tất cả các phần tử trên mảng bên trái và mảng bên phải được sắp xếp.
Lưu ý: Sắp xếp nhanh được thực hiện trên cùng một mảng và không có mảng mới nào được tạo trong quá trình này.
Vì vậy, chúng ta cần gọi phân vùng này () đã giải thích ở trên và dựa vào đó chúng ta chia mảng thành các phần. Vì vậy, đây là mã nơi bạn sử dụng nó,
function quickSort(items, left, right) {var index;if (items.length> 1) {index = partition(items, left, right); //index returned from partitionif (left < index - 1) { //more elements on the left side of the pivotquickSort(items, left, index - 1);}if (index < right) { //more elements on the right side of the pivotquickSort(items, index, right);}}return items;}// first call to quick sortvar result = quickSort(items, 0, items.length - 1);
Hoàn thành mã sắp xếp nhanh:
var items = [5,3,7,6,2,9];function swap(items, leftIndex, rightIndex){var temp = items[leftIndex];items[leftIndex] = items[rightIndex];items[rightIndex] = temp;}function partition(items, left, right) {var pivot = items[Math.floor((right + left) / 2)], //middle elementi = left, //left pointerj = right; //right pointerwhile (i <= j) {while (items[i] < pivot) {i++;}while (items[j]> pivot) {j--;}if (i <= j) {swap(items, i, j); //sawpping two elementsi++;j--;}}return i;}function quickSort(items, left, right) {var index;if (items.length> 1) {index = partition(items, left, right); //index returned from partitionif (left < index - 1) { //more elements on the left side of the pivotquickSort(items, left, index - 1);}if (index < right) { //more elements on the right side of the pivotquickSort(items, index, right);}}return items;}// first call to quick sortvar sortedArray = quickSort(items, 0, items.length - 1);console.log(sortedArray); //prints [2,3,5,6,7,9]
LƯU Ý: Sắp xếp nhanh chạy với Độ phức tạp thời gian là O (nlogn).