Sắp xếp mảng 1 chiều A bằng thuật toán QuickSort cài đặt C/C++

Cho mảng một chiều a. Hãy cài đặt QuickSort để sắp xếp mảng trên theo thứ tự tăng dần.

QuickSort là một thuật toán sắp xếp được sử dùng rộng rãi nhất và vì lý do: trong hầu hết mọi trường hợp, nó là phương pháp nhanh nhất, thời gian chạy thuật toán là O(N*logN). Cơ bản thì thuật toán QuickSort hoạt động bằng cách phân hoạch một dãy thành dãy con, và gọi thuật toán QuickSort để sắp xếp từng dãy con đó. Thuật toán gồm 3 bước cơ bản như sau.

1. Chọn khóa. Khóa được chọn thường là phần tử đầu của mảng, giữa mảng hoặc cuối mảng.
2. Phân hoạch dãy con thành nhóm bên trái (nhỏ hơn khóa) và nhóm bên phải ( lớn hơn khóa).
3. Gọi lại thuật toán để sắp xếp nhóm bên trái.
4. Gọi lại thuật toán để sắp xếp nhớm bên phải.

Sau khi phân hoạch, tất cả những phần tử phía bên trái nhỏ hơn những phần tử bên phải. Nêu như chúng ta sắp xếp phần dãy con bên trái và đến phần dãy con bên phải, toàn bộ dãy sẽ được sắp xếp.

Chương trình cài đặt:

#include<iostream>

#include<conio.h>

using namespace std;

int n = 11;

int arr[] = {5,9,4,12,10,444,345,958,2,4,3};

void quicksort(int* arr, int leftIndex, int rightIndex){

 int i = leftIndex;

 int j= rightIndex;

 int pivot = arr[(leftIndex + rightIndex)/2];

 while(i<=j){

  while(arr[i] < pivot) i++;

  while(arr[j]> pivot) j--;

  if(i<=j){

   int temp = arr[i];

   arr[i] = arr[j];

   arr[j] = temp;

   i++;j--;

  }

  if(i<rightIndex) quicksort(arr,i,rightIndex);

  if(j>leftIndex) quicksort(arr,leftIndex,j);

 }

}

int main(){

 quicksort(arr,0,10);

 freopen("QUICKSORT.OUT","w",stdout);

 for(int i=0;i<11;i++){

  cout<<arr[i]<<" ";

 }

 return 0;

}