Thuật toán quicksort c++

     

Chào ace, bài này chúng ta sẽ khám phá về một trong những thuật toán bố trí được thực hiện nhiều trong lập trình sẵn và thực tiễn nhất sẽ là QuickSort, tiếp sau đây thietkewebshop.vn sẽ reviews và share chi tiết(khái niệm, ứng dụng của nó, code ví dụ, điểm mạnh, điểm yếu…) về QuickSort thông qua các phần sau.

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


1. Giới thiệu

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

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

Quá trình đặc biệt trong quickSort là partition(). Mục tiêu của phân vùng là, cho một mảng và 1 phần tử x của mảng làm cho trụ, đặt x vào đúng vị trí của chính nó trong mảng đã sắp xếp và đặt tất cả các phần tử nhỏ tuổi hơn (nhỏ rộng x) trước x với đặt toàn bộ các bộ phận lớn hơn (lớn rộng x) sau x. Tất cả điều này bắt buộc được triển khai trong thời hạn tuyến tính.

Mã giả hàm QuickSort đệ quy:


/ * phải chăng -> Chỉ số bắt đầu, cao -> Chỉ số xong * /quickSort(arr<>, low, high){ if (low

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

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

/ * phải chăng -> Chỉ số bắt đầu, cao -> Chỉ số ngừng * /quickSort(arr<>, low, high){ if (low Mã giả mang lại partition()

/ * Hàm này nhận bộ phận cuối cùng làm cho trục, vị tríphần tử xoay sinh hoạt vị trí đúng đắn của nó vào mảng được bố trí và đặt tất cả bé dại hơn (nhỏ hơn pivot) ở phía trái của trục và toàn bộ các phần tử lớn rộng ở mặt phảitrong tổng thể trục * /partition (arr<>, low, high){ // pivot (Element to 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 chế tạo ra chỉ mục của phần tử nhỏ tuổi hơn, i = -1Di chuyển các phần tử từ j = low cho high-1j = 0: vày arr pivot, không làm gì cả// Không đổi khác trong i và arr <>j = 2: vì arr pivot, không làm gì cả// Không biến hóa trong i với arr <>j = 4: vì arr

2. Code ví dụ như trên các 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) khổng lồ left of pivot & all greater elements 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 khổng lồ 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 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, and 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 to 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, và places all smaller (smaller than pivot) lớn left of pivot and all greater elements lớn 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, & places all smaller (smaller than pivot) # to left of pivot & all greater elements khổng lồ 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 to lớn be sorted, # low --> Starting index, # high --> Ending index # Function to vày 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, & 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 to 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 triển khai 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 dành cho hai cuộc call đệ quy, thuật ngữ cuối cùng dành cho các bước phân vùng. K là số phần tử nhỏ tuổi hơn pivot.

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

Trường vừa lòng xấu nhất: Trường vừa lòng xấu nhất xẩy ra khi quy trình phân vùng luôn luôn chọn bộ phận lớn tuyệt nhất hoặc bé dại nhất làm pivot. Nếu bọn họ xem xét chiến lược phân vùng sinh hoạt trên, nơi bộ phận cuối cùng luôn luôn được chọn làm trục, trường hòa hợp xấu độc nhất vô nhị sẽ xẩy ra khi mảng vẫn được thu xếp theo đồ vật tự tăng hoặc giảm. Sau đó là tái diễn cho 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ự lặp lại nghỉ ngơi trên là: θ(n2).


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

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

Trường hòa hợp trung bình:

Để triển khai phân tích trường thích hợp trung bình, bọn họ cần xem xét tất cả các hoán vị có thể có của mảng và giám sát thời gian thực hiện cho hầu hết hoán vị, điều này còn có vẻ không dễ dàng.

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

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

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

Xem thêm: Mua Bán Nhà Bán Dưới 1 Tỷ Quận Bình Thạnh, Giá: 1, Bán Nhà Quận Bình Thạnh

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

Việc tiến hành mặc định không đúng định. Mặc dù nhiên, ngẫu nhiên thuật toán thu xếp nào cũng có thể ổn định bằng phương pháp coi các chỉ mục là tham số so sánh.

QuickSort tất cả tại khu vực không?


Theo có mang rộng của thuật toán trên chỗ, nó đủ điều kiện là thuật toán bố trí tại chỗ bởi vì nó chỉ thực hiện thêm không khí để lưu lại trữ những lệnh gọi hàm đệ quy chứ không hẳn để thao tác đầu vào.

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

Trong thuật toán QuickSort đối chọi giản, chúng tôi chọn 1 phần tử có tác dụng pivot, phân vùng mảng xung quanh pivot cùng lặp lại cho các mảng con ở bên trái và bên cần của pivot.

Hãy chu đáo một mảng gồm nhiều phần tử dư thừa. Ví dụ: 1, 4, 2, 4, 2, 4, 1, 2, 4, 1, 2, 2, 2, 2, 4, 1, 4, 4, 4. Trường hợp 4 được chọn làm trụ trong QuickSort đối kháng giản, họ chỉ sửa một 4 và cách xử lý đệ quy các lần lộ diện còn lại. Trong 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 bộ phận bằng pivot.

c) arr bộ phận lớn rộng pivot.

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

Làm cụ nào để thực hiện QuickSort cho danh sách được Liên kết?

QuickSort trên danh sách links Singly


QuickSort trên danh sách được liên kết kép

Chúng ta hoàn toàn có thể triển khai QuickSort tái diễn theo cách thức không?

Có, vui mừng tham khảo thu xếp nhanh lặp lại.

Tại sao bố trí Nhanh được ưu tiên rộng Merge Sort để thu xếp Mảng

Sắp xếp cấp tốc ở dạng thông thường là sắp xếp tại khu vực (tức là ko yêu cầu thêm dung lượng) trong lúc sắp xếp hợp tốt nhất yêu mong thêm O (N) bộ nhớ, N biểu hiện kích thước mảng hoàn toàn có thể khá đắt. Việc phân chia và sa thải không gian quá được thực hiện để bố trí hợp nhất có tác dụng tăng thời hạn chạy của thuật toán. So sánh độ tinh vi trung bình, cửa hàng chúng tôi thấy rằng cả nhị kiểu sắp tới xếp đều phải có độ phức hợ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 duy nhất bị mất do sử dụng thêm không gian lưu trữ O (N).

Hầu hết các 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 bản ngẫu nhiên có độ phức hợp thời gian dự con kiến ​​là O (nLogn). Trường thích hợp xấu nhất cũng rất có thể xảy ra trong phiên bạn dạng ngẫu nhiên, tuy thế trường hợp xấu tuyệt nhất không xảy ra đối với một mẫu cụ thể (như mảng được sắp xếp) và bố trí nhanh ngẫu nhiên chuyển động tốt vào thực tế.

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

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

Tại sao MergeSort được ngưỡng mộ 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 hợp này khác nhau chủ yếu do sự khác biệt trong phân bổ bộ nhớ lưu trữ của mảng và list liên kết. Không y như mảng, các nút danh sách liên kết có thể không gần cạnh trong cỗ nhớ. Không y như mảng, trong list liên kết, bạn có thể chèn những mục vào giữa trong O (1) không khí thừa và O (1) thời gian. Vị đó vận động hợp nhất của sắp xếp hợp nhất có thể được tiến hành mà không tồn tại thêm dung tích cho list được liên kết.

Xem thêm: Top 9 Địa Chỉ Mua Máy Phun Sương Mini Tại Hà Nội, Tphcm Chính Hãng


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

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

Tài liệu trường đoản cú thietkewebshop.vn:

Nếu chúng ta thấy hay với hữu ích, bạn cũng có thể tham gia các kênh sau của thietkewebshop.vn để nhận được không ít hơn nữa: