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

 
HTC Titan Review: 1st Windows 7 Phone By HTC

HTC Titan Review: 1st Windows 7 Phone By HTC

The HTC titan it is one big smartphone. This huge phone is grabbing eyeballs as this newest Windows device proudly flaunts the 4.7″ screen making the display large and clear.

Motorola Atrix 4G Review

Motorola Atrix 4G Review

Motorola made a brave leap in the smartphone market with Motorola Atrix 4G. It is the most advanced Android phone created by Motorola.

Cách nhỏ Update Drupal core from 8.7 to 8.8 bằng Composer

Cách nhỏ Update Drupal core from 8.7 to 8.8 bằng Composer

Drupal 8.8 is stable! This release includes many improvements for things like the Media Library, workspaces, and migrations

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

 

Diet con trung