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 (62 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

 
Sử dụng Bootswatch Themes ở Drupal 7 như thế nào?

Sử dụng Bootswatch Themes ở Drupal 7 như thế nào?

The standard look and feel of Bootstrap is unmistakable and often you can spot a website using it a mile away. The dead giveaways are the buttons and navigation, but it doesn't have to be this way.

Windows 8: Liệu có thể thống lĩnh cả hai thị trường?

Windows 8: Liệu có thể thống lĩnh cả hai thị trường?

Tham vọng của Microsoft là rất lớn khi muốn phổ biến Windows 8 lên mọi thiết bị. Liệu Microsoft có thể thành công trên cả máy để bàn và di động chỉ với một hệ điều hành?

Hướng dẫn từng bước tạo custom form trên Drupal 8

Hướng dẫn từng bước tạo custom form trên Drupal 8

In Drupal 8 form API is similar to Drupal 7 Form API. forms still uses array structure to render the data. but having separate validation and submission form.Drupal 8 has some new (HTML 5) elements available.

Tomdesgin.vn

 

Drupal Services