Trang chủLập trìnhCTDL & Thuật toánThuật toán sắp xếp đổi chỗ trực tiếp (Interchange Sort)

Thuật toán sắp xếp đổi chỗ trực tiếp (Interchange Sort)

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.

Ý tưởng của thuật toán Interchange Sort

Minhh họa thuật toán sắp xếp đổi chỗ trực tiếp(Nguồn codelearn.io)
Minhh họa thuật toán sắp xếp đổi chỗ trực tiếp(Nguồn codelearn.io)

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.

Ví dụ các bước thực hiện sắp xếp dãy số 4,3,1,2

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

Kết quả chạy chương trình Interchange sort sắp xếp dãy số 3,4,1,2

Đá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é.

3 1 Bỏ phiếu bình chọn
Xếp hạng bài viết
BÀI VIẾT LIÊN QUAN
Đăng ký nhận thông báo
Thông báo email khi
guest
0 Bình luận
Không thể gửi email
Phản hồi nội tuyến

NÊN ĐỌC THÊM

Bạn muốn tìm kiếm gì?


0
Giáo sư! có thể ném gạch bên dưới nhé!x
()
x