Trong bài viết này Blog tuicocach.com sẽ giới thiệu tới các bạn thuật toán sắp xếp đổi chỗ trực tiếp. Đây là một trong 7 thuật toán sắp xếp căn bản thường dùng.
DANH SÁCH BÀI VIẾT Thuật toán sắp xếp nhanh (Quick Sort) Thuật toán sắp xếp trộn (Merge Sort) Thuật toán sắp xếp đổi chỗ trực tiếp (Interchange Sort) Thuật toán sắp xếp nổi bọt (Bubble Sort) Thuật toán sắp xếp chọn(Selection Sort) Thuật toán sắp xếp chèn (Insertion sort)
Ý tưởng của thuật toán Interchange Sort
Thuật toán Interchange sort chia mảng ra làm 2 mảng con, mảng bên trái đã được sắp xếp và bên phải chưa được sắp xếp. Thuật toán Interchange sort sắp xếp một mảng bằng cách đổi chỗ liên tục phần tử ở đầu đoạn chưa được sắp xếp(không phải đầu mảng) với phần tử nhỏ hơn nó cho tới khi duyệt tới cuối mảng, thực hiện lặp cho tới khi mảng hoàn toàn được sắp xếp.
XÊM THÊM Thuật toán sắp xếp chọn(Selection Sort) Thuật toán sắp xếp chèn (Insertion sort) Thuật toán sắp xếp nổi bọt (Bubble Sort)
Ví dụ sử dụng thuật toán BubbleSort sắp xếp dãy {3,4,1,2} theo thứ tự tăng dần ta sẽ thấy các bước thực hiện như sau.
Cài đặt thuật toán Interchange Sort trên C/C++
#include <stdio.h>
//Hàm đổi chỗ 2 số nguên a,b
void Swap(int &a, int &b){
int temp = a;
a = b;
b = temp;
}
//Hàm sắp xế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[i] > a[j]) //Thực hiện đổi chỗ phần tử nhỏ hơn với phần tử thứ i.
Swap(a[i], a[j]);
}
//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");
}
int main()
{
int arr[] = {3,4,1,2};
int n = sizeof(arr)/sizeof(arr[0]);
InterchangeSort(arr, n);
printf("Sorted array: \n");
printArray(arr, n);
return 0;
}
Kết quả chạy chương trình
Đánh giá thuật toán sắp xếp Interchange sort
Độ phức tạp thuật toán: O(n^2)
Cảm ơn đã theo dõi bài viết, nếu có bất kỳ thắc mắc hay góp ý comment bên dưới nhé.
