Sắp xếp bong bóng và thế là xong
Mọi người đều biết rất rõ rằng phương pháp nhanh nhất được gọi là từ lớp trao đổi. sắp xếp nhanh chóng. Các luận văn được viết về nó, nhiều bài báo trên Habré được dành cho nó và các thuật toán lai phức tạp được phát minh dựa trên nó. Nhưng hôm nay chúng ta sẽ không nói về sắp xếp nhanh chóng, và về một phương thức trao đổi khác - phương pháp cũ sắp xếp bong bóng và những cải tiến, sửa đổi, đột biến và biến thể của nó.
Lợi ích thực tế từ những phương pháp này không quá lớn và nhiều người dùng habra đã trải qua tất cả những điều này ở lớp một. Vì vậy, bài viết hướng đến những người mới quan tâm đến lý thuyết thuật toán và đang thực hiện những bước đầu tiên theo hướng này.
hình ảnh: bong bóng
Hôm nay chúng ta sẽ nói về điều đơn giản nhất phân loại trao đổi.
Nếu có ai quan tâm, tôi sẽ nói rằng có những lớp khác - sắp xếp lựa chọn, sắp xếp chèn, sắp xếp hợp nhất, phân loại phân phối, phân loại lai Và sắp xếp song song. Nhân tiện, cũng có phân loại bí truyền. Đây là nhiều thuật toán giả, về cơ bản là không thể thực hiện được, hài hước và các thuật toán giả khác mà tôi sẽ viết một vài bài báo trong trung tâm “IT Hài hước”.
Nhưng điều này không liên quan gì đến bài giảng hôm nay; bây giờ chúng ta chỉ quan tâm đến việc sắp xếp trao đổi đơn giản. Bản thân cũng có rất nhiều cách sắp xếp trao đổi (tôi biết hơn một tá), vì vậy chúng ta sẽ xem xét cái gọi là sắp xếp bong bóng và một số thứ khác có liên quan chặt chẽ với nó.
Tôi sẽ cảnh báo trước với bạn rằng hầu hết tất cả các phương pháp trên đều rất chậm và sẽ không có phân tích chuyên sâu về độ phức tạp về thời gian của chúng. Một số nhanh hơn, một số chậm hơn, nhưng đại khái, chúng ta có thể nói rằng trung bình ồ(n 2). Ngoài ra, tôi thấy không có lý do gì để bài viết lộn xộn với việc triển khai bằng bất kỳ ngôn ngữ lập trình nào. Những người quan tâm có thể dễ dàng tìm thấy các ví dụ về mã trên Rosetta, Wikipedia hoặc nơi khác.
Nhưng hãy quay lại việc sắp xếp các trao đổi. Thứ tự xảy ra là kết quả của việc tìm kiếm tuần tự lặp đi lặp lại trong mảng và so sánh các cặp phần tử với nhau. Nếu các phần tử được so sánh không được sắp xếp tương đối với nhau thì chúng ta hoán đổi chúng. Câu hỏi duy nhất là làm thế nào để bỏ qua mảng một cách chính xác và trên cơ sở nào để chọn các cặp để so sánh.
Hãy bắt đầu không phải với cách sắp xếp nổi bật tiêu chuẩn mà bằng một thuật toán có tên là...
Kiểu ngu ngốc
Sắp xếp thực sự là ngu ngốc. Chúng tôi xem qua mảng từ trái sang phải và so sánh các hàng xóm trên đường đi. Nếu chúng ta gặp một cặp phần tử chưa được sắp xếp lẫn nhau, chúng ta hoán đổi chúng và quay trở lại hình vuông, tức là về phần đầu. Chúng ta xem lại và kiểm tra lại mảng, nếu lại gặp phải một cặp phần tử lân cận “không chính xác”, thì chúng ta đổi địa điểm và bắt đầu lại từ đầu. Chúng ta tiếp tục cho đến khi mảng được sắp xếp từng chút một.Bạn sẽ nói: “Bất kỳ kẻ ngốc nào cũng có thể sắp xếp như vậy,” và bạn sẽ hoàn toàn đúng. Đây là lý do tại sao việc phân loại được gọi là "ngu ngốc". Trong bài giảng này, chúng tôi sẽ liên tục cải tiến và sửa đổi phương pháp này. Bây giờ anh ấy gặp khó khăn tạm thời ồ(n 3), sau khi thực hiện một chỉnh sửa, chúng tôi sẽ đưa nó đến ồ(n 2), sau đó chúng ta sẽ tăng tốc thêm một chút, rồi thêm một chút nữa và cuối cùng chúng ta sẽ nhận được ồ(N nhật ký N) – và nó sẽ không phải là “Sắp xếp nhanh” chút nào!
Hãy thực hiện một cải tiến duy nhất cho việc sắp xếp ngu ngốc. Sau khi phát hiện ra hai phần tử liền kề chưa được sắp xếp trong quá trình đi qua và hoán đổi chúng, chúng ta sẽ không quay lại phần đầu của mảng mà sẽ bình tĩnh tiếp tục duyệt đến cuối mảng.
Trong trường hợp này, trước mắt chúng ta không có gì hơn ngoài những điều nổi tiếng...
Sắp xếp bong bóng
Hoặc sắp xếp bằng cách trao đổi đơn giản. Một tác phẩm kinh điển bất hủ của thể loại này. Nguyên tắc hoạt động rất đơn giản: chúng ta duyệt mảng từ đầu đến cuối, đồng thời hoán đổi các phần tử lân cận chưa được sắp xếp. Kết quả của lần vượt qua đầu tiên, phần tử tối đa sẽ “nổi” đến vị trí cuối cùng. Bây giờ chúng ta lại duyệt qua phần chưa được sắp xếp của mảng (từ phần tử đầu tiên đến phần tử áp chót) và thay đổi các phần tử lân cận chưa được sắp xếp trong quá trình thực hiện. Phần tử lớn thứ hai sẽ ở vị trí thứ hai đến cuối cùng. Tiếp tục với tinh thần tương tự, chúng ta sẽ duyệt qua phần chưa sắp xếp ngày càng giảm của mảng, đẩy cực đại tìm được về cuối.Nếu chúng ta không chỉ đẩy mức tối đa đến cuối mà còn đẩy mức tối thiểu về đầu, thì chúng ta thành công...
Phân loại máy lắc
Cô ấy giống nhau sắp xếp ngẫu nhiên, cô ấy cũng vậy phân loại cocktail. Quá trình bắt đầu như trong một "bong bóng": chúng tôi vắt kiệt sức đến mức tối đa. Sau đó, chúng ta quay 180 0 và đi theo hướng ngược lại, đồng thời quay lại điểm bắt đầu không phải là mức tối đa mà là mức tối thiểu. Sau khi sắp xếp xong các phần tử đầu tiên và cuối cùng trong mảng, chúng ta thực hiện lại thao tác lộn nhào. Sau khi quay đi quay lại nhiều lần, cuối cùng chúng ta cũng kết thúc quá trình và đứng ở giữa danh sách.Phân loại bằng máy lắc hoạt động nhanh hơn một chút so với phân loại bong bóng, vì cả giá trị tối đa và tối thiểu lần lượt di chuyển qua mảng theo các hướng được yêu cầu. Những cải tiến, như họ nói, là hiển nhiên.
Như bạn có thể thấy, nếu bạn tiếp cận quá trình liệt kê một cách sáng tạo thì việc đẩy các phần tử nặng (nhẹ) đến cuối mảng sẽ diễn ra nhanh hơn. Vì vậy, những người thợ thủ công đã đề xuất một “bản đồ đường đi” phi tiêu chuẩn khác để đi vòng quanh danh sách.
Sắp xếp chẵn-lẻ
Lần này chúng ta sẽ không chạy đi chạy lại trong mảng mà sẽ quay lại ý tưởng đi bộ một cách có hệ thống từ trái sang phải mà chúng ta sẽ chỉ tiến một bước rộng hơn. Ở lần chuyển đầu tiên, các phần tử có khóa lẻ được so sánh với các phần tử lân cận của chúng dựa trên các vị trí chẵn (phần tử thứ nhất được so sánh với phần tử thứ 2, sau đó phần tử thứ 3 với khóa thứ 4, phần tử thứ 5 với phần tử thứ 6, v.v.). Sau đó, ngược lại, chúng ta so sánh/thay đổi phần tử “chẵn” với phần tử “lẻ”. Sau đó lại là “lẻ-chẵn”, rồi lại “chẵn-lẻ”. Quá trình dừng lại khi, sau hai lần liên tiếp đi qua mảng (“chẵn lẻ” và “chẵn lẻ”), không có một trao đổi nào xảy ra. Vì vậy, họ đã sắp xếp nó.Trong một “bong bóng” thông thường, trong mỗi lần chuyển, chúng tôi nén mức tối đa hiện tại một cách có hệ thống đến cuối mảng. Nếu bạn nhảy dọc theo các chỉ số chẵn và lẻ, thì tất cả các phần tử lớn hơn hoặc nhỏ hơn của mảng sẽ đồng thời được đẩy sang đúng một vị trí trong một lần chạy. Nó hoạt động nhanh hơn theo cách này.
Chúng ta hãy nhìn vào cái cuối cùng trang trí lại* Vì Sắp xếp bóng đènka** - Sắp xếp theo lược***. Phương pháp này tổ chức rất nhanh chóng, ồ(n 2) là khó khăn lớn nhất của nó. Trung bình theo thời gian chúng ta có ồ(N nhật ký N), và điều tuyệt vời nhất là bạn thậm chí sẽ không tin vào điều đó, ồ(N). Đó là, một đối thủ cạnh tranh rất xứng đáng với tất cả các loại "loại nhanh" và điều này, bạn nhớ nhé, không cần sử dụng đệ quy. Tuy nhiên, tôi đã hứa rằng hôm nay chúng ta sẽ không đi sâu vào tốc độ di chuyển, vì vậy tôi sẽ ngừng nói và chuyển thẳng sang thuật toán.
Tất cả là lỗi của rùa
Một chút nền tảng. Năm 1980, Włodzimierz Dobosiewicz giải thích tại sao phương pháp sắp xếp bong bóng và các dẫn xuất của nó hoạt động chậm đến vậy. Tất cả là do rùa. “Rùa” là những phần tử nhỏ nằm ở cuối danh sách. Như bạn có thể nhận thấy, các loại bong bóng tập trung vào “thỏ” (đừng nhầm với “thỏ” của Babushkin – các phần tử có giá trị lớn ở đầu danh sách. Họ di chuyển rất nhanh về phía đích. Nhưng loài bò sát chậm chạp bò đến đầu một cách miễn cưỡng. Bạn có thể tùy chỉnh bánh tortilla bằng cách sử dụng lược.Hình ảnh: con rùa tội lỗi
Phân loại lược
Trong “bong bóng”, “shaker” và “chẵn lẻ”, khi lặp qua một mảng, các phần tử lân cận sẽ được so sánh. Ý tưởng chính của “lược” là ban đầu tạo ra một khoảng cách đủ lớn giữa các phần tử được so sánh và khi mảng được sắp xếp, thu hẹp khoảng cách này xuống mức tối thiểu. Bằng cách này, chúng tôi chải mảng, dần dần làm phẳng nó thành những sợi ngày càng gọn gàng.Tốt hơn là nên tính đến khoảng cách ban đầu giữa các phần tử được so sánh, không chỉ bất kỳ mà còn tính đến một giá trị đặc biệt gọi là yếu tố khử, giá trị tối ưu của nó là khoảng 1,247. Đầu tiên, khoảng cách giữa các phần tử bằng kích thước của mảng chia cho sự giảm bớt nguyên tố(tất nhiên kết quả được làm tròn đến số nguyên gần nhất). Sau đó, sau khi duyệt mảng ở bước này, chúng ta lại chia bước đó cho sự giảm bớt nguyên tố và xem lại danh sách một lần nữa. Điều này tiếp tục cho đến khi chênh lệch chỉ số đạt đến một. Trong trường hợp này, mảng được sắp xếp bằng bong bóng thông thường.
Giá trị tối ưu đã được thiết lập bằng thực nghiệm và lý thuyết sự giảm bớt nguyên tố:
Khi phương pháp này được phát minh, rất ít người chú ý đến nó vào đầu những năm 70, 80. Một thập kỷ sau, khi lập trình không còn là lĩnh vực của các nhà khoa học và kỹ sư IBM mà đã nhanh chóng trở nên phổ biến rộng rãi, phương pháp này đã được Stephen Lacy và Richard Box khám phá lại, nghiên cứu và phổ biến vào năm 1991.
Đó thực sự là tất cả những gì tôi muốn nói với bạn về việc sắp xếp bong bóng và những thứ khác thích nó.
- Ghi chú
* rút gọn ( tiếng Ukraina) - sự cải tiến
** Sắp xếp theo bóng đèn ( tiếng Ukraina) – Sắp xếp bong bóng
*** Sắp xếp theo lược ( tiếng Ukraina) – Phân loại lược
Hôm nay chúng ta sẽ đề cập đến chủ đề sắp xếp trong Pascal. Có khá nhiều phương pháp khác nhau, hầu hết chúng không được biết đến rộng rãi và về nguyên tắc, kiến thức về chúng là không cần thiết. Chỉ cần biết bộ cơ bản và một vài bộ bổ sung là đủ. Trong bài viết này, tôi sẽ kể cho bạn về cách sắp xếp nổi tiếng nhất - sắp xếp bong bóng, còn được gọi là sắp xếp trao đổi đơn giản.
Đầu tiên, sắp xếp trong Pascal là gì và tại sao nó lại cần thiết? Sắp xếp là phương pháp sắp xếp một mảng (thường theo thứ tự tăng dần hoặc giảm dần). Trong các bài toán có những dòng như “sắp xếp các phần tử mảng, bắt đầu từ mức tối thiểu (tối đa)” . Hãy nhớ rằng đây là điều tương tự.
Hãy quay trở lại sắp xếp bong bóng. Tại sao cô lại được đặt tên như vậy? Vấn đề là đây là một sự tương tự. Hãy tưởng tượng một mảng thông thường được sắp xếp theo chiều dọc. Kết quả của việc sắp xếp là các phần tử nhỏ hơn sẽ di chuyển lên trên. Nghĩa là, ở đây mảng có thể được biểu diễn dưới dạng nước và các phần tử nhỏ hơn ở dạng bong bóng nổi lên trên.
Bây giờ hãy nói nhiều hơn về chính thuật toán. Nó khá đơn giản:
1. Để sắp xếp, sử dụng 2 chu trình, một chu trình lồng vào nhau. Một cái được sử dụng cho các bước, cái còn lại cho các bước phụ.
2. Bản chất của thuật toán là so sánh hai phần tử. Chính xác là hai. Hãy để tôi giải thích, ví dụ chúng ta có một mảng có 10 phần tử. Các phần tử sẽ được so sánh theo cặp: 1 và 2, 2 và 3, 3 và 4, 4 và 5, 6 và 7, v.v. Khi so sánh các cặp, nếu phần tử trước lớn hơn phần tử tiếp theo thì chúng sẽ bị hoán đổi. Ví dụ: nếu phần tử thứ hai là 5 và phần tử thứ ba là 2 thì chúng sẽ hoán đổi chúng.
3. Sắp xếp bong bóng được chia thành các bước. Trong mỗi bước, việc so sánh theo cặp được thực hiện. Kết quả của mỗi bước là các phần tử lớn nhất bắt đầu xếp hàng từ cuối mảng. Tức là sau bước đầu tiên, phần tử lớn nhất của mảng sẽ ở vị trí cuối cùng. Ở bước thứ hai, công việc được thực hiện với tất cả các phần tử ngoại trừ phần tử cuối cùng. Một lần nữa, phần tử lớn nhất được tìm thấy và đặt ở cuối mảng đang được làm việc. Bước thứ ba lặp lại bước thứ hai và cứ như vậy cho đến khi mảng được sắp xếp. Để dễ hiểu hơn, tôi sẽ đưa ra một ví dụ rõ ràng. Hãy lấy một mảng gồm 7 phần tử: 2,5,11,1,7,8,3. Chúng ta hãy xem. (Click vào hình để phóng to hình ảnh)
Hãy chuyển trực tiếp đến mã. Như đã đề cập, chúng ta cần hai chu kỳ. Nó sẽ trông như thế này
hằng số
m = 7; (số phần tử trong mảng)
var
msort: mảng số nguyên; (thực ra là mảng của chúng tôi)
i, j, k: số nguyên; (i là bước, j là bước phụ)
bắt đầu
writeln("Nhập phần tử mảng");
for i:= 1 to m do
đọc(msort[i]);
Với i:= 1 to m - 1 do
cho j:= 1 với m - tôi làm
nếu msort[j] > msort thì bắt đầu
k:= msort[j];
msort[j] := msort;
loại := k;
kết thúc;
Write("Sắp xếp mảng: ");
for i:= 1 to m do
viết(msort[i]:4);
kết thúc.
Chú ý phần tử k. Nó chỉ cần cho một mục đích: hoán đổi hai phần tử của một mảng. Thực tế là trong Pascal không có chức năng đặc biệt nào có thể thực hiện hành động như vậy. Vì vậy, bạn phải tự vẽ, thêm một yếu tố bổ sung để trao đổi. Bài viết này kết thúc bằng phương pháp sắp xếp bong bóng, các bài viết tiếp theo sẽ được đăng trong tuần sau (hoặc có thể sớm hơn).
Người ta ước tính rằng có tới một phần tư thời gian của các máy tính tập trung được dùng để phân loại dữ liệu. Điều này là do việc tìm một giá trị trong một mảng đã được sắp xếp trước sẽ dễ dàng hơn nhiều. Nếu không, việc tìm kiếm sẽ giống như tìm kim đáy bể.
Có những lập trình viên dành toàn bộ thời gian làm việc để nghiên cứu và thực hiện các thuật toán sắp xếp. Điều này là do phần lớn phần mềm kinh doanh liên quan đến quản lý cơ sở dữ liệu. Mọi người tìm kiếm cơ sở dữ liệu để biết thông tin mọi lúc. Điều này có nghĩa là các thuật toán tìm kiếm đang có nhu cầu cao.
Nhưng có một "nhưng". Thuật toán tìm kiếm hoạt động nhanh hơn nhiều với cơ sở dữ liệu đã được sắp xếp. Trong trường hợp này, chỉ cần tìm kiếm tuyến tính.
Mặc dù tại một số thời điểm máy tính không có người dùng nhưng các thuật toán sắp xếp vẫn tiếp tục hoạt động trên cơ sở dữ liệu. Người tìm kiếm quay lại và cơ sở dữ liệu đã được sắp xếp dựa trên mục đích tìm kiếm này hoặc mục đích tìm kiếm khác.
Bài viết này cung cấp các ví dụ về việc triển khai các thuật toán sắp xếp tiêu chuẩn.
Sắp xếp lựa chọn
Để sắp xếp một mảng theo thứ tự tăng dần, bạn phải tìm phần tử có giá trị lớn nhất ở mỗi lần lặp. Với nó, bạn cần trao đổi phần tử cuối cùng. Phần tử tiếp theo có giá trị cao nhất được đặt ở vị trí thứ hai đến vị trí cuối cùng. Điều này sẽ xảy ra cho đến khi các phần tử ở vị trí đầu tiên trong mảng theo đúng thứ tự.
Mã C++
void SortAlgo::selectionSort(int data, int lenD) ( int j = 0; int tmp = 0; for (int i=0; i
Sắp xếp bong bóng
Sắp xếp bong bóng so sánh các phần tử liền kề và hoán đổi vị trí nếu phần tử tiếp theo nhỏ hơn phần tử trước. Nhiều lần đi qua dữ liệu được yêu cầu. Trong lần chuyển đầu tiên, hai phần tử đầu tiên trong mảng được so sánh. Nếu chúng không theo thứ tự, chúng sẽ được đổi chỗ và sau đó các phần tử trong cặp tiếp theo sẽ được so sánh. Trong cùng điều kiện, họ cũng đổi chỗ cho nhau. Do đó, việc sắp xếp xảy ra trong mỗi chu kỳ cho đến khi đạt đến cuối mảng.
Mã C++
void SortAlgo::bubbleSort(int data, int lenD) ( int tmp = 0; for (int i = 0;i Sắp xếp chèn chia mảng thành hai vùng: có thứ tự và không có thứ tự. Ban đầu, toàn bộ mảng là một vùng không có thứ tự. Ở lần chuyển đầu tiên, phần tử đầu tiên từ vùng không có thứ tự sẽ bị xóa và đặt vào đúng vị trí trong vùng có thứ tự. Trên mỗi lần vượt qua, kích thước của vùng có thứ tự tăng thêm 1 và kích thước của vùng bị xáo trộn giảm đi 1. Vòng lặp chính chạy từ 1 đến N-1. Ở lần lặp thứ j, phần tử [i] được chèn vào đúng vị trí trong vùng có thứ tự. Điều này được thực hiện bằng cách dịch chuyển tất cả các phần tử của vùng có thứ tự lớn hơn [i] một vị trí sang phải. [i] được chèn vào khoảng trống giữa các phần tử nhỏ hơn [i] và các phần tử lớn hơn [i]. Mã C++
void SortAlgo::insertionSort(int data, int lenD) ( int key = 0; int i = 0; for (int j = 1;j Mã C++
void SortAlgo::mergeSort(int data, int lenD) ( if (lenD>1)( int middle = lenD/2; int rem = lenD-middle; int * L = new int; int * R = new int; for ( int tôi=0;i Sắp xếp nhanh sử dụng thuật toán chia để trị. Nó bắt đầu bằng cách chia mảng ban đầu thành hai vùng. Các phần này nằm ở bên trái và bên phải của phần tử được đánh dấu, được gọi là phần hỗ trợ. Khi kết thúc quá trình, một phần sẽ chứa các phần tử nhỏ hơn tham chiếu và phần còn lại sẽ chứa các phần tử lớn hơn tham chiếu. Mã C++
void SortAlgo::quickSort(int * data, int const len) ( int const lenD = len; int Pivot = 0; int ind = lenD/2; int i,j = 0,k = 0; if (lenD>1) ( int * L = new int ; int * R = new int ; trục = dữ liệu; for (i=0;i Sắp xếp chèn
Hợp nhất sắp xếp
Sắp xếp nhanh chóng
