Đánh giá thuật toán sắp xếp nổi bọt
Độ phức tạp thuật toán
- Trường hợp tốt: O(n)
- Trung bình: O(n^2)
- Trường hợp xấu: O(n^2)
Không gian bộ nhớ sử dụng: O(1)
Nếu bạn đang cần học một ngôn ngữ lập trình, hay tìm tới các khóa học hay mà tôi chia sẻ ở mục khóa học nhé. Bạn hãy để lại các thắc mắc, ý kiến đóng góp nếu có xuống mục bình luận ở cuối bài viết nhé.
Theo dõi lập trình không khó tại:
Sắp xếp nổi bọt
Phân loại | Giải thuật sắp xếp |
Cấu trúc dữ liệu | Ngẫu nhiên |
Hiệu suất trường hợp tệ nhất | Trung bình |
Độ phức tạp không gian trường hợp tệ nhất | Không tốn thêm vùng nhớ |
Tối ưu | Không |
Sắp xếp nổi bọt (tiếng Anh: bubble sort) là một thuật toán sắp xếp đơn giản, với thao tác cơ bản là so sánh hai phần tử kề nhau, nếu chúng chưa đứng đúng thứ tự thì đổi chỗ (swap). Có thể tiến hành từ trên xuống (bên trái sang) hoặc từ dưới lên (bên phải sang). Sắp xếp nổi bọt còn có tên là sắp xếp bằng so sánh trực tiếp. Nó sử dụng phép so sánh các phần tử nên là một giải thuật sắp xếp kiểu so sánh.
Mã thật ví dụ[sửa | sửa mã nguồn]
Viết bằng Pascal[sửa | sửa mã nguồn]
var a: array[1..1000] of integer; n, i: integer; procedure BubbleSort; var i, j, tmp: integer; begin for i:= 1 to n – 1 do for j:= i + 1 to n do if a[i] < a[j] then begin tmp:= a[i]; a[i]:= a[j]; a[j]:= tmp; end; end; BEGIN readln(n); for i:= 1 to n do readln(a[i]); BubbleSort; for i:= 1 to n do write(a[i], ‘ ‘); readln END.
Viết bằng Java[sửa | sửa mã nguồn]
private static void bubbleSort(int[] unsortedArray, int length) { int temp, counter, index; for(counter=0; counter
unsortedArray[index+1]) { //Test if need a swap or not. temp = unsortedArray[index]; //These three lines just swap the two elements: unsortedArray[index] = unsortedArray[index+1]; unsortedArray[index+1] = temp; } } } }
Viết bằng C++[sửa | sửa mã nguồn]
#include
using namespace std; long long a[N], n;//Thay N là số phần tử trong mảng template
> void bubblesort(T *L,T *R,Cmp ss= less
()) //sap *L,*(L+1)…*(R-1) { for(T *i=L;i
L;j–) if(ss(*j,*(j-1))) swap(*j,*(j-1)); } int main() { cin>>n; for(int i=1; i<=n;i++) cin>>a[i]; bubblesort(a+1,a+n+1); for(int i=1; i<=n;i++) cout<
Viết bằng PHP[sửa | sửa mã nguồn]
$arr=array(1,5,7,8,9,10,2,3,6); function s($a,$b){ if($a==$b){ return 1; } if($a<$b){ return 1; }else{ return -1; } } usort($arr,’s’); print_r($arr); exit(); other code $arr = […]; $arr_count = count($arr); //loop for ($i = 0; $i < $arr_count; $i++) { for ($j = 1; $j < $arr_count – $i; $j++) { if ($arr[$j-1] > $arr[$j]) { $tmp = $arr[$j-1]; $arr[$j-1] = $arr[$j]; $arr[$j] = $tmp; } } } for($i=0;$i<$arr_count;$i++){ echo $arr[$i].””; }
Viết bằng Python[sửa | sửa mã nguồn]
list = [] list_final = [] num = int(input(“how many number you want to add?\n”)) for i in range(num) : number = int(input(“adding numbers”)) list.append(number) if list[i] not in list_final : list_final.append(list[i])#if list exits the same number many timnes , it will delete and make the list_final for j in range(len(list_final)): for k in range(j): if list_final[j] < list_final[k]:#compare numbers in the list tmp = list_final[j] list_final[j] = list_final[k] list_final[k] = tmp print(list_final)
Chào mừng các bạn quay trở lại với blog của Nguyễn Văn Hiếu. Đây là một bài viết trong series các thuật toán sắp xếp có minh họa code sử dụng ngôn ngữ lập trình C++. Ở bài viết này Nguyễn Văn Hiếu xin giới thiệu tới các bạn thuật toán sắp xếp nổi bọt. Nội dung bài viết bao gồm các phần sau:
- Ý tưởng của thuật toán
- Ví dụ minh họa
- Minh họa thuật toán sử dụng ngôn ngữ C++
- Đánh giá thuật toán
Lưu ý: Bài viết chỉ mô tả cho việc sắp xếp dãy số tăng dần theo thuật toán sắp xếp nổi bọt. Việc sắp xếp dãy số giảm dần sẽ tương tự và bạn đọc tự tìm hiểu
Bài viết liên quan:
- Sắp xếp dãy số theo thứ tự giảm dần, tăng dần trong C/C++
- Cây tìm kiếm nhị phân – Binary search tree
- Danh sách liên kết đơn – Single linked list
Giải thuật mẫu cho sắp xếp nổi bọt (Bubble Sort)
Chúng ta thấy rằng giải thuật sắp xếp nổi bọt so sánh mỗi cặp phần tử trong mảng trừ khi cả toàn bộ mảng đó đã hoàn toàn được sắp xếp theo thứ tự tăng dần. Điều này có thể làm tăng độ phức tạp, tức là tăng các thao tác so sánh và tráo đổi không cần thiết nếu như mảng này không cần sự tráo đổi nào nữa khi tất cả các phần tử đã được sắp xếp theo thứ tự tăng dần rồi.
Để tránh việc này xảy ra, chúng ta có thể sử dụng một biến swapped chẳng hạn để giúp chúng ta biết có cần thực hiện thao tác tráo đổi thứ tự hay không. Nếu không cần thiết thì thoát khỏi vòng lặp.
Bạn theo dõi phần giải thuật mẫu minh họa sau:
Bắt đầu hàm bubbleSort( list : mảng các phần tử ) loop = list.count; for i = 0 tới loop-1 thực hiện: swapped = false for j = 0 tới loop-1 thực hiện: /* so sánh các phần tử cạnh nhau */ if list[j] > list[j+1] then /* tráo đổi chúng */ swap( list[j], list[j+1] ) swapped = true kết thúc if kết thúc for /*Nếu không cần tráo đổi phần tử nào nữa thì tức là mảng đã được sắp xếp. Thoát khỏi vòng lặp.*/ if(not swapped) then break kết thúc if kết thúc for Kết thúc hàm return list
Ví dụ minh họa
Giả sử chúng ta cần sắp xếp dãy số [5 1 4 2 8] này tăng dần.Lần lặp đầu tiên:( 5 1 4 2 8 ) –> ( 1 5 4 2 8 ), Ở đây, thuật toán sẽ so sánh hai phần tử đầu tiên, và đổi chỗ cho nhau do 5 > 1.( 1 5 4 2 8 ) –> ( 1 4 5 2 8 ), Đổi chỗ do 5 > 4( 1 4 5 2 8 ) –> ( 1 4 2 5 8 ), Đổi chỗ do 5 > 2( 1 4 2 5 8 ) –> ( 1 4 2 5 8 ), Ở đây, hai phần tử đang xét đã đúng thứ tự (8 > 5), vậy ta không cần đổi chỗ.
Lần lặp thứ 2:( 1 4 2 5 8 ) –> ( 1 4 2 5 8 )( 1 4 2 5 8 ) –> ( 1 2 4 5 8 ), Đổi chỗ do 4 > 2( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )Bây giờ, dãy số đã được sắp xếp, Nhưng thuật toán của chúng ta không nhận ra điều đó ngay được. Thuật toán sẽ cần thêm một lần lặp nữa để kết luận dãy đã sắp xếp khi và khi khi nó đi từ đầu tới cuối mà không có bất kỳ lần đổi chỗ nào được thực hiện.
Lần lặp thứ 3:( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
Giải thuật cho sắp xếp nổi bọt (Bubble Sort)
Giả sử list là một mảng có n phần tử. Tiếp đó giả sử hàm swap để tráo đổi giá trị của các phần tử trong mảng (đây là giả sử, tất nhiên là bạn có thể viết code riêng cho hàm swap này).
Bắt đầu giải thuật BubbleSort(list) for tất cả phần tử trong list if list[i] > list[i+1] swap(list[i], list[i+1]) kết thúc if kết thúc for return list Kết thúc BubbleSort
Cách giải thuật sắp xếp nổi bọt làm việc?
Giả sử chúng ta có một mảng không có thứ tự gồm các phần tử như dưới đây. Bây giờ chúng ta sử dụng giải thuật sắp xếp nổi bọt để sắp xếp mảng này.
Giải thuật sắp xếp nổi bọt bắt đầu với hai phần tử đầu tiên, so sánh chúng để kiểm tra xem phần tử nào lớn hơn.
Trong trường hợp này, 33 lớn hơn 14, do đó hai phần tử này đã theo thứ tự. Tiếp đó chúng ta so sánh 33 và 27.
Chúng ta thấy rằng 33 lớn hơn 27, do đó hai giá trị này cần được tráo đổi thứ tự.
Mảng mới thu được sẽ như sau:
Tiếp đó chúng ta so sánh 33 và 35. Hai giá trị này đã theo thứ tự.
Sau đó chúng ta so sánh hai giá trị kế tiếp là 35 và 10.
Vì 10 nhỏ hơn 35 nên hai giá trị này chưa theo thứ tự.
Tráo đổi thứ tự hai giá trị. Chúng ta đã tiến tới cuối mảng. Vậy là sau một vòng lặp, mảng sẽ trông như sau:
Để đơn giản, tiếp theo mình sẽ hiển thị hình ảnh của mảng sau từng vòng lặp. Sau lần lặp thứ hai, mảng sẽ trông giống như:
Sau mỗi vòng lặp, ít nhất một giá trị sẽ di chuyển tới vị trí cuối. Sau vòng lặp thứ 3, mảng sẽ trông giống như:
Và khi không cần tráo đổi thứ tự phần tử nào nữa, giải thuật sắp xếp nổi bọt thấy rằng mảng đã được sắp xếp xong.
Tiếp theo, chúng ta tìm hiểu thêm một số khía cạnh thực tế của giải thuật sắp xếp.
Giải thuật[sửa | sửa mã nguồn]
Sắp xếp từ trên xuống[sửa | sửa mã nguồn]
Giả sử dãy cần sắp xếp có n phần tử. Khi tiến hành từ trên xuống, ta so sánh hai phần tử đầu, nếu phần tử đứng trước lớn hơn phần tử đứng sau thì đổi chỗ chúng cho nhau. Tiếp tục làm như vậy với cặp phần tử thứ hai và thứ ba và tiếp tục cho đến cuối tập hợp dữ liệu, nghĩa là so sánh (và đổi chỗ nếu cần) phần tử thứ n-1 với phần tử thứ n. Sau bước này phần tử cuối cùng chính là phần tử lớn nhất của dãy.
Sau đó, quay lại so sánh (và đổi chố nếu cần) hai phần tử đầu cho đến khi gặp phần tử thứ n-2….
Ghi chú: Nếu trong một lần duyệt, không phải đổi chỗ bất cứ cặp phần tử nào thì danh sách đã được sắp xếp xong.
Sắp xếp từ dưới lên[sửa | sửa mã nguồn]
Sắp xếp từ dưới lên so sánh (và đổi chỗ nếu cần) bắt đầu từ việc so sánh cặp phần tử thứ n-1 và n. Tiếp theo là so sánh cặp phần tử thứ n-2 và n-1,… cho đến khi so sánh và đổi chỗ cặp phần tử thứ nhất và thứ hai. Sau bước này phần tử nhỏ nhất đã được nổi lên vị trí trên cùng (nó giống như hình ảnh của các “bọt” khí nhẹ hơn được nổi lên trên). Tiếp theo tiến hành với các phần tử từ thứ 2 đến thứ nm.
Tài liệu tham khảo
- https://vi.wikipedia.org/wiki/S%E1%BA%AFp_x%E1%BA%BFp_n%E1%BB%95i_b%E1%BB%8Dt
- https://en.wikipedia.org/wiki/Bubble_sort
©️ Tác giả: Lê Ngọc Hoa từ Viblo
All Rights Reserved
BàiThuật toán sắp xếp nổi bọt
Chào mừng các bạn quay trở lại với blog của Nguyễn Văn Hiếu. Đây là một bài viết trong series các thuật toán sắp xếp có minh họa code sử dụng ngôn ngữ lập trình C++. Ở bài viết này Nguyễn Văn Hiếu xin giới thiệu tới các bạn thuật toán sắp xếp nổi bọt. Nội dung bài viết bao gồm các phần sau:
- Ý tưởng của thuật toán
- Ví dụ minh họa
- Minh họa thuật toán sử dụng ngôn ngữ C++
- Đánh giá thuật toán
Lưu ý: Bài viết chỉ mô tả cho việc sắp xếp dãy số tăng dần theo thuật toán sắp xếp nổi bọt. Việc sắp xếp dãy số giảm dần sẽ tương tự và bạn đọc tự tìm hiểu
Bài viết liên quan:
- Sắp xếp dãy số theo thứ tự giảm dần, tăng dần trong C/C++
- Cây tìm kiếm nhị phân – Binary search tree
- Danh sách liên kết đơn – Single linked list
NỘI DUNG BÀI VIẾT
Lời giải
Sắp xếp nổi bọt (Bubble Sort) là một giải thuật sắp xếp đơn giản. Giải thuật sắp xếp này được tiến hành dựa trên việc so sánh cặp phần tử liền kề nhau và tráo đổi thứ tự nếu chúng không theo thứ tự.
Giải thuật này không thích hợp sử dụng với các tập dữ liệu lớn khi mà độ phức tạp trường hợp xấu nhất và trường hợp trung bình là Ο(n2) với n là số phần tử.
Giải thuật sắp xếp nổi bọt là giải thuật chậm nhất trong số các giải thuật sắp xếp cơ bản. Giải thuật này còn chậm hơn giải thuật đổi chỗ trực tiếp mặc dù số lần so sánh bằng nhau, nhưng do đổi chỗ hai phần tử kề nhau nên số lần đổi chỗ nhiều hơn.
Dưới đây là chương trình C để giải bài sắp xếp nổi bọt (Bubble Sort) trong C:
#include
#include
#define MAX 10 int arr[MAX] = {6, 7, 0, 2, 8, 1, 3, 9, 4, 5}; void bubbleSort() { int temp; int i,j; bool swapped = false; // lap qua tat ca cac so for(i = 0; i < MAX-1; i++) { swapped = false; // vong lap thu hai for(j = 0; j < MAX-1-i; j++) { printf(“So sanh cac phan tu: [ %d, %d ] “, arr[j],arr[j+1]); // kiem xa xem so ke tiep co nho hon so hien tai hay khong // trao doi cac so. // (Muc dich: lam noi bot (bubble) so lon nhat) if(arr[j] > arr[j+1]) { temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; swapped = true; printf(” => trao doi [%d, %d]\n”, arr[j], arr[j+1]); } else { printf(” => khong can trao doi\n”); } } // neu khong can trao doi nua, tuc la // mang da duoc sap xep va thoat khoi vong lap. if(!swapped) { break; } printf(“Vong lap thu %d#: “, (i+1)); display(); } } void display() { int i; printf(“[“); // Duyet qua tat ca phan tu for(i = 0; i < MAX; i++){ printf(“%d “, arr[i]); } printf(“]\n”); } main(){ printf(“Mang du lieu dau vao: “); display(); printf(“—————————–\n”); bubbleSort(); printf(“—————————–\n”); printf(“\nMang sau khi da sap xep: “); display(); }
Chạy chương trình C trên cho kết quả như sau:
Giải thuật sắp xếp nổi bọt (Bubble Sort)
Ví dụ minh họa
Giả sử chúng ta cần sắp xếp dãy số [5 1 4 2 8] này tăng dần.Lần lặp đầu tiên:( 5 1 4 2 8 ) –> ( 1 5 4 2 8 ), Ở đây, thuật toán sẽ so sánh hai phần tử đầu tiên, và đổi chỗ cho nhau do 5 > 1.( 1 5 4 2 8 ) –> ( 1 4 5 2 8 ), Đổi chỗ do 5 > 4( 1 4 5 2 8 ) –> ( 1 4 2 5 8 ), Đổi chỗ do 5 > 2( 1 4 2 5 8 ) –> ( 1 4 2 5 8 ), Ở đây, hai phần tử đang xét đã đúng thứ tự (8 > 5), vậy ta không cần đổi chỗ.
Lần lặp thứ 2:( 1 4 2 5 8 ) –> ( 1 4 2 5 8 )( 1 4 2 5 8 ) –> ( 1 2 4 5 8 ), Đổi chỗ do 4 > 2( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )Bây giờ, dãy số đã được sắp xếp, Nhưng thuật toán của chúng ta không nhận ra điều đó ngay được. Thuật toán sẽ cần thêm một lần lặp nữa để kết luận dãy đã sắp xếp khi và khi khi nó đi từ đầu tới cuối mà không có bất kỳ lần đổi chỗ nào được thực hiện.
Lần lặp thứ 3:( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
Mã giả[sửa | sửa mã nguồn]
Sắp xếp từ trên xuống[sửa | sửa mã nguồn]
procedure bubble_sort1(list L, number n) //n=listsize For number i from n downto 2 for number j from 1 to (i – 1) if L[j] > L[j + 1] //nếu chúng không đúng thứ tự swap(L[j], L[j + 1]) //đổi chỗ chúng cho nhau endif endfor endfor endprocedure
Sắp xếp từ dưới lên[sửa | sửa mã nguồn]
procedure bubble_sort2(list L, number n) //n=listsize For number i from 1 to n-1 for number j from n-1 downto i if L[j] > L[j + 1] //nếu chúng không đúng thứ tự swap(L[j], L[j + 1]) //đổi chỗ chúng cho nhau endif endfor endfor endprocedure
Giảm bớt vòng duyệt[sửa | sửa mã nguồn]
Nếu trong một lần duyệt nào đó với một i cố định khi vòng lặp j kết thúc mà không cần phải đổi chỗ cặp phần tử nào, nghĩa là mọi cặp phần tử kề nhau đã đứng đúng thứ tự thì dãy đã được sắp xếp và không cần tiến hành vòng lặp tiếp theo. Do đó có thể dùng một cờ để kiểm soát việc này. Ta có một đoạn mã giả của thuật toán nổi bọt như sau:
procedure bubble_sort3(list L, number n) i:= n while i > 1 do has_swapped:= 0 //khởi tạo lại giá trị cờ for number j from 1 to (i – 1) if L[j] > L[j + 1] //nếu chúng không đúng thứ tự swap(L[j], L[j + 1]) //đổi chỗ chúng cho nhau has_swapped:= 1 //có đổi chỗ ít nhất một lần, danh sách chưa sắp xếp xong endif endfor if has_swapped = 0 //nếu không có lần đổi chỗ nào, danh sách đã sắp xếp xong exit else //nếu có ít nhất một lần đổi chỗ, danh sách chưa sắp xếp xong i = i – 1 endif enddo endprocedure
Ghi chú: Cũng có thể không cần dùng đến biến i, khi đó mỗi lần kiểm tra đều phải duyệt từ đầu đến cuối dãy.
Làm quen với thuật toán
Nghe đến tên gọi thú vị của thuật toán sắp xếp này có khi các bạn cũng hình dung sơ sơ về phương thức làm việc của thuật toán rồi chứ. Sắp xếp nổi bọt (bubble sort) là một thuật toán sắp xếp cơ bản, chúng ta sẽ thao tác dữ liệu cần sắp xếp “nổi bọt” lần lượt theo thứ tự chúng ta mong muốn (từ trái sang phải, từ dưới lên trên, từ trên xuống dưới, …).
Những điều lưu ý của thuật toán
Ưu điểm
- Là thuật toán cơ bản, dễ hiểu, phù hợp cho người bắt đầu học về sắp xếp.
- Đoạn code ngắn gọn, dễ nhớ.
Nhược điểm
- Hiệu suất chậm nhất trong các thuật toán sắp xếp.
- Không hiệu quả với những dữ liệu lớn.
Thời gian tính và độ phức tạp
Với mỗi ta cần phép so sánh. Do đó số nhiều nhất các lần so sánh và đổi chỗ trong giải thuật là: Do đó ta có độ phúc tạp là .
Sắp xếp nổi bọt (Bubble Sort) là gì ?
Sắp xếp nổi bọt là một giải thuật sắp xếp đơn giản. Giải thuật sắp xếp này được tiến hành dựa trên việc so sánh cặp phần tử liền kề nhau và tráo đổi thứ tự nếu chúng không theo thứ tự.
Giải thuật này không thích hợp sử dụng với các tập dữ liệu lớn khi mà độ phức tạp trường hợp xấu nhất và trường hợp trung bình là Ο(n2) với n là số phần tử.
Giải thuật sắp xếp nổi bọt là giải thuật chậm nhất trong số các giải thuật sắp xếp cơ bản. Giải thuật này còn chậm hơn giải thuật đổi chỗ trực tiếp mặc dù số lần so sánh bằng nhau, nhưng do đổi chỗ hai phần tử kề nhau nên số lần đổi chỗ nhiều hơn.
Triển khai giải thuật sắp xếp nổi bọt trong C
Một điều nữa mà chúng ta chưa nói tới trong 2 phần thiết kế giải thuật đó là cứ sau mỗi vòng lặp thì các giá trị lớn nhất sẽ xuất hiện ở vị trí cuối mảng (như trong hình minh họa: sau vòng lặp 1 là 35; sau vòng lặp 2 là 33 và 35; …). Do đó, vòng lặp tiếp theo sẽ không cần bao gồm cả các phần tử đã được sắp xếp này. Để thực hiện điều này, trong phần code chúng ta giới hạn vòng lặp lặp bên để tránh phải lặp lại các giá trị đã qua sắp xếp này.
Để theo dõi code đầy đủ của giải thuật sắp xếp nổi bọt trong ngôn ngữ C, mời bạn click chuột vào chương: Sắp xếp nổi bọt (Bubble Sort) trong C.
Đã có app VietJack trên điện thoại, giải bài tập SGK, SBT Soạn văn, Văn mẫu, Thi online, Bài giảng….miễn phí. Tải ngay ứng dụng trên Android và iOS.
Follow fanpage của team https://www.facebook.com/vietjackteam/ hoặc facebook cá nhân Nguyễn Thanh Tuyền https://www.facebook.com/tuyen.vietjack để tiếp tục theo dõi các loạt bài mới nhất về Java,C,C++,Javascript,HTML,Python,Database,Mobile…. mới nhất của chúng tôi.
Bài học Cấu trúc dữ liệu và giải thuật phổ biến tại vietjack.com:
- Giải thuật tiệm cận – Asymptotic Algorithms
- Cấu trúc dữ liệu mảng (Array)
- Danh sách liên kết – Linked List
- Cấu trúc dữ liệu ngăn xếp – Stack
- Cấu trúc dữ liệu hàng đợi – Queue
- Tìm kiếm tuyến tính – Linear Search
- Tìm kiếm nhị phân – Binary Search
- Sắp xếp nổi bọt – Bubble Sort
- Sắp xếp chèn – Insertion Sort
Đánh giá thuật toán sắp xếp nổi bọt
Độ phức tạp thuật toán
- Trường hợp tốt: O(n)
- Trung bình: O(n^2)
- Trường hợp xấu: O(n^2)
Không gian bộ nhớ sử dụng: O(1)
Nếu bạn đang cần học một ngôn ngữ lập trình, hay tìm tới các khóa học hay mà tôi chia sẻ ở mục khóa học nhé. Bạn hãy để lại các thắc mắc, ý kiến đóng góp nếu có xuống mục bình luận ở cuối bài viết nhé.
Theo dõi lập trình không khó tại:
Sắp xếp nổi bọt (Bubble Sort) là gì ?
Bài đăng này đã không được cập nhật trong 5 năm
Sắp xếp nổi bọt là một giải thuật sắp xếp đơn giản. Giải thuật sắp xếp này được tiến hành dựa trên việc so sánh cặp phần tử liền kề nhau và tráo đổi thứ tự nếu chúng không theo thứ tự.
Giải thuật này không thích hợp sử dụng với các tập dữ liệu lớn khi mà độ phức tạp trường hợp xấu nhất và trường hợp trung bình là Ο(n2) với n là số phần tử.
Giải thuật sắp xếp nổi bọt là giải thuật chậm nhất trong số các giải thuật sắp xếp cơ bản. Giải thuật này còn chậm hơn giải thuật đổi chỗ trực tiếp mặc dù số lần so sánh bằng nhau, nhưng do đổi chỗ hai phần tử kề nhau nên số lần đổi chỗ nhiều hơn.
Ý tưởng thuật toán: Xuất phát từ phần tử cuối danh sách ta tiến hành so sánh với phần tử bên trái của nó. Nếu phần tử đang xét có khóa nhỏ hơn phần tử bên trái của nó ta tiến đưa nó về bên trái của dãy bằng cách hoán vị với phần tử bên trái của nó. Tiếp tục thực hiện như thế đối với bài toán có n phần tử thì sau n –1 bước ta thu được danh sách tăng dần.
Giải thuật
Bước 1: i=0; //Phần tử đầu tiên
Bước 2:Lần lượt so sánh và đổi chổ (nếu cần) từ phải sang trái đối với các phần từ từ a[n] đến a[i]. với biến gán j=n-i. và lặp lại khi j>i.
Bước 3: i=i+1
Bước 4:
Nếu i < n, quay lại Bước 2.
Ngược lại, dừng, dãy đã cho đã sắp xếp đúng vị trí.
Ví dụ
Cho dãy A gồm các phần tử: 4 5 0 11 8 6 9. Hãy dùng giải thuật sắp xếp nổi bọt để sắp xếp lại dãy đã cho.
Đầu tiên i=0 và j= 6.
Xét aj-1 và aj tức là a6 và a5 . Do 6<9 nên không đổi chỗ và j=j-1;
Xét tiếp a5 và a5 . Do 8>6 nên đổi chỗ 6 và 8 được dãy 4 5 0 11 6 8 9. Sau đó j=j-1;
Xét tiếp a4 và a3 . Do 11>6 nên đổi chỗ 11 và 6 được dãy 4 5 0 6 11 8 9. Sau đó tiếp tục giảm j=j-1;
Xét tiếp a3 và a2 . Do 0<6 nên không đổi chỗ và Sau đó giảm j=j-1;
Xét tiếp a2 và a1 . Do 5>0 nên đổi chỗ 5 và 0 được dãy 4 0 5 6 11 8 9. Sau đó tiếp tục giảm j=j-1;
Xét tiếp a1 và a0 . Do 4>0 nên đổi chỗ 4 và 0 được dãy 0 4 5 6 11 8 9. Sau đó tiếp tục giảm j=j-1;
Do j=i=0 nên tăng biến i lên i=i+1=1;
j=6.
Xét a6 và a5 . Do 9>8 nên không đổi chỗ và giữ nguyên dãy 0 4 5 6 11 8 9. Sau đó giảm j=j-1;
Xét a5 và a4 . Do 11>8 nên đổi chỗ 11 và 8 được dãy 0 4 5 6 8 11 9. Sau đó tiếp tục giảm j=j-1;
Tương tự như trên, giảm j dần về 1. Dãy vẫn giữ nguyên như vậy. Sau đó tăng i lên ;
j=6.
Xét a6 và a5 . Do 11>9 nên đổi chỗ 11 và 9 được dãy 0 4 5 6 8 9 11. Sau đó giảm j=j-1;
Do lúc này i>n nên dừng giải thuật và nhận dãy 0 4 5 6 8 9 11.
Code C/C++
Hàm sắp xếp theo giải thuật 2 vòng lập
void Sapxep(int a[], int n) { int i, j; for (int i = 0; i
i; j--){ if (a[j] < a[j - 1]){ swap(a[j], a[j - 1]); } } } }
void swap(int &a, int &b) { int c = a; a = b; b = c; }
All rights reserved
Nội dung chính
Code sắp xếp nổi bọt trong C/C++
// Code from https://nguyenvanhieu.vn #include
void swap(int &x, int &y) { int temp = x; x = y; y = temp; } // Hàm sắp xếp bubble sort void bubbleSort(int arr[], int n) { int i, j; bool haveSwap = false; for (i = 0; i < n-1; i++){ // i phần tử cuối cùng đã được sắp xếp haveSwap = false; for (j = 0; j < n-i-1; j++){ if (arr[j] > arr[j+1]){ swap(arr[j], arr[j+1]); haveSwap = true; // Kiểm tra lần lặp này có swap không } } // Nếu không có swap nào được thực hiện => mảng đã sắp xếp. Không cần lặp thêm if(haveSwap == false){ break; } } } /* 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”); } // Driver program to test above functions int main() { int arr[] = {64, 34, 25, 12, 22, 11, 90}; int n = sizeof(arr)/sizeof(arr[0]); bubbleSort(arr, n); printf(“Sorted array: n”); printArray(arr, n); return 0; }
Ở đây, trong hàm bubbleSort tôi sử dụng thêm một biến haveSwap để kiểm tra tại lần lặp hiện hành có xảy ra việc đổi chỗ hai số không. Nếu không, ta có thể kết luận mảng đã sắp xếp mà không cần phải thêm một lần lặp nữa.
Kiểm tra kết quả:
Sorted array: 11 12 22 25 34 64 90
Code sắp xếp nổi bọt trong C/C++
// Code from https://blog.luyencode.net #include
void swap(int &x, int &y) { int temp = x; x = y; y = temp; } // Hàm sắp xếp bubble sort void bubbleSort(int arr[], int n) { int i, j; bool haveSwap = false; for (i = 0; i < n-1; i++){ // i phần tử cuối cùng đã được sắp xếp haveSwap = false; for (j = 0; j < n-i-1; j++){ if (arr[j] > arr[j+1]){ swap(arr[j], arr[j+1]); haveSwap = true; // Kiểm tra lần lặp này có swap không } } // Nếu không có swap nào được thực hiện => mảng đã sắp xếp. Không cần lặp thêm if(haveSwap == false){ break; } } } /* 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”); } // Driver program to test above functions int main() { int arr[] = {64, 34, 25, 12, 22, 11, 90}; int n = sizeof(arr)/sizeof(arr[0]); bubbleSort(arr, n); printf(“Sorted array: n”); printArray(arr, n); return 0; }
Ở đây, trong hàm bubbleSort tôi sử dụng thêm một biến haveSwap để kiểm tra tại lần lặp hiện hành có xảy ra việc đổi chỗ hai số không. Nếu không, ta có thể kết luận mảng đã sắp xếp mà không cần phải thêm một lần lặp nữa.
Kiểm tra kết quả:
Sorted array: 11 12 22 25 34 64 90
Miêu tả về thuật toán
Ý tưởng
Ý tưởng thuật toán cũng giống như việc xếp hàng trong giờ thể dục. Thầy giáo thể dục muốn xếp các bạn trong lớp thành một hàng theo thứ tự từ thấp đến cao, thầy so sánh chiều cao của bạn học sinh đứng cạnh nhau trong hàng, nếu bạn bên phải thấp hơn bạn bên trái thì đổi chỗ bạn cho nhau.
Chi tiết thuật toán
Xét một mảng gồm số nguyên:
- Với cách sắp xếp không giảm từ trái qua phải, mục đích của chúng ta là đưa dần các số lớn nhất về cuối dãy (ngoài cùng bên phải).
- Bắt đầu từ vị trí số , xét lần lượt từng cặp phần tử, nếu phần tử bên phải nhỏ hơn phần tử bên trái, ta sẽ thực hiện đổi chỗ phần tử này, nếu không, xét tiếp cặp tiếp theo. Với cách làm như vậy, phần tử nhỏ hơn sẽ “nổi” lên, còn phần tử lớn hơn sẽ “chìm” dần và về bên phải.
- Khi kết thúc vòng thứ nhất, ta sẽ đưa được phần tử lớn nhất về cuối dãy. Sang vòng thứ hai, ta tiếp tục bắt đầu ở vị trí đầu tiên như vậy và đưa được phần tử lớn thứ hai về vị trí thứ hai ở cuối dãy …
- Hình ảnh minh họa thuật toán:
- Thuật toán C++ tham khảo:
// hàm sắp xếp nổi bọt (bubble sort) void BubbleSort(int a[], int n){ int temp; // biến tạm temp for (int i = 0; i < n; i++){ for (int j = i + 1; j < n; j++){ if (a[j] > a[j+1]){ temp = a[j]; a[j] = a[j+1]; a[j+1] = temp; } } } }
- Thuật toán Java tham khảo:
private static void bubbleSort(int[] unsortedArray, int length) { int temp, counter, index; for(counter=0; counter
unsortedArray[index+1]) { //Test if need a swap or not. temp = unsortedArray[index]; //These three lines just swap the two elements: unsortedArray[index] = unsortedArray[index+1]; unsortedArray[index+1] = temp; } } } }
- Thuật toán PHP tham khảo:
$arr = [...]; $arr_count = count($arr); //loop for ($i = 0; $i < $arr_count; $i++) { for ($j = 1; $j < $arr_count - $i; $j++) { if ($arr[$j-1] > $arr[$j]) { $tmp = $arr[$j-1]; $arr[$j-1] = $arr[$j]; $arr[$j] = $tmp; } } } for($i=0;$i<$arr_count;$i++){ echo $arr[$i].""; }
Keywords searched by users: sắp xếp nổi bọt trong c
Categories: Phát hiện thấy 21 Sắp Xếp Nổi Bọt Trong C
See more here: kientrucannam.vn
See more: https://kientrucannam.vn/vn/