Sắp xếp các phương pháp trong lập trình: sắp xếp theo "bong bóng"

Sắp xếp theo một bong bóng không chỉ không được coi là phương pháp nhanh nhất, hơn nữa, nó đóng danh sách các cách đặt hàng chậm nhất. Tuy nhiên, nó cũng có lợi thế của nó. Vì vậy, phân loại theo phương pháp bong bóng là giải pháp hợp lý nhất và tự nhiên cho vấn đề, nếu bạn cần sắp xếp các yếu tố theo một thứ tự nhất định. Một người bình thường, ví dụ, sẽ sử dụng nó bằng tay, chỉ đơn giản bằng trực giác.

Tên bất thường này đến từ đâu?

Tên của phương pháp đã được phát minh bằng cách sử dụng một sự tương đồng với bong bóng khí trong nước. Đây là phép ẩn dụ. Cũng giống như các bọt khí nhỏ tăng lên trên cùng - bởi vì mật độ của chúng lớn hơn bất kỳ chất lỏng (trong trường hợp này - nước), và mỗi phần tử của mảng, nó nhỏ hơn giá trị, nó càng dần dần đi đến đầu danh sách các con số.

Mô tả thuật toán

Bong bóng phân loại được thực hiện như sau:

• Đợt đầu tiên: các yếu tố của mảng số được lấy trong hai và cũng được so sánh theo cặp. Nếu trong một số hai phần tử giá trị đầu tiên lớn hơn thứ hai, chương trình sẽ trao đổi địa điểm;
• Do đó, con số lớn nhất là ở cuối mảng. Trong khi tất cả các yếu tố khác vẫn như cũ, theo trật tự hỗn độn và cần phân loại thêm;
• Do đó, một lần thứ hai là cần thiết: nó được sản xuất bằng cách tương tự như trước (đã được mô tả) và có một số so sánh - trừ một;
• Ở đèo, số so sánh số ba là một lần ít hơn thứ hai, và số ít hơn hai. Và như vậy;
• Chúng tôi tóm tắt rằng mỗi lần vượt qua (trong mảng, một số cụ thể) trừ đi (số lần vượt qua).

Ngay cả thuật toán ngắn hơn của chương trình trong tương lai có thể được viết như sau:

• Mảng số được kiểm tra cho đến khi tìm thấy hai con số, phần thứ hai phải lớn hơn số thứ nhất;
• Không chính xác được đặt liên quan đến mỗi yếu tố khác của mảng, chương trình hoán đổi.

Pseudo mã dựa trên thuật toán được mô tả

Cách thực hiện đơn giản nhất như sau:

Thủ tục Sortirovka_Puzirkom ;

Bắt đầu

Một vòng lặp cho j từ nachalnii_index đến konechii_index ;

Một vòng lặp cho i từ nachalnii_index đến konechii_index-1 ;

Nếu massiv [i]> massiv [i + 1] (phần tử đầu tiên lớn hơn thứ hai), sau đó:

(Thay đổi giá trị tại các địa điểm);

Kết thúc

Tất nhiên, ở đây đơn giản chỉ làm trầm trọng thêm tình hình: các thuật toán đơn giản, nó càng cho thấy tất cả những thiếu sót. Việc tốn nhiều thời gian là quá tuyệt đối ngay cả đối với một mảng nhỏ (có tính tương đối: đối với một người trung bình khoảng thời gian có thể nhỏ, nhưng trong mỗi phần của chương trình mỗi giây hoặc thậm chí mili giây trong tài khoản).

Nó đã thực hiện tốt hơn. Ví dụ, có tính đến việc trao đổi các giá trị trong mảng ở một số nơi:

Thủ tục Sortirovka_Puzirkom ;

Bắt đầu

Sortirovka = true;

Chu kỳ trong khi sortirovka = true;

Sortirovka = sai;

Một vòng lặp cho i từ nachalnii_index đến konechii_index-1 ;

Nếu massiv [i]> massiv [i + 1] (phần tử đầu tiên lớn hơn thứ hai), sau đó:

(Chúng tôi thay đổi các yếu tố ở những nơi);

Sortirovka = true; (Chỉ ra rằng việc trao đổi đã được thực hiện).

Sự kết thúc.

Nhược điểm của phương pháp

Bất lợi chính là khoảng thời gian của quy trình. Thuật toán sắp xếp bong bóng hoạt động bao lâu?

Thời gian thực hiện được tính từ hình vuông của số lượng trong mảng - kết quả cuối cùng là tỷ lệ thuận với nó.

Với trường hợp xấu nhất, mảng sẽ được đi qua nhiều lần vì có các phần tử trong đó, trừ một giá trị. Điều này là bởi vì cuối cùng chỉ có một phần tử không có gì để so sánh, và lần cuối cùng đi qua mảng đó trở thành một hành động vô dụng.

Ngoài ra, phương pháp phân loại bằng các trao đổi đơn giản, như nó được gọi là, chỉ có hiệu quả đối với các mảng có kích thước nhỏ. Bạn không thể xử lý số lượng lớn dữ liệu: kết quả sẽ là lỗi hoặc sự cố của chương trình.

Ưu điểm

Sắp xếp một bong bóng rất dễ hiểu. Trong chương trình giảng dạy của các trường đại học kỹ thuật, khi nghiên cứu thứ tự của các phần tử của một mảng, nó đi trước. Phương pháp này dễ thực hiện cả trong ngôn ngữ lập trình Delphi (D (Delphi) và C / C ++ (C / C plus plus)), một thuật toán cực kỳ đơn giản để sắp xếp các giá trị theo đúng thứ tự và Pascal (Pascal) . Việc sắp xếp với bong bóng là lý tưởng cho người mới bắt đầu.

Do những thiếu sót, thuật toán không được sử dụng cho mục đích ngoại khoá.

Một nguyên tắc rõ ràng về phân loại

Quan điểm ban đầu của mảng là 8 22 4 74 44 37 1 7

Bước 1 8 22 4 74 44 37 1 7

8 22 4 74 44 1 37 7

8 22 4 74 1 44 37 7

8 22 4 1 74 44 37 7

8 22 1 4 74 44 37 7

8 1 22 4 74 44 37 7

1 8 22 4 74 44 37 7

Bước 2 1 8 22 4 74 44 7 37

1 8 22 4 74 7 44 37

1 8 22 4 7 74 44 37

1 8 22 4 7 74 44 37

1 8 4 22 7 74 44 37

1 4 8 22 7 74 44 37

Bước 3 1 4 8 22 7 74 37 44

1 4 8 22 7 37 74 44

1 4 8 22 7 37 74 44

1 4 8 7 22 37 74 44

1 4 7 8 22 37 74 44

Bước 4 1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

Bước 5 1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

Bước 6 1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

Bước 7 1 4 7 8 22 37 44 74

Ví dụ về cách phân loại bằng một bong bóng trong Pascal

Ví dụ:

Const kol_mas = 10;

Var massiv: array [1..kol_mas] của số nguyên;

A, b, k: số nguyên;

Bắt đầu

Writeln ('đầu vào', kol_mas, 'các yếu tố của mảng');

Đối với một: = 1 để kol_mas làm readln (massiv [a]);

Đối với một: = 1 để kol_mas-1 để bắt đầu

Đối với b: = a + 1 để kol_mas bắt đầu

Nếu massiv [a]> massiv [b] bắt đầu

K: = massiv [a]; Massiv [a]: = massiv [b]; Massiv [b]: k;

Kết thúc;

Kết thúc;

Kết thúc;

Writeln ('sau khi sắp xếp');

Đối với một: = 1 để kol_mas do writeln (massiv [a]);

Kết thúc.

Ví dụ về phân loại bằng một bong bóng trong C (C)

Ví dụ:

#include

#include

Int main (int argc, char * argv [])

{

Int massiv [8] = {36, 697, 73, 82, 68, 12, 183, 88}, i, ff;

Đối với (;;) {

Ff = 0;

Đối với (i = 7, i> 0, i -) {

Nếu (massiv [i]

Trao đổi (massiv [i], massiv [i-1]);

Ff ++;

}

}

Nếu (ff == 0) phá vỡ;

}

Getch (); / / Màn hình chậm trễ

Trả lại 0;

}.