Tóm Tắ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 hoàn toàn 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.
Bạn đang đọc: Thuật Toán Sắp Xếp Trong C++ – Techacademy
// 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;ia[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
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 tiên phong 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 thành phần trong mảng C + + theo thứ tự giảm từ từ bằng hàm qsort, tất cả chúng ta đơn thuần chỉ cần đổi khác 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ự độc lạ 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ì tất cả chúng ta trả về return aNum – bNum, và với hàm compareIntDesc ( ) ở sắp xếp giảm dần thì tất cả chúng ta trả về giá trị ngược lại là return bNum – aNum .
Và tất cả chúng ta sử dụng hàm qsort để viết chương trình sắp xếp thành phần trong mảng C + + theo thứ tự giảm dần như sau :
#include#include 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 tất cả chúng ta sẽ triển khai 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ơ bản thường gặp trong khi học ngôn từ 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 tiêu sắp xếp .
Sau khi tất cả chúng ta tạo một hàm sắp xếp sort_numbers_asceinating ( ) để triển khai việc làm sắp xếp theo thứ tự tăng dần thì tất cả chúng ta gọi nó ở hàm main ( ) để sử dụng và hiển thị tác dụng ra màn hình hiển thị bằng câu lệnh cout, cin
#includeusing 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à giải thuật của bài toán sắp xếp, vậy thì thứ nhất, ta hãy khám phá xem bài toán sắp xếp là gì trước đã .
Bài toán sắp xếp chắc như đinh không còn lạ lẫm gì với mỗi tất cả chúng ta, nó là 1 trong những bài toán được phát hiện thông dụng nhất trong thực tiễn. Ví dụ như sắp xếp list 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à tất cả chúng ta sẽ sắp xếp lại các thành phần của một list theo chiều tăng hoặc giảm dần theo một tiêu chuẩn nào đó của thành phần trong list .
Ví dụ như bạn sắp xếp list 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 tài liệu mà ta có, thuận tiện tìm kiếm những thành phần đứng nhất về một tiêu chuẩn nào đó như mình đã nói trong Thuật toán kiếm tìm trong C + +, hầu hết đa phần bài toán đều quy về bài toán tìm kiếm. Ví dụ :
Bạn có một list lớp học chưa được sắp xếp, bạn muốn biết được là mức độ đề thi có khó so với học viên hay không, top 3 học viên có điểm trung bình cao nhất. Vậy thì sau khi bạn triển khai việc sắp xếp giảm theo điểm trung bình, bạn sẽ thuận tiện kiểm tra được mức độ của đề so với học viên là dễ hay khó trải qua việc nhìn vào đầu và cuối list, đầu list điểm không cao lắm và cuối list điểm thấp thì chắc như đinh đề này khó so với học viên và ngược lại .
Trong lập trình, sắp xếp không chỉ đơn thuần là để tìm một hoặc nhiều thành phần đứng đầu về một tiêu chuẩn nào đó hay để có cái nhìn tổng quan về tài 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 triển khai tìm kiếm, thuật toán tìm kiếm nhị phân có độ phức tạp thời hạn là O ( log ( n ) ) và không thay đổi, nhưng thuật toán này chỉ vận dụng được với dãy đã được sắp xếp. Vậy khi này, bạn hoàn toàn có thể triển khai sắp xếp trước sau đó vận dụng thuật toán tìm kiếm nhị phân .
Bài toán sắp xếp chỉ đơn thuần có vậy, giờ đây mình sẽ trình làng đến các bạn một số ít giải thuật tìm kiếm phổ cập nhất mà lập trình viên nào cũng nên biết. Hãy cùng mở màn thôi !
Lưu ý trước khi đọc bài : bạn cần có kỹ năng và kiến thức 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 không thay đổi, thuật toán sắp xếp ổn định nghĩa là thứ tự của các thành phần có cùng giá trị sẽ không biến hóa so với bắt đầ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 tiên phong mà mình trình làng đến các bạn và cũng là thuật toán đơn thuần nhất trong các thuật toán mà mình sẽ trình làng, sáng tạo độc đáo của thuật toán này như sau :
Duyệt qua list, làm cho các thành phần lớn nhất hoặc nhỏ nhất di dời về phía cuối list, liên tục lại làm thành phần lớn nhất hoặc nhỏ nhất kế đó di dời về cuối hay chính là làm cho thành phần nhỏ nhất ( hoặc lớn nhất ) nổi lên, cứ như vậy cho đến hết list Cụ thể các bước thực thi 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 thuần đúng không nào, tất cả chúng ta hãy cùng setup 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 ra mắt đến các bạn, sáng tạo độc đáo của thuật toán này như sau : duyệt từ đầu đến thành phần kề cuối list, duyệt tìm thành phần nhỏ nhất từ vị trí kế thành phần đang duyệt đến hết, sau đó đổi vị trí của thành phần nhỏ nhất đó với thành phần đang duyệt và cứ liên tục như vậy .
Cho mảng A có n thành phần chưa được sắp xếp. Cụ thể các bước của giải thuật này vận 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 hạn 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 thiết lập là thuật toán sắp xếp không không thay đổi, nó còn có một phiên bản khác nâng cấp cải tiến là thuật toán sắp xếp chọn không thay đổi .
+ 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 trình làng, ý tưởng sáng tạo của thuật toán này như sau : ta có mảng bắt đầu gồm thành phần A [ 0 ] xem như đã sắp xếp, ta sẽ duyệt từ thành phần 1 đến n – 1, tìm cách chèn những thành phần đó vào vị trí thích hợp trong mảng khởi đầu đã được sắp xếp .
Giả sử cho mảng A có n thành phần chưa được sắp xếp. Các bước thực thi của thuật toán vận 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 sáng tạo 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ựa như .
Giả sử left là vị trí đầu và right là cuối mảng đang xét, đơn cử 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ị, đơn cử ý tưởng sáng tạo là : chọn một điểm làm chốt ( gọi là pivot ), sắp xếp mọi thành phần bên trái chốt đều nhỏ hơn chốt và mọi thành phần 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, vận dụng tựa như 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 thành phần .
Cụ thể vận 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 hành động thời hạn 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à thành phần trung vị, thành phần này làm cho số thành phần nhỏ hơn trong dãy bằng hoặc sấp xỉ số thành phần lớn hơn trong dãy. Tuy nhiên, việc tìm thành phần 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 thuần, người ta thường sử dụng thành phần 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 xử lý 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
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=0 && row2=0 && column1=0 && 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à quy trình sắp xếp lại các thành phần trong một tập hợp theo một trình tự nào đó nhằm mục đích mục tiêu giúp quản trị và tìm kiếm các thành phần thuận tiện và nhanh gọn 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
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 trong thực tiễn :
- 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ẽ ra mắt 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 khám phá về sắp xếp nhanh là gì ? Cũng như phương pháp nó hoạt động giải trí và tiến hành trong C + + như thế nào .
Giải thích thuật toán
Trong phần này tất cả chúng ta có hai tiến trình. Giai đoạn một là quá trình phân đoạn mảng ( partition ( ) ) và quá trình hai là quy trình tiế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 cụ thể hơn mình đã có chú thích rõ ràng, đơn cử 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 thi sắp xếp dãy số bằng cách tái diễn việc làm đổi chỗ 2 số liên tục 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
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 hoàn toàn 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 hiệu 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 list có n thành phần a0, a1, a2, …, an-1 .
Giả sử đoạn a [ 0 ] trong list đã được sắp xếp. Bắt đầu từ thành phần thứ i = 1, tức là a1. Tìm cách chèn thành phần 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 thành phần 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í tiên phong trong list .
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
Một câu hỏi đặt ra là cách chèn thành phần trong list 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 list .
Dời chỗ các thành phần 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=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:"<
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
Xem thêm: Bài 2 – Cấu trúc thư mục Laravel – ITCOM
Average rating 0 / 5. Vote count : 0 No votes so far ! Be the first to rate this post.
Source: https://final-blade.com
Category: Kiến thức Internet
