Tổng hợp một số thuật toán cơ bản về sắp xếp - Phần 1
23/09/2016 7 minutes read
Share:
Hôm nay, mình sẽ chia sẻ với các bạn một số thuật toán cơ bản về sắp xếp. Những thuật toán sau thường dễ để triển khai, tuy nhiên thì độ phức tạp của chúng là N^2. Vì vậy, những thuật toán này chỉ áp dụng cho những bài toán với số lượng phần tử nhỏ. Với những bài toán có số lượng phần tử lớn thì ta sẽ sử dụng những thuật toán nhanh hơn – sẽ được giới thiệu ở phần sau.
Thuật toán sắp xếp chọn trực tiếp – Selection sort
| void SelectionSort(int *a, int N) | |
| { | |
| for(int i = 0; i < N - 1; i++) | |
| { | |
| int idmin = i; | |
| // Tìm ra phần tử có giá trị nhỏ nhất | |
| for(int j = i + 1; j < N; j++) | |
| if(a[j] < a[idmin]) | |
| idmin = j; | |
| // Đổi chỗ phần tử đầu tiên của dãy còn lại với phần tử nhỏ nhất | |
| swap(a[i], a[idmin]); | |
| } | |
| } |
Thuật toán sắp xếp chèn trực tiếp – Insertion sort
| void InsertionSort(int *a, int N) | |
| { | |
| int pos, x; | |
| for(int i = 1; i < N; i++) | |
| { | |
| pos = i - 1; | |
| x = a[i]; | |
| // giả sử dãy a[0], a[1], ... , a[i] đã sắp xếp | |
| // bắt đầu từ a[i], duyệt về đầu mảng và tìm vị trí thích hợp cho a[i] | |
| while(pos >= 0 && a[pos] > x) | |
| { | |
| a[pos + 1] = a[pos]; | |
| pos--; | |
| } | |
| a[pos+1] = x; | |
| } | |
| } |
Thuật toán sắp xếp chèn trực tiếp dựa trên tìm kiếm nhị phân – Binary insertion sort
| void BinaryInsertionSort(int *a, int N) | |
| { | |
| int l, r, m, x; | |
| for(int i = 1; i < N; i++) | |
| { | |
| l = 0; | |
| r = i - 1; | |
| x = a[i]; | |
| // Tương tự như Insertionsort nhưng ở đây | |
| // ta dựa vào tìm kiếm nhị phân để xác định | |
| // vị trí phù hợp cho a[i] được nhanh hơn | |
| while (l <= r) | |
| { | |
| m = (l + r) / 2; | |
| if(a[m] > x) r = m - 1; | |
| else l = m + 1; | |
| } | |
| for(int j = i; j > l; j--) | |
| a[j] = a[j-1]; | |
| a[l] = x; | |
| } | |
| } |
Thuật toán sắp xếp đổi chỗ trực tiếp – Interchange sort
| void InterChangeSort(int *a, int N) | |
| { | |
| for(int i = 0; i < N - 1; i++) | |
| for(int j = i + 1; j < N; j++) | |
| if(a[j] < a[i]) | |
| swap(a[j], a[i]); | |
| } |
Thuật toán sắp xếp nổi bọt – Bubble sort
| 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]); | |
| } |
Thuật toán sắp xếp Shaker sort
| void ShakerSort(int *a, int N) | |
| { | |
| // Thuật toán cải tiến thuật toán sắp xếp nổi bọt | |
| // Bình thường khi ta sắp xếp nổi bọt, giả sử tăng dần | |
| // Thì phần tử nhỏ nhất sẽ được dồn về trái, dần dần cho đến hết. | |
| // Còn với thuật toán này ta sẽ dồn phần tử nhỏ nhất về trái, phần tử lớn lớn sang phải đồng thời | |
| int left, right, k; | |
| left = 0; | |
| right = N-1; | |
| k = N-1; | |
| while(left < right) | |
| { | |
| for(int j = right; j > left; j--) | |
| { | |
| if(a[j] < a[j-1]) | |
| { | |
| swap(a[j], a[j-1]); | |
| k = j; | |
| } | |
| } | |
| left = k; | |
| for (int j = left; j < right; j++) | |
| { | |
| if (a[j] > a[j+1]) | |
| { | |
| swap(a[j], a[j+1]); | |
| k = j; | |
| } | |
| } | |
| right = k; | |
| } | |
| } |
Code by Phạm Văn Lâm
Share:
Tiếp theo