[Bài toán] Sắp xếp mảng 1 chiều bằng QuickSort

[Bài toán] 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.
[Thuật toá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;
}

Nếu bạn có câu hỏi hay góp ý xin hãy để lại ý kiến trong phần comment của bài viết.

Cám ơn bạn đã đọc bài viết này. Hãy chia sẻ bài viết và bình luận ý kiến của bạn ở bên dưới.

Share this

Chào mừng bạn đến với SimpleCodeCJava Blog - Mục đích của chúng tôi khi thành lập blog này là muốn chia sẻ những kiến thức và kinh nghiệm lập trình mà chúng tôi đã học được với mong muốn giúp đỡ mọi người, giúp bạn rút ngắn được thời gian tìm hiểu cũng như việc giải quyết những vấn đề trong lập trình C và Java.