Sắp xếp là 1 định nghĩa cơ bản nhưng khá quan trọng đối với mỗi lập trình viên. Việc sắp xếp sẽ giúp chúng ta dễ dàng hơn trong việc giải quyết những vấn đề khác như tìm kiếm một phần tử, tìm phần tử lớn nhất, nhỏ nhất,…Trong bài viết này, hãy cùng Techacademy đi tìm hiểu kĩ hơn về thuật toán sắp xếp trong C++ nhé! Show
Danh Mục Bài Viết 1. Sắp Xếp Mảng 1 Chiều Tăng Dần Trong C++Cách sắp xếp mảng một chiều theo thứ tự tăng dần trong C / C++. Cách sắp xếp dãy số thực char, mảng số nguyên n nhập vào từ bàn phím. Nếu bạn đang tìm cách sắp xếp các kí tự kiểu char, bạn cũng có thể sử dụng các này nhé! Ở đây mình sẽ viết thành hàm cho dễ sử dụng nhé. hàm swap do mình viết ra có tác dụng đổi chỗ hai phần tử cho nhau. // Ham doi vi tri hai phan tu void swap(int &a, int &b){ }
// Ham sap xep tang
void sortArrTang(int a[], int n){ }Giải thích: Nếu cần sắp xếp mảng có n phần tử. Ta chỉ cần thực hiện n-1 lần chọn, bởi vì phần tử cuối cùng đã tự đúng vị trí nên trong vòng lặp for đầu tiên i<n-1. Trong vòng lặp thứ 2: Ta sẽ chạy từ vị trí j = i+1 đến cuối mảng, tức là từ sau i đến hết mảng. Nếu có phần từ nào nhỏ hơn a[i] thì ta đổi chỗ. Như vậy sau vòng lặp đầu tiên ta sẽ tìm được phần từ nhỏ nhất của mảng. Cứ như vậy Sắp Xếp Mảng 1 Chiều Tăng Dần Trong C++2. Sắp Xếp Giảm Dần Trong C++Để sắp xếp phần tử trong mảng C++ theo thứ tự giảm dần dần bằng hàm qsort, chúng ta đơn giản chỉ cần thay đổi hàm so sánh như dưới đây là xong: int compareIntDesc(const void* a, const void* b){ }Sự khác biệt giữa 2 hàm so sánh này là ở giá trị mà nó trả về. Với hàm compareIntAsc() ở sắp xếp tăng dần thì chúng ta trả về return aNum – bNum, và với hàm compareIntDesc() ở sắp xếp giảm dần thì chúng ta trả về giá trị ngược lại là return bNum – aNum. Và chúng ta sử dụng hàm qsort để viết chương trình sắp xếp phần tử trong mảng C++ theo thứ tự giảm dần như sau: include <iostream>include <cstdlib>using namespace std; /Định nghĩa macro SIZE_OF_ARRAY để lấy độ dài (số phần tử) trong mảng chỉ định/ define SIZE_OF_ARRAY(array) (sizeof(array)/sizeof(array[0]))/Tạo hàm in phần tử trong mảng/ void show_array(int array[], int length){ }
/Tạo hàm so sánh giảm dần sử dụng trong hàm qsort/
int compareIntDesc(const void* a, const void* b){ }
int main(){ }
Kết quả của phép sắp xếp mảng giảm dần trong C++ như dưới đây. Bạn hãy thử chạy chương trình và kiểm tra nhé.8 7 7 5 4 3 2 99 80 7 5 4 3 2 Sắp Xếp Giảm Dần Trong C++3. Sắp Xếp Chuỗi Tăng Dần Trong C++Trong bài tập này chúng ta sẽ thực hiện chương trình C++ để sắp xếp các số trong mảng theo thứ tự tăng dần, đây là 1 bài tập căn bản thường gặp trong khi học ngôn ngữ C++. Chương trình sau đây người dùng sẽ nhập vào n số, sau khi người dùng nhập xong các số đó, chương trình này sẽ sắp xếp và hiển thị chúng theo thứ tự tăng dần. Ở đây mình đã tạo ra một hàm do người dùng định nghĩa sort_numbers_asceinating() cho mục đích sắp xếp. Sau khi chúng ta tạo một hàm sắp xếp sort_numbers_asceinating() để thực hiện công việc sắp xếp theo thứ tự tăng dần thì chúng ta gọi nó ở hàm main() để sử dụng và hiển thị kết quả ra màn hình bằng câu lệnh cout, cin include <iostream>using namespace std; void sort_numbers_ascending(int number[], int count) { int temp, i, j, k; for (j = 0; j < count; ++j) { }
cout<<"Các số sau khi được sắp xếp tăng dần:\n";
for (i = 0; i < count; ++i) }
int main()
{
int i, count, number[20];
cout<<"Nhập số lương phần tử trong mảng:";
cin>>count;
cout<<"\nNhập giá trị cho từng phần tử trong mảng:\n";
for (i = 0; i < count; ++i) sort_numbers_ascending(number, count);
}Kết quả: Sắp Xếp Chuỗi Tăng Dần Trong C+++ Bài toán sắp xếpThuật toán sắp xếp là lời giải của bài toán sắp xếp, vậy thì trước tiên, ta hãy tìm hiểu xem bài toán sắp xếp là gì trước đã. Bài toán sắp xếp chắc chắn không còn xa lạ gì với mỗi chúng ta, nó là 1 trong những bài toán được bắt gặp phổ biến nhất trong thực tế. Ví dụ như sắp xếp danh sách lớp học, sắp xếp quyển sách, sắp xếp tiền… Vậy thì bài toán sắp xếp là gì? Bài toán sắp xếp là chúng ta sẽ sắp xếp lại các phần tử của một danh sách theo chiều tăng hoặc giảm dần theo một tiêu chí nào đó của phần tử trong danh sách. Ví dụ như bạn sắp xếp danh sách lớp học theo điểm trung bình từ cao đến thấp, sắp những quyển sách theo kích cỡ từ nhỏ đến lớn, sắp xếp những tờ tiền theo mệnh giá từ thấp đến cao… Mục đích của việc sắp xếp chính là giúp ta có cái nhìn tổng quan hơn về những dữ liệu mà ta có, dễ dàng tìm kiếm những phần tử đứng nhất về một tiêu chí nào đó như mình đã nói trong Thuật toán kiếm tìm trong C++, hầu như đa số bài toán đều quy về bài toán tìm kiếm. Ví dụ: Bạn có một danh sách lớp học chưa được sắp xếp, bạn muốn biết được là mức độ đề thi có khó đối với học sinh hay không, top 3 học sinh có điểm trung bình cao nhất. Vậy thì sau khi bạn thực hiện việc sắp xếp giảm theo điểm trung bình, bạn sẽ dễ dàng kiểm tra được mức độ của đề đối với học sinh là dễ hay khó thông qua việc nhìn vào đầu và cuối danh sách, đầu danh sách điểm không cao lắm và cuối danh sách điểm thấp thì chắc chắn đề này khó đối với học sinh và ngược lại. Trong lập trình, sắp xếp không chỉ đơn giản là để tìm một hoặc nhiều phần tử đứng đầu về một tiêu chí nào đó hay để có cái nhìn tổng quan về dữ liệu, sắp xếp còn làm cơ sở cho các giải thuật nâng cao với hiệu suất cao hơn. Ví dụ như khi thực hiện tìm kiếm, thuật toán tìm kiếm nhị phân có độ phức tạp thời gian là O(log(n)) và ổn định, nhưng thuật toán này chỉ áp dụng được với dãy đã được sắp xếp. Vậy khi này, bạn có thể thực hiện sắp xếp trước sau đó áp dụng thuật toán tìm kiếm nhị phân. Bài toán sắp xếp chỉ đơn giản có vậy, bây giờ mình sẽ giới thiệu đến các bạn một số giải thuật tìm kiếm phổ biến nhất mà lập trình viên nào cũng nên biết. Hãy cùng bắt đầu thôi! Lưu ý trước khi đọc bài: bạn cần có kỹ năng lập trình C++ cơ bản, hiểu về độ phức tạp của thuật toán. Trong bài viết có sử dụng từ thuật toán sắp xếp ổn định, thuật toán sắp xếp ổn định nghĩa là thứ tự của các phần tử có cùng giá trị sẽ không thay đổi so với ban đầu. Ví dụ như 1 5 3 3 4, sau khi sắp xếp cũng là 1 3 3 4 5. + Sắp xếp nổi bọt (Bubble Sort)Sắp xếp nổi bọt hay bubble sort là thuật toán sắp xếp đầu tiên mà mình giới thiệu đến các bạn và cũng là thuật toán đơn giản nhất trong các thuật toán mà mình sẽ giới thiệu, ý tưởng của thuật toán này như sau: Duyệt qua danh sách, làm cho các phần tử lớn nhất hoặc nhỏ nhất dịch chuyển về phía cuối danh sách, tiếp tục lại làm phần tử lớn nhất hoặc nhỏ nhất kế đó dịch chuyển về cuối hay chính là làm cho phần tử nhỏ nhất (hoặc lớn nhất) nổi lên, cứ như vậy cho đến hết danh sách Cụ thể các bước thực hiện của giải thuật này như sau:
Thật đơn giản đúng không nào, chúng ta hãy cùng cài đặt thuật toán này trong C++ nha. + Sắp xếp chọn (Selection Sort)Sắp xếp chọn hay selection sort sẽ là thuật toán thứ hai mà mình giới thiệu đến các bạn, ý tưởng của thuật toán này như sau: duyệt từ đầu đến phần tử kề cuối danh sách, duyệt tìm phần tử nhỏ nhất từ vị trí kế phần tử đang duyệt đến hết, sau đó đổi vị trí của phần tử nhỏ nhất đó với phần tử đang duyệt và cứ tiếp tục như vậy. Cho mảng A có n phần tử chưa được sắp xếp. Cụ thể các bước của giải thuật này áp dụng trên mảng A như sau:
Đối với thuật toán sắp xếp chọn, do sử dụng 2 vòng lặp lồng vào nhau, độ phức tạp thời gian trung bình của thuật toán này là O(n2). Thuật toán sắp xếp chọn mình cài đặt là thuật toán sắp xếp không ổn định, nó còn có một phiên bản khác cải tiến là thuật toán sắp xếp chọn ổn định. + Sắp xếp chèn (Insertion Sort)Sắp xếp chèn hay insertion sort là thuật toán tiếp theo mà mình giới thiệu, ý tưởng của thuật toán này như sau: ta có mảng ban đầu gồm phần tử A[0] xem như đã sắp xếp, ta sẽ duyệt từ phần tử 1 đến n – 1, tìm cách chèn những phần tử đó vào vị trí thích hợp trong mảng ban đầu đã được sắp xếp. Giả sử cho mảng A có n phần tử chưa được sắp xếp. Các bước thực hiện của thuật toán áp dụng trên mảng A như sau:
+ Sắp xếp trộn (Merge Sort)Sắp xếp trộn (merge sort) là một thuật toán dựa trên kỹ thuật chia để trị, ý tưởng của thuật toán này như sau: chia đôi mảng thành hai mảng con, sắp xếp hai mảng con đó và trộn lại theo đúng thứ tự, mảng con được sắp xếp bằng cách tương tự. Giả sử left là vị trí đầu và right là cuối mảng đang xét, cụ thể các bước của thuật toán như sau:
+ Sắp xếp nhanh (Quick Sort)Sắp xếp nhanh (quick sort) hay sắp xếp phân đoạn (Partition) là là thuật toán sắp xếp dựa trên kỹ thuật chia để trị, cụ thể ý tưởng là: chọn một điểm làm chốt (gọi là pivot), sắp xếp mọi phần tử bên trái chốt đều nhỏ hơn chốt và mọi phần tử bên phải đều lớn hơn chốt, sau khi xong ta được 2 dãy con bên trái và bên phải, áp dụng tương tự cách sắp xếp này cho 2 dãy con vừa tìm được cho đến khi dãy con chỉ còn 1 phần tử. Cụ thể áp dụng thuật toán cho mảng như sau:
Phần tử được chọn làm chốt rất quan trọng, nó quyết định thời gian thực thi của thuật toán. Phần tử được chọn làm chốt tối ưu nhất là phần tử trung vị, phần tử này làm cho số phần tử nhỏ hơn trong dãy bằng hoặc sấp xỉ số phần tử lớn hơn trong dãy. Tuy nhiên, việc tìm phần tử này rất tốn kém, phải có thuật toán tìm riêng, từ đó làm giảm hiệu suất của thuật toán tìm kiếm nhanh, do đó, để đơn giản, người ta thường sử dụng phần tử chính giữa làm chốt. 5. Sắp Xếp Mảng 2 Chiều Tăng Dần Trong C++Bắt đầu ở đây, để cho ngắn gọn bài viết. Mình sẽ chỉ đưa ra hàm con giải quyết phần đề bài của bài tập mảng 2 chiều tương ứng. Các bạn sẽ tự thêm nó vào hàm main nhé. BT1. Viết hàm tính tổng các số chẵn trong ma trận int TongCacSoChan(int a[][100], int m, int n) { int sum = 0; for(int i = 0; i < m; i++) return sum;
}
BT2. Viết hàm liệt kê các số nguyên tố trong ma trận, đếm các số nguyên tố có trong ma trậnbool SoNguyenTo(int soA) { }
int DemSoLuongSNT(int a[][100], int m, int n)
{
int dem = 0;
for(int i = 0; i < m; i++) return dem;
}
void LietKeSNT(int a[][100], int m, int n)
{
int dem = 0;
for(int i = 0; i < m; i++) }
BT3. Viết hàm xóa một dòng của ma trận. Viết hàm xóa một cột của ma trận1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 void XoaDong(int a[][100], int &m, int n, int r) { for(int i=r;i<m-1;i++) m--;
}
void XoaCot(int a[][100], int m, int &n, int c)
{
for(int i=0;i<m;i++) n--;
}
BT4. Viết hàm đổi chỗ 2 hàng của 1 ma trận. Viết hàm đổi chỗ 2 cột của ma trận.0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 void swap(int &a, int &b) { int temp = a; a = b; b = temp; } void DoiCho2Hang(int a[][100], int m, int n, int row1, int row2) { if((row1>=0 && row1<m)&&(row2>=0 && row2<m)) }
void DoiChoHaiCot(int a[][100], int m, int n, int column1, int column2)
{
if((column1>=0 && column1<n)&&(column2>=0 && column2<n)) }
BT5. Viết hàm tìm giá trị lớn nhất/ nhỏ nhất trên đường chéo chính của ma trận.//Tìm max int Max(int a[][100], int n) { int max = a[0][0]; for(int i = 1; i < n; i++) return max;
}
//Tìm min
int Min(int a[][100], int n)
{
int min = a[0][0];
for(int i = 1; i < n; i++) return min;
}
Sắp Xếp Mảng 2 Chiều Tăng Dần Trong C++6. Các Thuật Toán Sắp Xếp Trong C++Sắp xếp là quá trình bố trí lại các phần tử trong một tập hợp theo một trình tự nào đó nhằm mục đích giúp quản lý và tìm kiếm các phần tử dễ dàng và nhanh chóng hơn. Tại sao phải sắp xếp?
Các phương pháp sắp xếp thông dụng:
Interchange SortKhái niệm nghịch thế:
Mảng chưa sắp xếp sẽ có nghịch thế Mảng đã có thứ tự sẽ không chứa nghịch thế a[0] <= a[1] <=… <=[n -1] Nhận xét:
Ý tưởng:
int compareIntDesc(const void* a, const void* b){ }0 Đánh giá:
Bubble SortÝ tưởng:
int compareIntDesc(const void* a, const void* b){ }1 Đánh giá:
Khuyết điểm:
Insertion SortNhận xét:
Ý tưởng chính:
int compareIntDesc(const void* a, const void* b){ }2 Đánh giá:
Selection SortNhận xét:
Ý tưởng: mô phỏng một trong những cách sắp xếp tự nhiên nhất trong thực tế:
int compareIntDesc(const void* a, const void* b){ }3 Đánh giá:
Trong mọi trường hợp, số lần so sánh là: Các Thuật Toán Sắp Xếp Trong C++Các Thuật Toán Sắp Xếp Trong C++7. Sắp Xếp Quicksort Trong CTrong bài này mình sẽ giới thiệu thuật toán Quick Sort (sắp xếp nhanh), đây là thuật toán sắp xếp được xem là nhanh nhất. Chúng ta sẽ cùng nhau tìm hiểu về sắp xếp nhanh là gì? Cũng như cách thức nó hoạt động và triển khai trong C++ như thế nào. Giải thích thuật toánTrong phần này chúng ta có hai giai đoạn. Giai đoạn một là giai đoạn phân đoạn mảng (partition()) và giai đoạn hai là giai đoạn sắp xếp (quickSort()).
Thuật toán Quick Sort trong C++Ở phần trên mình đã nêu ra các bước viết thuật toán. Để chi tiết hơn mình đã có chú thích rõ ràng, cụ thể trong từng dòng code trong thuật toán dưới đây. Các bạn hãy đọc thật kỹ nhé: Hàm partition() int compareIntDesc(const void* a, const void* b){ }4 Hàm quicksort() int compareIntDesc(const void* a, const void* b){ }5 Hàm swap() int compareIntDesc(const void* a, const void* b){ }6 Sắp Xếp Quicksort Trong C8. Hàm Sắp Xếp Nổi Bọt Trong C++Ý tưởng của sắp xếp nổi bọtThuật toán sắp xếp nổi bọt thực hiện sắp xếp dãy số bằng cách lặp lại công việc đổi chỗ 2 số liên tiếp nhau nếu chúng đứng sai thứ tự(số sau bé hơn số trước với trường hợp sắp xếp tăng dần) cho đến khi dãy số được sắp xếp. Ví dụ minh họaGiả sử chúng ta cần sắp xếp dãy số [5 1 4 2 8] này tăng dần. Lần lặp đầu tiên: ( 5 1 4 2 8 ) –> ( 1 5 4 2 8 ), Ở đây, thuật toán sẽ so sánh hai phần tử đầu tiên, và đổi chỗ cho nhau do 5 > 1. ( 1 5 4 2 8 ) –> ( 1 4 5 2 8 ), Đổi chỗ do 5 > 4 ( 1 4 5 2 8 ) –> ( 1 4 2 5 8 ), Đổi chỗ do 5 > 2 ( 1 4 2 5 8 ) –> ( 1 4 2 5 8 ), Ở đây, hai phần tử đang xét đã đúng thứ tự (8 > 5), vậy ta không cần đổi chỗ. Lần lặp thứ 2: ( 1 4 2 5 8 ) –> ( 1 4 2 5 8 ) ( 1 4 2 5 8 ) –> ( 1 2 4 5 8 ), Đổi chỗ do 4 > 2 ( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ) ( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ) Bây giờ, dãy số đã được sắp xếp, Nhưng thuật toán của chúng ta không nhận ra điều đó ngay được. Thuật toán sẽ cần thêm một lần lặp nữa để kết luận dãy đã sắp xếp khi và khi khi nó đi từ đầu tới cuối mà không có bất kỳ lần đổi chỗ nào được thực hiện. Lần lặp thứ 3: ( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ) ( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ) ( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ) ( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ) Code sắp xếp nổi bọt trong C/C++int compareIntDesc(const void* a, const void* b){ }7 Ở đây, trong hàm bubbleSort tôi sử dụng thêm một biến haveSwap để kiểm tra tại lần lặp hiện hành có xảy ra việc đổi chỗ hai số không. Nếu không, ta có thể kết luận mảng đã sắp xếp mà không cần phải thêm một lần lặp nữa. Kiểm tra kết quả: int compareIntDesc(const void* a, const void* b){ }8 Đánh giá thuật toán sắp xếp nổi bọtĐộ phức tạp thuật toán
Không gian bộ nhớ sử dụng: O(1) Hàm Sắp Xếp Nổi Bọt Trong C++9. Sắp Xếp Chèn Trong C+++ Ý tưởng thuật toán sắp xếp chèn trực tiếpGiả sử cần sắp xếp tăng dần một danh sách có n phần tử a0, a1, a2,…,an-1. Giả sử đoạn a[0] trong danh sách đã được sắp xếp. Bắt đầu từ phần tử thứ i=1, tức là a1. Tìm cách chèn phần tử ai vào vị trí thích hợp của đoạn đã được sắp xếp để có dãy mới a0,…,ai trở nên có thứ tự. Vị trí này chính là vị trí giữa hai phần tử ak-1 và ak thỏa ak-1 < ai < ak (0<= k <=i). Lưu ý, khi k=0 thì có nghĩa là ai cần chèn vào trước vị trí đầu tiên trong danh sách. Lặp lại quá trình trên ở mỗi lần lặp với mỗi lần lặp thì tăng i lên 1 đến khi i<n thì dừng quá trình lặp. Một câu hỏi đặt ra là cách chèn phần tử trong danh sách như thế nào? Các bạn hãy đọc tiếp phần 2 và 3 nhé. |