Chương trình C ++ để thực hiện sắp xếp nhanh trên số lượng lớn các phần tử

Kỹ thuật quicksort được thực hiện bằng cách tách danh sách thành hai phần. Ban đầu, một phần tử xoay được chọn bằng thuật toán phân vùng. Phần bên trái của pivot giữ các giá trị nhỏ hơn pivot và phần bên phải giữ giá trị lớn hơn. Sau khi phân vùng, mỗi danh sách riêng biệt được phân vùng bằng cách sử dụng cùng một thủ tục.

Ở đây chúng tôi đang xem xét một mảng lớn (gần 100 phần tử) để sắp xếp. Chúng tôi đang lấy một số con số sau đó xáo trộn chúng theo thứ tự ngẫu nhiên để làm cho chúng không được sắp xếp. Sau đó, sắp xếp bằng kỹ thuật quicksort.

Sự phức tạp của Kỹ thuật Quicksort

Độ phức tạp về thời gian - O (n log n) cho trường hợp tốt nhất và trường hợp trung bình, O (n ² ) cho trường hợp xấu nhất.
Độ phức tạp của không gian - O (log n)

Đầu vào - Danh sách chưa sắp xếp:90 45 22 11 22 50
Đầu ra - Mảng sau khi sắp xếp:11 22 22 45 50 90

Thuật toán

phân vùng (mảng, dưới, trên)

Đầu vào - Mảng tập dữ liệu, ranh giới dưới và ranh giới trên

Đầu ra - Xoay đúng vị trí

 Begin pivot:=array [upper] i:=Lower - 1 cho j trong phạm vi từ thấp hơn đến cao hơn, thực hiện if array [j]   quickSort (mảng, trái, phải) 
 
  Đầu vào  - Một mảng dữ liệu và giới hạn dưới và trên của mảng 
 
  Đầu ra  - Mảng được sắp xếp 
  Begin if low   Mã mẫu 
  #include  #include  #include  #define MAX 100using namespace std; void random_shuffle (int arr []) {// hàm xáo trộn các phần tử mảng vào các vị trí ngẫu nhiên srand (time (NULL )); for (int i =MAX - 1; i> 0; i--) {int j =rand ()% (i + 1); int temp =arr [i]; arr [i] =arr [j]; arr [j] =temp; }} int partion (int arr [], int p, int r) {int pivot =arr [r]; // mục cuối cùng dưới dạng pivot int i =p - 1; for (int j =p; j   Đầu ra 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100