Thuật Toán Quicksort Trong C++

     

Chào ace, bài bác này họ sẽ tìm hiểu về một trong các thuật toán sắp xếp được thực hiện nhiều trong thiết kế và thực tế nhất đó là QuickSort, dưới đây giangdien.com.vn sẽ trình làng và chia sẻ chi tiết(khái niệm, vận dụng của nó, code ví dụ, điểm mạnh, điểm yếu…) về QuickSort thông qua những phần sau.

Bạn đang xem: Thuật toán quicksort trong c++


1. Giới thiệu

Giống như Merge Sort, QuickSort là 1 trong những thuật toán chia và Chinh phục. Nó chọn 1 phần tử làm trục với phân vùng mảng sẽ cho bao bọc trục vẫn chọn. Có tương đối nhiều phiên bạn dạng khác nhau của QuickSort chọn pivot theo những phương pháp khác nhau.

Luôn chọn thành phần đầu tiên làm trục.Luôn chọn thành phần cuối cùng có tác dụng trụ (được thực thi bên dưới)Chọn một phần tử thốt nhiên làm trục quay.Chọn trung vị có tác dụng trục.

Quá trình đặc trưng trong quickSort là partition(). Kim chỉ nam của phân vùng là, cho 1 mảng và một trong những phần tử x của mảng có tác dụng trụ, đặt x vào đúng vị trí của nó trong mảng đã thu xếp và đặt tất cả các phần tử bé dại hơn (nhỏ rộng x) trước x với đặt toàn bộ các phần tử lớn hơn (lớn rộng x) sau x. Toàn bộ điều này bắt buộc được triển khai trong thời hạn tuyến tính.

Mã mang hàm QuickSort đệ quy:


/ * rẻ -> Chỉ số bắt đầu, cao -> Chỉ số xong xuôi * /quickSort(arr<>, low, high){ if (low

*
Thuật toán phân vùng

Có thể gồm nhiều phương pháp để thực hiện tại phân vùng, sau mã đưa áp dụng cách thức được chỉ dẫn trong sách CLRS. Logic rất đối kháng giản, chúng tôi bắt đầu từ phần tử ngoài cùng bên trái và theo dõi và quan sát chỉ số của các phần tử nhỏ hơn (hoặc bằng) là i. Trong lúc duyệt, nếu công ty chúng tôi tìm thấy một phần tử nhỏ tuổi hơn, shop chúng tôi hoán đổi bộ phận hiện tại với arr . Giả dụ không, họ bỏ qua thành phần hiện tại.

/ * thấp -> Chỉ số bắt đầu, cao -> Chỉ số chấm dứt * /quickSort(arr<>, low, high){ if (low Mã giả mang đến partition()

/ * Hàm này nhận phần tử cuối cùng làm trục, vị tríphần tử xoay ở vị trí đúng đắn của nó trong mảng được sắp xếp và đặt tất cả nhỏ dại hơn (nhỏ hơn pivot) ở phía bên trái của trục và toàn bộ các thành phần lớn rộng ở mặt phảitrong tổng cộng trục * /partition (arr<>, low, high){ // pivot (Element khổng lồ be placed at right position) pivot = arr; i = (low - 1) // Index of smaller element for (j = low; j Hình minh họa partition():

arr <> = 10, 80, 30, 90, 40, 50, 70Chỉ số: 0 1 2 3 4 5 6low = 0, high = 6, pivot = arr = 70Khởi sinh sản chỉ mục của phần tử bé dại hơn, i = -1Di gửi các thành phần từ j = low mang lại high-1j = 0: bởi arr pivot, không làm những gì cả// Không biến hóa trong i cùng arr <>j = 2: vì arr pivot, không làm gì cả// Không thay đổi trong i cùng arr <>j = 4: vị arr

2. Code lấy ví dụ trên những ngôn ngữ

C++


/* C++ implementation of QuickSort */#include using namespace std; // A utility function khổng lồ swap two elements void swap(int* a, int* b) int t = *a; *a = *b; *b = t; /* This function takes last element as pivot, places the pivot element at its correct position in sorted array, và places all smaller (smaller than pivot) to left of pivot and all greater elements to right of pivot */int partition (int arr<>, int low, int high) { int pivot = arr; // pivot int i = (low - 1); // Index of smaller element for (int j = low; j Array to be sorted, low --> Starting index, high --> Ending index */void quickSort(int arr<>, int low, int high) { if (low C

/* C implementation QuickSort */#include // A utility function to lớn swap two elements void swap(int* a, int* b) int t = *a; *a = *b; *b = t; /* This function takes last element as pivot, places the pivot element at its correct position in sorted array, & places all smaller (smaller than pivot) lớn left of pivot and all greater elements to lớn right of pivot */int partition (int arr<>, int low, int high) { int pivot = arr; // pivot int i = (low - 1); // Index of smaller element for (int j = low; j Array lớn be sorted, low --> Starting index, high --> Ending index */void quickSort(int arr<>, int low, int high) { if (low Java

// Java program for implementation of QuickSort class QuickSort { /* This function takes last element as pivot, places the pivot element at its correct position in sorted array, and places all smaller (smaller than pivot) lớn left of pivot & all greater elements khổng lồ right of pivot */ int partition(int arr<>, int low, int high) { int pivot = arr; int i = (low-1); // index of smaller element for (int j=low; j Array lớn be sorted, low --> Starting index, high --> Ending index */ void sort(int arr<>, int low, int high) { if (low Python

# Python program for implementation of Quicksort Sort # This function takes last element as pivot, places # the pivot element at its correct position in sorted # array, và places all smaller (smaller than pivot) # khổng lồ left of pivot & all greater elements to right # of pivot def partition(arr,low,high): i = ( low-1 ) # index of smaller element pivot = arr # pivot for j in range(low , high): # If current element is smaller than the pivot if arr Array khổng lồ be sorted, # low --> Starting index, # high --> Ending index # Function to vị Quick sort def quickSort(arr,low,high): if low C#

// C# program for implementation of QuickSort using System; class GFG { /* This function takes last element as pivot, places the pivot element at its correct position in sorted array, và places all smaller (smaller than pivot) to left of pivot and all greater elements khổng lồ right of pivot */ static int partition(int <>arr, int low, int high) { int pivot = arr; // index of smaller element int i = (low - 1); for (int j = low; j Array lớn be sorted, low --> Starting index, high --> Ending index */ static void quickSort(int <>arr, int low, int high) { if (low Kết quả

Sorted array:1 5 7 8 9 10

3. Độ phức tạp

Thời gian thực hiện bởi QuickSort nói chung rất có thể được viết như sau.

T(n) = T(k) + T(n-k-1) + θ(n)Hai thuật ngữ đầu tiên giành cho hai cuộc gọi đệ quy, thuật ngữ sau cuối dành cho quá trình phân vùng. K là số phần tử bé dại hơn pivot.

Thời gian thực hiện bởi QuickSort phụ thuộc vào vào mảng đầu vào và kế hoạch phân vùng. Sau đó là ba trường hợp.

Trường đúng theo xấu nhất: Trường hợp xấu nhất xảy ra khi quá trình phân vùng luôn luôn chọn phần tử lớn tuyệt nhất hoặc nhỏ nhất có tác dụng pivot. Nếu họ xem xét chiến lược phân vùng ngơi nghỉ trên, nơi phần tử cuối cùng luôn được chọn làm trục, trường hòa hợp xấu độc nhất sẽ xẩy ra khi mảng đang được thu xếp theo vật dụng tự tăng hoặc giảm. Sau đây là tái diễn mang lại trường vừa lòng xấu nhất.

T(n) = T(0) + T(n-1) + θ(n)tương đương với T(n) = T(n-1) + θ(n)Giải pháp của sự việc lặp lại nghỉ ngơi trên là: θ(n2).


Trường hợp giỏi nhất: trường hợp tốt nhất có thể xảy ra khi quy trình phân vùng luôn chọn thành phần ở giữa làm cho trục. Sau đây là tái diễn mang lại trường hợp xuất sắc nhất.

T(n) = 2T(n/2) + θ(n)Giải pháp của việc lặp lại nghỉ ngơi trên là θ (nLogn). Nó hoàn toàn có thể được giải quyết bằng cách sử dụng trường phù hợp 2 của Định lý Master.

Trường đúng theo trung bình:

Để triển khai phân tích trường đúng theo trung bình, bọn họ cần xem xét tất cả các hoán vị hoàn toàn có thể có của mảng và thống kê giám sát thời gian triển khai cho hồ hết hoán vị, điều này còn có vẻ rất khó dàng.

Chúng ta rất có thể có ý tưởng phát minh về trường đúng theo trung bình bằng cách xem xét trường vừa lòng khi phân hoạch để O (n / 9) phần tử trong một tập hợp cùng O (9n / 10) thành phần trong tập phù hợp khác. Sau đó là tái diễn mang đến trường hòa hợp này.

T(n) = T(n/9) + T(9n/10) + θ(n)Giải pháp của sự tái diễn trên cũng là O (nLogn)

Mặc mặc dù độ phức hợp thời gian vào trường phù hợp xấu độc nhất của QuickSort là O (n2), cao hơn nhiều thuật toán bố trí khác như Merge Sort với Heap Sort, QuickSort trên thực tế nhanh hơn, bởi vòng lặp phía bên trong của nó rất có thể được triển khai tác dụng trên số đông các kiến ​​trúc và đa số các -dữ liệu cố giới. QuickSort có thể được thực hiện theo nhiều phương pháp khác nhau bằng phương pháp thay thay đổi sự tuyển lựa của trục, cho nên vì thế trường hòa hợp xấu độc nhất hiếm lúc xảy ra so với một loại dữ liệu nhất định. Tuy nhiên, bố trí hợp độc nhất vô nhị thường được xem như là tốt hơn khi dữ liệu lớn cùng được lưu trữ trong bộ nhớ ngoài.

Xem thêm: Kể Tên Những Anh Hùng Tuổi Nhỏ Chí Lớn Trong Lịch Sử Đất Nước Mà Em Biết

QuickSort bao gồm ổn định không?

Việc tiến hành mặc định sai trái định. Mặc dù nhiên, bất kỳ thuật toán sắp xếp nào cũng có thể ổn định bằng cách coi những chỉ mục là tham số so sánh.

QuickSort bao gồm tại chỗ không?


Theo tư tưởng rộng của thuật toán trên chỗ, nó đủ đk là thuật toán sắp xếp tại chỗ do nó chỉ sử dụng thêm không gian để lưu lại trữ những lệnh call hàm đệ quy chứ chưa phải để làm việc đầu vào.

QuickSort 3 bí quyết là gì?

Trong thuật toán QuickSort đối chọi giản, shop chúng tôi chọn một phần tử làm pivot, phân vùng mảng xung quanh pivot với lặp lại cho các mảng bé ở phía trái và bên buộc phải của pivot.

Hãy để mắt tới một mảng gồm nhiều bộ phận dư thừa. Ví dụ: 1, 4, 2, 4, 2, 4, 1, 2, 4, 1, 2, 2, 2, 2, 4, 1, 4, 4, 4. Ví như 4 được chọn làm trụ vào QuickSort 1-1 giản, chúng ta chỉ sửa một 4 và cách xử lý đệ quy những lần mở ra còn lại. Vào QuickSort 3 cách, một mảng arr được tạo thành 3 phần:

a) arr phần tử bé dại hơn pivot.

b) arr thành phần bằng pivot.

c) arr bộ phận lớn hơn pivot.

Xem vấn đề này để thực hiện.

Làm cụ nào để thực thi QuickSort cho list được Liên kết?

QuickSort trên danh sách link Singly


QuickSort trên danh sách được link kép

Chúng ta có thể triển khai QuickSort tái diễn theo phương pháp không?

Có, vui vẻ tham khảo sắp xếp nhanh lặp lại.

Tại sao sắp xếp Nhanh được ưu tiên hơn Merge Sort để bố trí Mảng

Sắp xếp cấp tốc ở dạng phổ biến là sắp xếp tại nơi (tức là không yêu cầu thêm dung lượng) trong lúc sắp xếp hợp duy nhất yêu cầu thêm O (N) bộ nhớ, N biểu hiện kích thước mảng rất có thể khá đắt. Việc phân bổ và vứt bỏ không gian vượt được áp dụng để thu xếp hợp nhất làm cho tăng thời hạn chạy của thuật toán. So sánh độ phức hợp trung bình, chúng tôi thấy rằng cả nhị kiểu sắp tới xếp đều phải sở hữu độ phức tạp trung bình O (NlogN) nhưng những hằng số khác nhau. Đối với mảng, sắp xếp hợp nhất bị mất do áp dụng thêm không khí lưu trữ O (N).

Hầu hết những triển khai thực tế của bố trí nhanh đều sử dụng phiên bản ngẫu nhiên. Phiên phiên bản ngẫu nhiên gồm độ phức hợp thời gian dự con kiến ​​là O (nLogn). Trường hòa hợp xấu tốt nhất cũng có thể xảy ra trong phiên bạn dạng ngẫu nhiên, tuy thế trường thích hợp xấu nhất không xảy ra so với một mẫu cụ thể (như mảng được chuẩn bị xếp) và bố trí nhanh ngẫu nhiên hoạt động tốt vào thực tế.

Quick Sort cũng là một thuật toán sắp xếp thân thiện với bộ nhớ lưu trữ cache vì nó bao gồm vị trí tham chiếu xuất sắc khi được sử dụng cho những mảng.

Sắp xếp nhanh cũng là đệ quy đuôi, do đó tối ưu hóa cuộc hotline đuôi được thực hiện.

Tại sao MergeSort được thương yêu hơn QuickSort cho những Danh sách được Liên kết?

Trong trường hợp danh sách liên kết, trường vừa lòng này khác nhau chủ yếu vì chưng sự biệt lập trong phân bổ bộ lưu trữ của mảng và danh sách liên kết. Không giống như mảng, các nút list liên kết có thể không tiếp giáp trong bộ nhớ. Không hệt như mảng, trong danh sách liên kết, bạn có thể chèn các mục vào giữa trong O (1) không khí thừa cùng O (1) thời gian. Vày đó hoạt động hợp độc nhất vô nhị của thu xếp hợp nhất hoàn toàn có thể được thực hiện mà không có thêm dung lượng cho danh sách được liên kết.

Xem thêm: Chữ Happy Birthday Viết Như Thế Nào, Happy Birthday To You Bằng Tiếng Việt


Trong mảng, chúng ta cũng có thể thực hiện truy vấn ngẫu nhiên vị các thành phần liên tục trong cỗ nhớ. Mang sử chúng ta có một mảng A số nguyên (4 byte) với đặt địa chỉ cửa hàng của A <0> là x thì để truy vấn A , bạn có thể truy cập thẳng vào bộ nhớ tại (x + i * 4). Không giống hệt như mảng, bọn họ không thể tiến hành truy cập tự nhiên trong list liên kết. Bố trí nhanh yêu thương cầu rất nhiều loại truy tìm cập. Trong danh sách links để truy cập chỉ mục thiết bị i, bọn họ phải dịch rời từng nút từ trên đầu đến nút thiết bị i vì chúng ta không gồm khối bộ nhớ liên tục. Bởi đó, chi tiêu tăng lên để sắp xếp nhanh chóng. Bố trí hợp nhất truy vấn dữ liệu một bí quyết tuần từ và nhu yếu truy cập bỗng nhiên thấp.

Nguồn với Tài liệu giờ anh tham khảo:

Tài liệu từ bỏ giangdien.com.vn:

Nếu chúng ta thấy hay và hữu ích, chúng ta có thể tham gia những kênh sau của giangdien.com.vn để nhận được không ít hơn nữa: