Các kỹ thuật sắp xếp trong ngôn ngữ C

Vấn đề

Các kỹ thuật sắp xếp khác nhau trong C là gì? Giải thích một kỹ thuật với ví dụ.

Giải pháp

C cung cấp năm kỹ thuật sắp xếp:

• Sắp xếp nổi bọt (Bubble sort) hay Sắp xếp trao đổi (Exchange Sort).
• Sắp xếp chọn (Selection sort).
• Sắp xếp chèn (Insertion sort) hay Sắp xếp tuyến tính (Linear sort).
• Sắp xếp nhanh (Quick sort) hay Sắp xếp trao đổi phân hoạch (Partition exchange sort).
• Sắp xếp trộn (Merge Sort) hay Sắp xếp bên ngoài (External sort).

Sắp xếp nổi bọt (Bubble sort)

Đây là kỹ thuật sắp xếp đơn giản nhất, còn gọi là sắp xếp trao đổi.

Thủ tục

• So sánh phần tử đầu tiên với các phần tử còn lại, trao đổi nếu không đúng thứ tự.

• Lặp lại cho các phần tử khác cho đến khi toàn bộ danh sách được sắp xếp.

30 50 40 10 20

Xét dãy số trên:

Lượt 1

So sánh phần tử đầu với các phần tử còn lại:

a[0] > a[1] → 30 > 50 (Sai) → không trao đổi

a[0] > a[2] → 30 > 40 (Sai) → không trao đổi

a[0] > a[3] → 30 > 10 (Đúng) → trao đổi

a[0] > a[4] → 10 > 20 (Sai) → không trao đổi

10 50 40 30 20

Lượt 2

So sánh phần tử thứ hai với các phần tử còn lại:

a[1] > a[2] → 50 > 40 (Đúng) → trao đổi

a[1] > a[3] → 40 > 30 (Đúng) → trao đổi

a[1] > a[4] → 30 > 20 (Đúng) → trao đổi

10 20 50 40 30

Lượt 3

So sánh phần tử thứ ba với các phần tử còn lại:

a[2] > a[3] → 50 > 40 (Đúng) → trao đổi

a[2] > a[4] → 40 > 30 (Đúng) → trao đổi

10 20 30 50 40

Lượt 4

So sánh phần tử thứ tư với phần tử còn lại:

a[3] > a[4] → 50 > 40 (Đúng) → trao đổi

10 20 30 40 50

Thuật toán

for (i=0; i<n-1; i++){     for (j=i+1; j<n; j++){         if (a[i] > a[j]){             t=a[i];             a[i] = a[j];             a[j] = t;         }     } }

Ví dụ

Chương trình C sắp xếp nổi bọt:

#include<stdio.h> int main(){     int a[50], i,j,n,t;     printf("enter the No: of elements in the list:\n");     scanf("%d", &n);     printf("enter the elements:\n");     for(i=0; i<n; i++){         scanf ("%d", &a[i]);     }     printf("Before bubble sorting the elements are:\n");     for(i=0; i<n; i++)         printf("%d \t\n", a[i]);     for (i=0; i<n-1; i++){         for (j=i+1; j<n; j++){             if (a[i] > a[j]){                 t = a[i];                 a[i] = a[j];                 a[j] = t;             }         }     }     printf ("after bubble sorting the elements are:\n");     for (i=0; i<n; i++)         printf("%d\t", a[i]);     return 0; }

Kết quả

enter the No: of elements in the list: 5 enter the elements: 12 11 45 26 67 Before bubble sorting the elements are: 12 11 45 26 67 after bubble sorting the elements are: 11 12 26 45 67