Thuật toán sắp xếp (sắp xếp nổi bọt) (Bubble Sort) với ví dụ trong C / C + + / Java

Thuật toán sắp xếp (sắp xếp nổi bọt) (Bubble Sort) với ví dụ trong C / C + + / Java

Bubble Sort là một trong những thuật toán phân loại đơn giản nhất mà chúng ta có thể sử dụng để sắp xếp một mảng hoặc một cấu trúc. Mặc dù nó đơn giản để thực hiện trong một chương trình C, thuật toán sắp xếp này cũng được coi là một thuật toán phân loại không hiệu quả. Thuật toán sắp xếp này hữu ích trong trường hợp tổng số các yếu tố được sắp xếp là quá nhỏ (có thể là trong khoảng 100). Khi kích thước dữ liệu lớn thì hiếm khi được sử dụng trong lập trình thực tế. Hãy phân tích thuật toán sắp xếp này chi tiết bằng cách thực hiện nó như là một chương trình C.

Lưu ý: - Vì thuật toán được thực hiện với sự trợ giúp của 2 vòng FOR, nó có thể được sử dụng như vậy cho bất kỳ ngôn ngữ lập trình như C / C ++ hoặc Java.

Xem xét một mảng gồm 5 phần tử theo thứ tự 5, 4, 3, 2, 1. Chúng ta cần sắp xếp danh sách này theo thứ tự tăng dần bằng cách sử dụng thuật toán sắp xếp. Khái niệm thuật toán sắp xếp là đơn giản, chúng ta có thể giải thích nó bằng 2 bước.

Bước 1: - Phần tử đầu tiên của dãy số được so sánh với phần tử tiếp theo. Để sắp xếp theo thứ tự tăng dần, chúng ta thường bắt đầu quá trình bằng cách kiểm tra nếu phần tử đầu tiên lớn hơn phần tử tiếp theo. Nếu có, ta trao đổi vị trí của phần tử cho phù hợp. Phần tử đầu tiên được di chuyển đến vị trí của phần tử thứ hai và phần tử thứ hai được di chuyển đến vị trí của phần tử đầu tiên. Nếu không, thì chúng ta không trao đổi. Bước tiếp theo, phần tử ở vị trí thứ hai được so sánh với phần tử ở vị trí thứ ba và quá trình trao đổi các phần tử được thực hiện nếu cần. Toàn bộ quá trình so sánh và trao đổi được lặp lại cho đến phần tử cuối cùng. Khi quá trình được hoàn thành, phần tử lớn nhất trong mảng sẽ được đặt ở vị trí cuối cùng của danh sách / mảng.

Chú ý cho Bước 1: - Ở đây lưu ý rằng, chúng ta so sánh hai phần tử theo thứ tự chúng ta so sánh phần tử thứ nhất và thứ 2 - phần tử thứ 2 và thứ 3 - sau đó là thứ 3 và thứ 4 và cuối cùng là thứ 4 và thứ 5. Vì vậy, tổng số so sánh là 4 (cho một mảng / dãy số của 5 chữ số). Nếu có các phần tử 'n' được sắp xếp, thì tổng số so sánh phải được thực hiện là = n-1

Bước 2: - Toàn bộ quá trình trong bước 1 được lặp lại 5 lần để lấy mảng được sắp xếp theo thứ tự 1, 2, 3, 4, 5. Nếu có n phần tử được sắp xếp, toàn bộ quá trình của bước 1 được lặp lại 'n 'lần.

Vì vậy, thuật toán bước 2 này có thể được thực hiện bằng ngôn ngữ C bằng cách sử dụng 2 cho các vòng lặp. Chỉ cần xem bên dưới:

for(i=0; ia[j+1])

{

temp=a[j];

a[j]=a[j+1];

a[j+1]=temp;

}

}

}

Bạn có thể tham khảo 2 hình ảnh dưới đây để hiểu rõ hơn về thuật toán sắp xếp này.  Hình bên dưới biểu diễn cách thức hoạt động của chương trình ở trên:

Bây giờ bạn có thể dễ dàng thấy hiệu quả của thuật toán "Bubble Sort". Nếu có 'n' các phần tử, đó là thứ tự của n * n. Điều này đơn giản bởi vì phải mất gần n so sánh để được thực hiện n lần.

Sửa đổi CODE Bubble Sort:

Mình khuyên bạn nên phân tích hai bước (bước 1 và bước 2) và hai hình ảnh cẩn thận. Bây giờ bạn có thể quan sát thực tế cho thấy số lần so sánh được thực hiện có thể được giảm xuống 1 sau mỗi lần qua vòng lặp FOR đầu tiên. Trong ví dụ trên để sắp xếp theo thứ tự tăng dần, số 5 lớn nhất sẽ đến vị trí cuối cùng sau lần đầu tiên. Đó là vị trí cố định và mình chắc chắn không có số lớn hơn 5 trong dãy số này. Như vậy, chúng ta có thể giảm số lần so sánh được thực hiện trong đợt tiếp theo. Tương tự như vậy sau lần qua vòng FOR thứ hai, số lớn thứ hai (4) được giữ ở vị trí thứ hai (trước 5). Như vậy chúng ta có thể giảm số lần so sánh một lần nữa trong lần tiếp theo. Sửa đổi này cải thiện tốc độ sắp xếp. Phần code được sửa đổi được đưa ra dưới đây:

for(i=0; ia[j+1])

{

temp=a[j];

a[j]=a[j+1];

a[j+1]=temp;

}

}

}

Với mã mới sửa đổi này, chúng tôi có thể cải thiện tốc độ sắp xếp.

Các trường hợp tốt nhất và xấu nhất của Bubble Sort:

Trường hợp tốt nhất là khi thuật toán mang lại hiệu quả tối đa (và hiệu suất nhanh), trong trường hợp xấu nhất là khi nó mang lại hiệu quả thấp nhất (hiệu suất chậm nhất). Trường hợp tốt nhất là khi mảng được sắp xếp theo thứ tự hoàn hảo (theo thứ tự sắp xếp). Ví dụ: - Lấy mảng theo thứ tự 1, 2, 3, 4, 5 và chúng ta cần sắp xếp theo thứ tự tăng dần. Trong trường hợp này mảng đã được sắp xếp! Vì vậy, khi thực hiện điều này với thuật toán sắp xếp, thuật toán sắp xếp chỉ làm phép so sánh. Không có sự trao đổi các phần từ xảy ra trong khi thuật toán hoạt động. Vì vậy, trong trường hợp này thuật toán xếp sếp thực hiện được hiệu quả tối đa của nó và chỉ cần thời gian tối thiểu. Trường hợp xấu nhất của việc sắp xếp bong bóng là khi chúng ta cần sắp xếp một mảng sắp xếp theo thứ tự giảm dần mà có chuỗi theo thứ tự tăng dần hoặc ngược lại. Xem xét trường hợp của một mảng theo thứ tự 5, 4, 3, 2, 1 và chúng ta cần sử dụng sắp xếp để mảng này theo thứ tự tăng dần. Trong trường hợp này, thuật toán tạo ra tối đa số lượng các phép so sánh cùng với số lượng các sự trao đổi phần tử cũng tối đa. Do đó thuật toán cho hiệu suất tệ nhất của nó (mất thời gian tối đa)

Cải thiện hiệu suất các thuật toán trong C

Nhiều trường hợp có thể xảy ra khi ta phân tích một thuật toán phân loại. Giống như trường hợp tốt nhất và trường hợp xấu nhất. Trong trường hợp tốt nhất của phân loại mảng 1, 2, 3, 4, 5 chúng ta đã thấy rằng "không có sự trao đổi các phần tử" xảy ra bất cứ lúc nào (thông qua việc làm việc của thuật toán). Bây giờ hãy xem xét một kịch bản sắp xếp một mảng thứ tự 1, 2, 3, 5, 4; Ở đây chỉ có hai yếu tố cuối cùng không theo thứ tự, 3 phần tử đầu tiên là theo thứ tự. Theo thuật toán sắp xếp, phần tử lớn nhất sẽ chiếm vị trí cuối cùng sau khi hoàn thành vòng lặp đầu tiên. Điều đó có nghĩa là, sau lần qua đầu tiên, mảng sẽ trở thành 1, 2, 3, 4, 5 - và nó được sắp xếp. Vì vậy, trong trường hợp này, 4 vòng còn lại được thực hiện bởi vòng FOR đầu tiên là một sự lãng phí thời gian. Sau lần qua đầu tiên, chỉ có sự so sánh các phần tử sẽ diễn ra và sẽ không có "sự trao đổi các phần tử".

Từ phân tích này, chúng ta có thể bỏ qua phần còn lại của vòng lặp bằng cách đưa ra một tuyên bố kết thúc hoặc sử dụng một cờ. Bằng cách này, chúng ta tiết kiệm rất nhiều thời gian mà có thể đã bị mất trong vòng lặp không cần thiết. Sửa đổi này có thể được thực hiện bằng cách sử dụng đoạn code sau đây.

for(i=0; ia[j+1])

{

temp=a[j];

a[j]=a[j+1];

a[j+1]=temp;

flag=0;

}

}

}

Hy vọng bạn đã hiểu thuật toán " Bubble Sort " cũng đủ. Nếu bạn có bất kỳ khó hiểu nào, vui lòng hỏi trong phần nhận xét.