Tag: Các Thuật Toán Sắp Xếp
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é!
- Inheritance Trong C++
- Polymorphism Trong C++
- Exceptions Trong C++
- Files Trong C++
- Template Trong C++
1. Sắp Xếp Mảng 1 Chiều Tăng Dần Trong C++
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é!
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){
int temp =a;
a=b;
b=temp;
}
// Ham sap xep tang
void sortArrTang(int a[], int n){
for(int i=0;i<n-1;i++)
for(int j=i+1;j<n;j++){
if(a[i]>a[j]){
swap(a[i], a[j]);
}
}
}
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
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){
int aNum = *(int*)a;
int bNum = *(int*)b;
return bNum - aNum;
}
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){
for(short i = 0; i < length; i++) cout << array[i] <<' ';
cout << endl;
}
/*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 aNum = *(int*)a;
int bNum = *(int*)b;
return bNum - aNum;
}
int main(){
int array1[] = {5, 4, 7, 2, 8, 7, 3};
int array2[] = {99, 4, 5, 2, 80, 7, 3};
/*Sử dụng hàm qsort để sắp xếp mảng giảm dần*/
qsort(array1, SIZE_OF_ARRAY(array1), sizeof(int), compareIntDesc);
qsort(array2, SIZE_OF_ARRAY(array2), sizeof(int), compareIntDesc);
/*Xem kết quả sắp xếp mảng*/
show_array(array1, SIZE_OF_ARRAY(array1));
show_array(array2, SIZE_OF_ARRAY(array2));
return 0;
}
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
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)
{
for (k = j + 1; k < count; ++k)
{
if (number[j] > number[k])
{
temp = number[j];
number[j] = number[k];
number[k] = temp;
}
}
}
cout<<"Các số sau khi được sắp xếp tăng dần:\n";
for (i = 0; i < count; ++i)
cout<<"\n"<< number[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)
cin>>number[i];
sort_numbers_ascending(number, count);
}
Kết quả:
4. Hàm Sắp Xếp Trong C++
+ Bài toán sắp xếp
Thuậ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:
- Gán i = 0
- Gán j = 0
- Nếu A[j] > A[j + 1] thì đối chỗ A[j] và A[j + 1]
- Nếu j < n – i – 1:
- Đúng thì j = j + 1 và quay lại bước 3
- Sai thì sang bước 5
- Nếu i < n – 1:
- Đúng thì i = i + 1 và quay lại bước 2
- Sai thì dừng lại
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:
- Gán i = 0
- Gán j = i + 1 và min = A[i]
- Nếu j < n:
- Nếu A[j] < A[min] thì min = j
- j = j + 1
- Quay lại bước 3
- Đổi chỗ A[min] và A[i]
- Nếu i < n – 1:
- Đúng thì i = i + 1 và quay lại bước 2
- Sai thì dừng lại
Đố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:
- Gán i = 1
- Gán x = A[i] và pos = i – 1
- Nếu pos >= 0 và A[pos] > x:
- A[pos + 1] = A[pos]
- pos = pos – 1
- Quay lại bước 3
- A[pos + 1] = x
- Nếu i < n:
- Đúng thì i = i + 1 và quay lại bước 2
- Sai thì dừng lại
+ 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:
- Nếu mảng còn có thể chia đôi được (tức left < right)
- Tìm vị trí chính giữa mảng
- Sắp xếp mảng thứ nhất (từ vị trí left đến mid)
- Sắp xếp mảng thứ 2 (từ vị trí mid + 1 đến right)
- Trộn hai mảng đã sắp xếp với nhau
+ 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:
- Chọn một phần tử làm chốt
- Sắp xếp phần tử bên trái nhỏ hơn chốt
- Sắp xếp phần tử bên phải nhỏ hơn chốt
- Sắp xếp hai mảng con bên trái và bên phải pivot
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++)
for(int j = 0; j < n; j++)
if(a[i][j]%2==0)
sum += a[i][j];
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ận
bool SoNguyenTo(int soA)
{
if (soA < 2)
{
return false;
}
else
{
for (int i = 2; i <= sqrt((float)soA); i ++)
{
if (soA%i==0)
{
return false;
}
}
}
return true;
}
int DemSoLuongSNT(int a[][100], int m, int n)
{
int dem = 0;
for(int i = 0; i < m; i++)
for(int j = 0; j < n; j++)
if(SoNguyenTo(a[i][j])) dem++;
return dem;
}
void LietKeSNT(int a[][100], int m, int n)
{
int dem = 0;
for(int i = 0; i < m; i++)
for(int j = 0; j < n; j++)
if(SoNguyenTo(a[i][j])) printf("%d\t", a[i][j]);
}
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ận
1
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++)
for(int j=0;j<n;j++)
a[i][j]=a[i+1][j];
m--;
}
void XoaCot(int a[][100], int m, int &n, int c)
{
for(int i=0;i<m;i++)
for(int j=c;j<n-1;j++)
a[i][j]=a[i][j+1];
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))
for(int j=0;j<n;j++)
swap(a[row1][j],a[row2][j]);
}
void DoiChoHaiCot(int a[][100], int m, int n, int column1, int column2)
{
if((column1>=0 && column1<n)&&(column2>=0 && column2<n))
for(int i=0;i<m;i++)
swap(a[i][column1],a[i][column2]);
}
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++)
if(a[i][i] > max)
max = a[i][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++)
if(a[i][i] < min)
min = a[i][i];
return min;
}
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ó thể sử dụng thuật toán tìm nhị phân
- Để thực hiện thao tác nào đó được nhanh hơn
Các phương pháp sắp xếp thông dụng:
- Phương pháp Đổi chỗ trực tiếp (Interchange sort)
- Phương pháp Nổi bọt (Bubble sort)
- Phương pháp Chèn trực tiếp (Insertion sort)
- Phương pháp Chọn trực tiếp (Selection sort)
Interchange Sort
Khái niệm nghịch thế:
- Xét một mảng các số a[0], a[1], … a[n-1]
- Nếu có i<j và a[i] > a[j], thì ta gọi đó là một 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:
- Để sắp xếp một dãy số, ta có thể xét các nghịch thế có trong dãy và làm triệt tiêu dần chúng đi
Ý tưởng:
- Xuất phát từ đầu dãy, tìm tất cả nghịch thế chứa phần tử này, triệt tiêu chúng bằng cách đổi chỗ phần tử này với phần tử tương ứng trong cặp nghịch thế
- Lặp lại xử lý trên với các phần tử tiếp theo trong dãy
void Swap(int &a, int &b){
int temp = a;
a = b;
b = temp;
}
void InterchangeSort(int a[], int n){
for (int i = 0; i < n - 1; i++)
for (int j = i + 1; j < n; j++)
if(a[i] > a[j]) //nếu có nghịch thế thì đổi chỗ
Swap(a[i], a[j]);
}
Đánh giá:
- Số lượng các phép so sánh xảy ra không phụ thuộc vào tình trạng của dãy số ban đầu
- Số lượng phép hoán vị thực hiện tùy thuộc vào kết quả so sánh
Bubble Sort
Ý tưởng:
- Xuất phát từ cuối dãy, đổi chỗ các cặp phần tử kế cận để đưa phần tử nhỏ hơn trong cặp phần tử đó về vị trí đầu dãy hiện hành, sau đó sẽ không xét đến nó ở bước tiếp theo
- Ở lần xử lý thứ i có vị trí đầu dãy là i
- Lặp lại xử lý trên cho đến khi không còn cặp phần tử nào để xét
void BubbleSort(int a[], int n){
for (int i = 0; i < n - 1; i++)
for (int j = n - 1; j > i; j--)
if(a[j] < a[j-1])
Swap(a[j], a[j-1]);
}
Đánh giá:
- Số lượng các phép so sánh xảy ra không phụ thuộc vào tình trạng của dãy số ban đầu
- Số lượng phép hoán vị thực hiện tùy thuộc vào kết quả so sánh
Khuyết điểm:
- Không nhận diện được tình trạng dãy đã có thứ tự hay có thứ tự từng phần
- Các phần tử nhỏ được đưa về vị trí đúng rất nhanh, trong khi các phần tử lớn lại được đưa về vị trí đúng rất chậm\
Insertion Sort
Nhận xét:
- Mọi dãy a[0] , a[1] ,…, a[n-1] luôn có i-1 phần tử đầu tiên a[0] , a[1] ,… , a[i-2] đã có thứ tự (i ≥ 2)
Ý tưởng chính:
- Tìm cách chèn phần tử a[i] vào vị trí thích hợp của đoạn đã được sắp để có dãy mới a[0] , a[1] ,… , a[i-1] trở nên có thứ tự
- Vị trí này chính là pos thỏa : a[pos-1] <= a[i ]< a[pos] (1 <= pos <= i)
void InsertionSort(int a[], int n){
int pos, x;
for(int i = 1; i < n; i++){ //đoạn a[0] đã sắp
x = a[i];
pos = i;
while(pos > 0 && x < a[pos-1]){
a[pos] = a[pos-1]; // dời chỗ
pos--;
}
a[pos] = x;
}
}
Đánh giá:
- Giải thuật thực hiện tất cả N-1 vòng lặp tìm pos, do số lượng phép so sánh và dời chỗ này phụ thuộc vào tình trạng của dãy số ban đầu, nên chỉ có thể ước lược trong từng trường hợp như sau:
Selection Sort
Nhận xét:
- Mảng có thứ tự thì a[i] = min(a[i], a[i+1], …, a[n-1])
Ý 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ế:
- Chọn phần tử nhỏ nhất trong n phần tử ban đầu, đưa phần tử này về vị trí đúng là đầu dãy hiện hành
- Xem dãy hiện hành chỉ còn n-1 phần tử của dãy ban đầu, bắt đầu từ vị trí thứ 2; lặp lại quá trình trên cho dãy hiện hành… đến khi dãy hiện hành chỉ còn 1 phần tử
void SelectionSort(int a[], int n)
{
int min; // chỉ số phần tử nhỏ nhất trong dãy hiện hành
for (int i = 0; i < n - 1; i++){
min = i;
for(int j = i + 1; j < n; j++)
if (a[j] < a[min])
min = j; // ghi nhận vị trí phần tử nhỏ nhất
if (min != i)
Swap(a[min], a[i]);
}
}
Đánh giá:
- Ở lượt thứ i, cần (n-i) lần so sánh để xác định phần tử nhỏ nhất hiện hành
- Số lượng phép so sánh không phụ thuộc vào tình trạng của dãy số ban đầu
Trong mọi trường hợp, số lần so sánh là:
7. Sắp Xếp Quicksort Trong C
Trong 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án
Trong 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()).
- Chọn pivot cho mảng, ở đây mình sẽ chọn pivot là số cuối cùng của mảng.
- Tạo hai biến là left và right để trỏ tới bên trái và bên phải của danh sách.
- Thực hiện so sánh các phần tử với pivot. Nếu phần tử nhỏ hơn pivot thì dịch chuyển qua bên trái và ngược lại.
- Sau khi dịch chuyển thực hiện công việc sắp xếp các phần tử trong mảng con mới, trước khi tiếp tục phân đoạn tiếp theo.
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 partition (int arr[], int low, int high)
{
int pivot = arr[high]; // khai báo phần tử đánh dâu pivot
int left = low; //khai báo biến bên trái
int right = high - 1; //khai báo biến bên phải
while(true){
while(left <= right && arr[left] < pivot) left++; // tìm phần tử >= phần tử pivot trong mảng
while(right >= left && arr[right] > pivot) right--; // tìm phần tử <= phần tử pivot trong mảng
if (left >= right) break; // sau khi duyệt xong thì thoát khỏi vòng lặp
swap(arr[left], arr[right]); // nếu chưa xong thì sử dụng hàm swap() để tráo đổi.
left++; // Vì left hiện tại đã xét, nên cần tăng
right--; // Vì right hiện tại đã xét, nên cần giảm
}
swap(arr[left], arr[high]);
return left; // Trả về chỉ số sẽ dùng để chia đôi mảng
}
Hàm quicksort()
void quickSort(int arr[], int low, int high)
{
if (low < high)
{
/* index là chỉ số nơi phần tử này đã đứng đúng vị trí
và đây là phần tử chia mảng làm 2 mảng con trái & phải */
int index = partition(arr, low, high);
// Gọi đệ quy sắp xếp 2 mảng con trái và phải
quickSort(arr, low, index - 1);
quickSort(arr, index + 1, high);
}
}
Hàm swap()
void swap(int &a, int &b)
{
int t = a;
a = b;
b = t;
}
8. Hàm Sắp Xếp Nổi Bọt Trong C++
Ý tưởng của sắp xếp nổi bọt
Thuậ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ọa
Giả 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++
// Code from https://nguyenvanhieu.vn
#include <stdio.h>
void swap(int &x, int &y)
{
int temp = x;
x = y;
y = temp;
}
// Hàm sắp xếp bubble sort
void bubbleSort(int arr[], int n)
{
int i, j;
bool haveSwap = false;
for (i = 0; i < n-1; i++){
// i phần tử cuối cùng đã được sắp xếp
haveSwap = false;
for (j = 0; j < n-i-1; j++){
if (arr[j] > arr[j+1]){
swap(arr[j], arr[j+1]);
haveSwap = true; // Kiểm tra lần lặp này có swap không
}
}
// Nếu không có swap nào được thực hiện => mảng đã sắp xếp. Không cần lặp thêm
if(haveSwap == false){
break;
}
}
}
/* Hàm xuất mảng */
void printArray(int arr[], int size)
{
int i;
for (i=0; i < size; i++)
printf("%d ", arr[i]);
printf("n");
}
// Driver program to test above functions
int main()
{
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr)/sizeof(arr[0]);
bubbleSort(arr, n);
printf("Sorted array: n");
printArray(arr, n);
return 0;
}
Ở đâ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ả:
Sorted array: 11 12 22 25 34 64 90
Đánh giá thuật toán sắp xếp nổi bọt
Độ phức tạp thuật toán
- Trường hợp tốt: O(n)
- Trung bình: O(n^2)
- Trường hợp xấu: O(n^2)
Không gian bộ nhớ sử dụng: O(1)
9. Sắp Xếp Chèn Trong C++
+ Ý tưởng thuật toán sắp xếp chèn trực tiếp
Giả 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é.
+ Các bước thực hiện thuật toán
Bước 1: i = 1;//giả sử có đoạn a[0] đã được sắp xếp
Bước 2: x = a[i];
Bước 3:
Tìm vị trí pos thích hợp trong đoạn a[0] đến a[i-1] để chèn a[i] vào danh sách.
Dời chỗ các phần tử từ a[pos] đến a[i-1] sang phải 1 vị trí để dành chổ cho a[i].
Bước 4: a[pos] = x;//chèn x, có đoạn a[0],…,a[i] đã được sắp.
Bước 5: i = i+1; nếu i < n -> lặp lại bước 2, ngược lại -> Dừng.
+ Cài đặt thuật toán sắp xếp chèn trực tiếp với C++
void Insertion_Sort(int a[], int n){
int pos, i;
int x;//lưu giá trị a[i] tránh bị ghi đè khi dời chỗ các phần tử
for(i=1; i<n; i++){//đoạn a[0] đã sắp xếp
x = a[i]; pos = i-1;
//tìm vị trí chèn x
while((pos>=0)&&(a[pos]>x)){
//kết hợp dời chỗ các phần tử sẽ đứng sau x trong danh sách mới
a[pos+1] = a[pos];
pos--;
}
a[pos+1] = x;//chèn x vào danh sách
}
}
void main()
{
int a[5] = {8, 4, 1, 6, 5};
Insertion_Sort(a, 5);
cout<<"Mang sau khi sap xep:"<<endl;
for(int i=0;i<5;i++){
cout<<a[i]<<" ";
}
system("pause");
}
Kết quả
Mang sau khi sap xep: 1 4 5 6 8
Đánh giá thuật toán
Trường hợp
Số lần so sánh
Tốt nhất
n-1
Xấu nhất
n(n-1)/2
Độ phức tạp thuật toán trong trường hợp xấu nhất là O(n2).
Đánh Giá Chất Lượng Bài Viết
