sort(a + 1, a + 1 + n)

admin - 03/05/2020

      Sắp xếp mảng là một thao tác thường được dùng rất nhiều trong các thuật toán như tìm kiếm nhị phân, tìm cặp gần nhất, tìm các giá trị lớn nhất, nhỏ nhất (ví dụ như các bài NHGACASOLUTA, ...). Thuật toán đơn giản nhất để sắp xếp một mảng n phần tử là:

for(i=1; i<n; i++)
   for(j=i+1; j<=n; j++)
      if(a[i]> a[j]) swap(a[i], a[j]);

     Thuật toán sắp xếp trên, cũng như một số thuật toán sắp xếp khác như SelectionSort, InsertionSort, BubbleSort có độ phức tạp là O(n2) - khoảng n(n+1)/2 bước thực hiện. Nếu n= 1.000 thì số bước thực hiện là 500.000, máy tính có thể thực hiện nhanh. Tuy nhiên, nếu n = 100.000 thì số bước thực hiện là 5.000.000.000, máy tính không thể thực hiện được trong khoảng vài giây. 
       Tuy nhiên có những thuật toán khác giúp cho việc sắp xếp có độ phức tạp O(nlog2n) như QuickSort, HeapSort, MergeSort. Nếu n = 100.000 thì số bước sắp xếp khoảng 1.700.000, máy tính hoàn toàn có thể thực hiện dưới 1 giây.

      Trong C++, người ta cung cấp sẵn một hàm sort trong thư viện algorithm để sắp xếp mảng với độ phức tạp O(nlog2n). Sử dụng như sau:

#include<algorithm>
#include<functional> // std::greater
using namespace std;

long long a[100005];
long long n;

int main()
{
    sort(a, a+n); // sắp xếp mảng a tăng dần từ phần tử 0 đến phần tử n-1
    sort(a+1, a+1+n); // sắp xếp mảng a tăng dần từ phần tử 1 đến phần tử n
    sort(a, a+n, greater<int>()); // sắp xếp mảng a giảm dần từ p.tử 0 đến p.tử n-1
}

      Nếu cần sắp một mảng các phần tử có kiểu struct thì cần viết thêm hàm so sánh. Ví dụ sắp xếp mảng PhanSo:

#include<algorithm>
using namespace std;

struct PhanSo
{
   long long ts;
    long long ms;    
};

PhanSo a[100005];
long long n;

bool SoSanh(const PhanSo &x, const PhanSo &y)
{
    return (double)x.ts/x.ms < (double)y.ts/y.ms;
}

int main()
{
    sort(a, a+n, SoSanh); // sắp xếp mảng phân số từ phần tử 0 đến phần tử n-1
    sort(a+1, a+1+n, SoSanh); // sắp xếp mảng phân số từ phần tử 1 đến phần tử n
}

 

CÁC PHẢN HỒI

Back to Top