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

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;

}
Bạn thấy bài viết này như thế nào?: 
Average: 9.9 (63 votes)
Ảnh của Tommy Tran

Tommy owner Express Magazine

Drupal Developer having 9+ year experience, implementation and having strong knowledge of technical specifications, workflow development. Ability to perform effectively and efficiently in team and individually. Always enthusiastic and interseted to study new technologies

  • Skype ID: tthanhthuy

Advertisement

 

jobsora

Dich vu khu trung tphcm

Dich vu diet chuot tphcm

Dich vu diet con trung

Quảng Cáo Bài Viết

 
Trải nghiệm Chromebook theo cách riêng của bạn

Trải nghiệm Chromebook theo cách riêng của bạn

Chromebook là một thiết bị di động được thiết kế riêng cho những người sống trên web. Với ưu điểm như thời lượng pin khủng, trọng lượng siêu nhẹ và bảo mật dữ liệu trên mạng nên đặc biệt thích hợp với những người thường xuyên online.

Google

Google thừa nhận nhiều người dùng iOS khó truy cập Gmail

Theo blog AllThingsD, Google đã công khai thừa nhận việc một số người sử dụng iOS gặp khó khăn khi kết nối với Gmail và công ty đang phát triển bản sửa lỗi.

"Cai nghiện" Facebook một cách thật khoa học

"Cai nghiện" Facebook một cách thật khoa học

Facebook là một mạng xã hội tuyệt vời. Facebook giúp bạn giữ kết nối cũng như chia sẻ mọi điều về cuộc sống thường ngày của mình với gia đình và bạn bè. Nếu là một nhà quản lí, doanh nhân

Công ty diệt chuột T&C

 

Diet con trung