SIMPLE
STRING
ARRAY
SORTING
POINTER
CALCULATION
NUMBER
OTHER
CÁC CHỦ ĐỀ
BÀI MỚI NHẤT
MỚI CẬP NHẬT

Tìm kiếm nhanh Quicksort trong C++

Trong bài tập này chúng ta sẽ thực hiện chương trình tìm kiếm nhanh Quicksort trong C++. Đây là một bài tập đơn giản giúp các bạn thực hành với các câu lệnh trong C++.

test php

banquyen png
Bài viết này được đăng tại freetuts.net, không được copy dưới mọi hình thức.

Quicksort là một thuật toán phân chia và sắp xếp.

Các bước là:

  1. Chọn một phần tử từ mảng, phần tử này được gọi là phần tử trục.
  2. Chia mảng các phần tử chưa được sắp xếp thành hai mảng có giá trị nhỏ hơn trục xuất hiện trong mảng phụ đầu tiên, trong khi tất cả các phần tử có giá trị lớn hơn trục xuất hiện trong mảng phụ thứ hai (các giá trị bằng nhau có thể đi theo một trong hai cách). Bước này được gọi là hoạt động phân vùng. 3) Lặp lại một cách đệ quy bước 2 (cho đến khi các mảng con được sắp xếp) vào mảng con của các phần tử có giá trị nhỏ hơn và riêng biệt với mảng con của các phần tử có giá trị lớn hơn. Logic tương tự chúng tôi đã thực hiện trong chương trình C++ sau đây.

Ví dụ: Chương trình sắp xếp nhanh trong C++

Trong ví dụ này chúng ta cần tạo một hàm sắp xếp nhanh trước với các bước như trên, sau đó ở hàm Main chúng ta sẽ gọi nó ra để sử dụng.

Bài viết này được đăng tại [free tuts .net]

#include <iostream>
using namespace std;
void quicksort(int number[25],int first,int last){
   int i, j, pivot, temp;
   if(first<last){
      pivot=first;
      i=first;
      j=last;
      while(i<j){
         while(number[i]<=number[pivot]&&i<last)
            i++;
         while(number[j]>number[pivot])
            j--;
         if(i<j){
            temp=number[i];
            number[i]=number[j];
            number[j]=temp;
         }
      }
      temp=number[pivot];
      number[pivot]=number[j];
      number[j]=temp;
      quicksort(number,first,j-1);
      quicksort(number,j+1,last);
   }
}

int main(){
   int i, count, number[25];

  cout<<"Bạn muốn nhập bao nhiêu số: ";
   cin>>count;

   cout<<count<<" bạn muốn nhập là: "<<endl;
   for(i=0;i<count;i++)
      cin>>number[i];

   quicksort(number,0,count-1);

   cout<<"Các số sau khi được sắp xếp là: ";
   for(i=0;i<count;i++)
      cout<<number[i]<<"\t";

   cout<<"\n---------------------------------\n";
   cout<<"Chương trình này được đăng tại freetuts.net";
}

Kết quả sau khi chạy chương trình:

sap xep nhanh PNG

Như vậy là chúng ta đã thực hiện xong chương trình Quicksort trong C++. Chúc các bạn thực hiện thành công!!!

Cùng chuyên mục:

Tổng quan về Iterators trong C++

Tổng quan về Iterators trong C++

[STL] Các hàm thường dùng của lớp Vector trong C++

[STL] Các hàm thường dùng của lớp Vector trong C++

[STL] Các hàm thông dụng của Map trong C++

[STL] Các hàm thông dụng của Map trong C++

[STL] Danh sách các hàm Algorithm thường dùng trong C++

[STL] Danh sách các hàm Algorithm thường dùng trong C++

[STL] Cách tìm kiếm và xóa phần tử của một container trong C++

[STL] Cách tìm kiếm và xóa phần tử của một container trong C++

[STL] Cách sắp xếp một vector trong C++

[STL] Cách sắp xếp một vector trong C++

[STL] So sánh giữa Map và Unordered Map trong C++

[STL] So sánh giữa Map và Unordered Map trong C++

[STL] So sánh giữa Vector và List trong C++

[STL] So sánh giữa Vector và List trong C++

[STL] Sử dụng Algorithm trong C++

[STL] Sử dụng Algorithm trong C++

[STL] Sử dụng Set trong C++

[STL] Sử dụng Set trong C++

Chuyển đổi một số nguyên thành dạng số La Mã trong C

Chuyển đổi một số nguyên thành dạng số La Mã trong C

Kiểm tra một số có phải là số Armstrong hay không trong C

Kiểm tra một số có phải là số Armstrong hay không trong C

Tính giai thừa của một số lớn trong C

Tính giai thừa của một số lớn trong C

Tính tổng các ước số của một số nguyên trong C

Tính tổng các ước số của một số nguyên trong C

Tính tổng các số nguyên trong một mảng sử dụng con trỏ trong C

Tính tổng các số nguyên trong một mảng sử dụng con trỏ trong C

Sử dụng con trỏ để sắp xếp một mảng số nguyên một cách tăng dần trong C

Sử dụng con trỏ để sắp xếp một mảng số nguyên một cách tăng dần trong C

Sử dụng con trỏ để tìm vị trí của một phần tử trong mảng trong C

Sử dụng con trỏ để tìm vị trí của một phần tử trong mảng trong C

Sắp xếp một mảng số nguyên sao trong C

Sắp xếp một mảng số nguyên sao trong C

Sắp xếp một mảng chuỗi theo thứ tự từ điển sử dụng thuật toán radix sort trong C

Sắp xếp một mảng chuỗi theo thứ tự từ điển sử dụng thuật toán radix sort trong C

Sắp xếp một mảng số nguyên sử dụng thuật toán heap sort trong C

Sắp xếp một mảng số nguyên sử dụng thuật toán heap sort trong C

Top