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: 10 (4 votes)
Ảnh của Tommy Tran

Tommy Tran 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
  • Phone/Zalo: (+84) 944 225 212
  • WhatsApp: (+84) 944 225 212
  • Line Messenger: (+84) 944 225 212
  • Email: asaleotestf@gmail.com
  • Telegram Messenger: https:/t.me/tommytran0401

Quảng cáo việc làm

 

Thích hợp các bạn nữ mảng thợ may làm việc tại nước NGA

Đơn hàng Tuyển dụng 100 Thợ may đi Nga(đợt 1 tháng 3.2021, đợt 2 tháng 5.2021). Lương thực lãnh 800 USD, bao ăn ở, vé máy bay và visa, phí xuất cảnh(1800 USD)trả khi đi làm có lương. Bạn có thể liên hệ CÔNG TY qua Phone/Zalo: (+84) 944 225 212. Công ty sẽ tư vấn cho bạn.

Xem chi tiết: >>> https://bit.ly/3o9NOfR

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

 
Rebuildable và reinstallable Drupal trong phần cài đặt drupal 8

Rebuildable và reinstallable Drupal trong phần cài đặt drupal 8

Configuration management is one of the most useful site development features in Drupal 8

Firefox 11 bất ngờ lộ diện

Firefox 11 bất ngờ lộ diện

“Người dùng sẽ luôn biết được những thay đổi mới nhất từ Firefox” - Mozilla đã tuyên bố như vậy và hãng đã cho thấy mình thực hiện tuyên bố này như thế nào, với việc liên tục tung ra những phiên bản mới của Firefox.

Tai nghe ứng dụng công nghệ giao tiếp trường gần

Tai nghe ứng dụng công nghệ giao tiếp trường gần

Công nghệ Near Field Communication (N.F.C – giao tiếp trường gần) cho phép dữ liệu được trao đổi giữa hai thiết bị trong một khoảng cách rất ngắn