Sắp Xếp Nổi Bọt Bubble Sort | Làm Quen Với Thuật Toán

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].""; }


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 )

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 )

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 được hiểu đơn giản như sau:

Thuật toán sắp xếp nổi bọt (Bubble Sort) sẽ tiến hành việc so sánh các cặp phần tử liền kề nhau và tráo đổi vị trí của nó cho đúng thứ tự mà người dùng mong muốn.

Bài viết này được đăng tại [free tuts .net]

Ví dụ:

Chúng ta có một tập các số như sau: A = {20; 5; 25; 30; 22; 40}. Giả sử chúng ta muốn sắp xếp theo chiều tăng dần từ trái sang phải, thì thuật toán sẽ hoạt động như sau:

• Thuật toán sẽ bắt đầu với cặp phần tử đầu tiên là {20; 5}. Trong cặp phần tử này 20 > 5 vì vậy thuật toán sẽ hoán đổi vị trí số 20 cho vị trí số 5. Sau khi hoán đổi được cặp phần tử mới là {5; 20}.
• Tiếp đến thuật toán sẽ so sánh cặp phần tử {20;25}. Trong trường hợp này vị trí của hai phần tử đã đúng, vì vậy thuật toán sẽ giữ nguyên vị trí của nó.
• Cứ như vậy thuật toán sẽ so sánh đến hết các cặp phần tử của tập A. Sau khi so sánh đến hết sẽ được kết quả như sau: A = {5; 20; 22; 25; 30; 40}.

Thuật toán sắp xếp nổi bọt (Bubble Sort) trong C++

Giả sử:

• Chúng ta có arr là một mảng chứa n phần tử.
• Một hàm
  
Swap()

  để tráo đổi các phần tử (hàm này mình sẽ viết ở bên dưới).

Giải thích thuật toán

• Trong thuật toán chúng ta cần tạo một biến haveSwap để kiểm tra xem tại lần lặp hiện tại có xảy ra việc trao đổi hai số hay không.
• Sử dụng vòng lặp for để lặp tất cả các phần tử có trong mảng. Nếu phần tử thứ J > J + 1 thì tiến hành gọi hàm
  
Swap()

  để tráo đổi vị trí. Sau đó gán haveSwap = true và ngược lại.
• Nếu không có Swap nào được thực hiện thì mảng đã được sắp xếp. Khi đó chúng ta sẽ thoát khỏi vòng lặp và không cần lặp thêm nữa.

Thuật toán sắp xếp nổi bọt C++

10 11 12 13 14 15 16 17 18 19

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, …).

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

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

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.

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

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.

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

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

Ví dụ sắp xếp nổi bọt áp dụng với mảng

Chúng ta sẽ áp dụng thuật toán trên để làm một bài toán đơn giản. Cụ thể chúng ta sẽ sắp xếp các phần tử có trong một mảng được nhập tử bàn phím.

Gợi ý:

• Việc đầu tiên chúng ta cần tạo hàm
  
Swap()

  để thực hiện tráo đổi vị trí các phần tử.
• Tiếp theo cần tạo hàm
  
bubbleSort()

  để thực hiện sắp xếp các phần tử.
• Cuối cùng chỉ cần tạo hàm main và yêu cầu người dùng nhập vào các phần tử cho mảng. Sau đó gọi hàm
  
bubbleSort()

  để sắp xếp là xong.

Code Mẫu:

10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64

Kết quả:

Như vậy là chúng ta đã thực hiện xong chương trình sắp xếp các phần tử có trong mảng. Cũng như kết thúc hướng dẫn thuật toán sắp xếp nổi bọt (Bubble Sort) trong C++. Chúc các bạn thực hiện thành công!!!.

Nội dung bài viết: