Hàm sắp xếp trong STL C++

I. Giới thiệu về STL STL (Standard Template Library) là một thư viện template (lập trình theo mẫu) cho C++ với những cấu trúc dữ liệu cũng như giải thuật được xây dựng tổng quát mà vẫn tận dụng được hiệu năng và tốc độ của ngôn ngữ lập trình C. Với khái niệm template,

I. Giới thiệu về STL

STL (Standard Template Library) là một thư viện template (lập trình theo mẫu) cho C++ với những cấu trúc dữ liệu cũng như giải thuật được xây dựng tổng quát mà vẫn tận dụng được hiệu năng và tốc độ của ngôn ngữ lập trình C. Với khái niệm template, những người lập trình đã đề ra khái niệm lập trình khái lược (generic programming), C++ được cung cấp kèm với bộ thư viện chuẩn STL.

Để sử dụng STL, bạn cần khai báo từ khóa using namespace std; sau các khai báo thư viện (ví dụ #include).

#include<iostream>#include<vector>usingnamespace std;//khai báo sử dụng STLmain(){....}

Tại bài viết này mình sẽ không đi sâu vào các tính năng của thư viện STL mà chú yếu khai thác các đặc tính cũng như cách sử dụng của hàm sort() trong thư viện STL của C++.

II. Một số cách sử dụng hàm sort()

1. Khai báo thư viện

Để sử dụng hàm sort(), chúng ta cần khai báo thư viện algorithm:

#include<algorithm>

2. Truy cập địa chỉ của phần tử trong mảng và vector

Các hàm thao tác trên đoạn trong thư viện <algorithm> đều sử dụng các tham số là các địa chỉ. Mỗi biến được tạo ra trong khi lập trình đều có địa chỉ cụ thể trong bộ nhớ, và các biến địa chỉ sẽ giúp chúng ta truy cập tới địa chỉ của biến đó. Đối với mảng và vector, ta có cách truy cập nhanh tới địa chỉ của các phần tử như sau:

Đối với mảng:

{Tên_mảng}+{Vị_trí};

Đối với vector:

{Tên_vector}.begin()+{Vị_trí};

3. Sắp xếp cơ bản

Xét mảng gồm n phần tử:

a[0],a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8],a[9]a[0], a[1], a[2], a[3], a[4], a[5], a[6], a[7], a[8], a[9]

Cách dùng cơ bản nhất của hàm sort() là sắp xếp tăng dần các phần tử từ vị trí ii đến vị trí jj (lưu ý ở đây ta xét mảng bắt đầu từ vị trí 00):

sort(a + i, a + j +1);

Ngoài ra đối với một số kiểu dữ liệu khác, như vector, ta có thể sử dụng câu lệnh như sau:

sort(a.begin(), a.end());

Ví dụ tham khảo:

#include<iostream>#include<algorithm>#include<vector>usingnamespace std;intmain(){int a[6]={5,4,3,2,1,0};sort(a, a +6);// thu được 0 1 2 3 4 5//	sort(a + 2, a + 5);  thu được 5 4 1 2 3 0
    vector<int> a ={5,4,3,2,1,0};sort(a.begin(), a.end());// thu được 0 1 2 3 4 5return0;}

4. Sắp xếp theo thứ tự giảm dần

Chúng ta có thể sắp xếp các phần tử theo thứ tự giảm dần bằng cách truyền tham số comp vào con trỏ hàm của hàm sort() như sau:

boolcomp(constint a,constint b){return a > b;}intmain(){int a[6]={0,1,2,3,4,5};sort(a, a +6, comp);// thu được 5 4 3 2 1 0
   vector<int> a ={0,1,2,3,4,5};sort(a.begin(), a.end(), comp);// thu được 5 4 3 2 1 0return0;}

5. Sử dụng 2 phép toán less và greater

Hai từ khóa lessgreater thể hiện cho hai phép toán sắp xếp tăng dần hoặc giảm dần (thực ra chính là thể hiện của các toán tử <>), khi muốn điều chỉnh cách sắp xếp ta chỉ cần thêm hai phép toán này vào tham số thứ ba của hàm sắp xếp theo cú pháp:

sort(l, r,greater<{Kiểu_phần_tử}>());sort(l, r,less<{Kiểu_phần_tử}>());

Trong đó, {Kiểu_phần_tử} là kiểu dữ liệu của các phần tử trong tập hợp cần sắp xếp.

  • Chương trình tham khảo:
#include<bits/stdc++.h>usingnamespace std;boolcmp(int A,int B){return A > B;}intmain(){int a[]={5,2,10,3,1};// Sắp xếp mảng.sort(a, a +5, cmp);// a = {10, 5, 3, 2, 1}.// In ra kết quả sắp xếp.
    cout <<"Kết quả sắp xếp: "<< endl;for(int i =0; i <5;++i)
        cout << a[i]<<' ';return0;}

Biên dịch và chạy chương trình trên sẽ cho ra kết quả:

Kết quả sắp xếp:105321

6. Một vài kiểu sắp xếp khác

  • Sắp xếp theo bảng chữ cái:
intmain(){
	string str[5]={"c","abc","ac","bb","aaaa"};sort(str, str +5);// "aaaa" "abc" "ac" "bb" "c"return0;}
  • Sắp xếp theo bảng chữ cái kết hợp độ dài tăng dần:
boolcmp(string str1,string str2){return str1.length()< str2.length();}intmain(){
	string str[5]={"c","abc","ac","bb","aaaa"};sort(str, str +5, cmp);// "c" "ac" "bb" "abc" "aaaa"return0;}

III. Xung quanh hàm sort()

1. Tham số phụ comp

Đây là một yếu tố ta có thể thay đổi linh hoạt để hướng hàm sort() đến mục đích mong muốn của chúng ta. Ngoài những ví dụ như trên bạn hoàn toàn có thể xây dựng một hàm sort() đặc biệt dành riêng cho bạn.

2. Nhận xét về hàm sort()

Hàm sort() tối ưu hóa hơn các đặc điểm so với những thuật toán sắp xếp thông thường, nó là một sự kết hợp cũng như cải tiến dung hòa giữa các thuật toán sắp xếp. Với tính linh hoạt của nó, hầu như hàm sort() có thể đáp ứng đầy đủ những nhu cầu sắp xếp của chúng ta.

3. Một số hàm sắp xếp khác

Ngoài ra bạn có thể tìm hiểu một số hàm sắp xếp khác, mỗi hàm đều có những điểm đặc biệt riêng của nó:

stable_sortpartial_sortpartial_sort_copynth_elementis_sortedpartitionstable_partition

IV. Tài liệu tham khảo

Nguồn: viblo.asia

Bài viết liên quan

WebP là gì? Hướng dẫn cách để chuyển hình ảnh jpg, png qua webp

WebP là gì? WebP là một định dạng ảnh hiện đại, được phát triển bởi Google

Điểm khác biệt giữa IPv4 và IPv6 là gì?

IPv4 và IPv6 là hai phiên bản của hệ thống địa chỉ Giao thức Internet (IP). IP l

Check nameservers của tên miền xem website trỏ đúng chưa

Tìm hiểu cách check nameservers của tên miền để xác định tên miền đó đang dùn

Mình đang dùng Google Domains để check tên miền hàng ngày

Từ khi thông báo dịch vụ Google Domains bỏ mác Beta, mình mới để ý và bắt đầ