ìm kiếm nhanh Quicksort trong C++ - Bài tập C++ có lời giải

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++.

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.

#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]<<"	";

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

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

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!!!