Chuyển tới nội dung
Home » Thuật Toán Sắp Xếp Nổi Bọt | Ví Dụ Minh Họa

Thuật Toán Sắp Xếp Nổi Bọt | Ví Dụ Minh Họa

Sắp xếp nổi bọt - Tin học 7 | Hoc10

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.

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
Sắp xếp nổi bọt - Tin học 7 | Hoc10
Sắp xếp nổi bọt – Tin học 7 | Hoc10

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.

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

Bài 08. Thuật Toán Sắp Xếp Nổi Bọt (Bubble Sort)  | Cấu Trúc Dữ Liệu Và Giải Thuật
Bài 08. Thuật Toán Sắp Xếp Nổi Bọt (Bubble Sort) | Cấu Trúc Dữ Liệu Và Giải Thuật

Đá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

Bạn đã hiểu về ý tưởng của thuật toán Bubble sort. Bây giờ, chúng ta hãy cùng nhau triển khai ý tưởng đó thành code xem như thế nào nhé.

package bubble.sort.algo;

public class BubbleSort {

// Hàm sắp xếp nổi bọt

void bubbleSort(int arr[]) {

int n = arr.length;

for (int i = 0; i < n – 1; i++)

for (int j = 0; j < n – i – 1; j++)

if (arr[j] > arr[j + 1]) {

// swap arr[j+1] và arr[i]

int temp = arr[j];

arr[j] = arr[j + 1];

arr[j + 1] = temp;

// In các phần tử của arr

void printArray(int arr[]) {

int n = arr.length;

for (int i = 0; i < n; ++i)

System.out.print(arr[i] + ” “);

System.out.println();

public static void main(String args[]) {

BubbleSort ob = new BubbleSort();

int arr[] = { 5, 1, 4, 2, 8 };

System.out.println(“Mảng ban đầu:”);

ob.printArray(arr);

ob.bubbleSort(arr);

System.out.println(“Mảng sau khi sắp xếp:”);

ob.printArray(arr);

Khi chạy chương trình ta có:

Mảng ban đầu:
5, 1, 4, 2, 8
Mảng sau khi sắp xếp:
1, 2 , 4, 5, 8

Phần code bên trên (tức hàm bubbleSort) luôn chạy với thời gian là

O(n^2)

ngay cả khi mảng được sắp xếp.
Nó có thể được tối ưu hóa bằng cách dừng thuật toán nếu vòng lặp bên trong mà không gây ra bất kỳ sự hoán đổi nào.

package bubble.sort.algo;

public class BubbleSortOptimized {

static void bubbleSort(int arr[], int n) {

int i, j, temp;

boolean swapped;

for (i = 0; i < n – 1; i++) {

swapped = false;

for (j = 0; j < n – i – 1; j++) {

if (arr[j] > arr[j + 1]) {

// swap arr[j] và arr[j+1]

temp = arr[j];

arr[j] = arr[j + 1];

arr[j + 1] = temp;

swapped = true;

// Nếu không có phần tử nào để hoán đổi

// bên trong vòng lặp thì Break

if (swapped == false)

break;

// In các phần tử của mảng

static void printArray(int arr[], int size) {

int i;

for (i = 0; i < size; i++)

System.out.print(arr[i] + ” “);

System.out.println();

public static void main(String args[]) {

int arr[] = { 5, 1, 4, 2, 8 };

int n = arr.length;

System.out.println(“Mảng ban đầu:”);

printArray(arr, n);

bubbleSort(arr, n);

System.out.println(“Mảng sau khi sắp xếp:”);

printArray(arr, n);

Giải thuật sắp xếp nổi bọt (Bubble Sort)

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.

#19.1. [C++]. Thuật Toán Sắp Xếp Chèn | Sắp Xếp Nổi Bọt | Sắp Xếp Chọn | Sắp Xếp Đếm Phân Phối
#19.1. [C++]. Thuật Toán Sắp Xếp Chèn | Sắp Xếp Nổi Bọt | Sắp Xếp Chọn | Sắp Xếp Đếm Phân Phối

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

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à .

Cấu trúc dữ liệu và giải thuật : Bubble Sort - Sắp xếp nổi bọt
Cấu trúc dữ liệu và giải thuật : Bubble Sort – Sắp xếp nổi bọt

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 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

Thuật toán sắp xếp nổi bọt - Bubble Sort.
Thuật toán 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 )

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.

minh họa thuật toán sắp xếp  nổi bọt
minh họa thuật toán sắp xếp nổi bọt

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)





Thuật toán sắp xếp nổi bọt (bubble sort)

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.

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

Đá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:

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

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

Cấu trúc dữ liệu và thuật toán #20: Hash table, hash function | DS&A
Cấu trúc dữ liệu và thuật toán #20: Hash table, hash function | DS&A

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

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

Hướng dẫn học Tin Học lớp 7 - SGK: Kết nối tri thức với cuộc sống - Bài 11: Tạo bài trình chiếu
Hướng dẫn học Tin Học lớp 7 – SGK: Kết nối tri thức với cuộc sống – Bài 11: Tạo bài trình chiếu

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

Keywords searched by users: thuật toán sắp xếp nổi bọt

Java] Bubble Sort: Thuật Toán Sắp Xếp Nổi Bọt
Java] Bubble Sort: Thuật Toán Sắp Xếp Nổi Bọt
Thực Hành] Minh Hoạ Thuật Toán Sắp Xếp Nổi Bọt - Học Java
Thực Hành] Minh Hoạ Thuật Toán Sắp Xếp Nổi Bọt – Học Java
Thuật Toán Sắp Xếp Bubble Sort Minh Họa Code Sử Dụng C++ – Luyện Code
Thuật Toán Sắp Xếp Bubble Sort Minh Họa Code Sử Dụng C++ – Luyện Code
Thuật Toán Sắp Xếp | Chào Mừng Các Bạn Đến Với Blog Của Nhóm G6
Thuật Toán Sắp Xếp | Chào Mừng Các Bạn Đến Với Blog Của Nhóm G6
Giải Bài 4 Sắp Xếp Nổi Bọt | Giải Tin Học 7 Cánh Diều - Tech12H
Giải Bài 4 Sắp Xếp Nổi Bọt | Giải Tin Học 7 Cánh Diều – Tech12H
Theo Em, Vì Sao Thuật Toán Sắp Xếp Này Lại Được Gọi Là Sắp Xếp Nổi Bọt?
Theo Em, Vì Sao Thuật Toán Sắp Xếp Này Lại Được Gọi Là Sắp Xếp Nổi Bọt?
Minh Họa Thuật Toán Sắp Xếp Nổi Bọt - Youtube
Minh Họa Thuật Toán Sắp Xếp Nổi Bọt – Youtube
Hãy Mô Phỏng Thuật Toán Sắp Xếp Nổi Bọt Cho Một Dãy Số Nguyên Tùy Chọn,  Không Ít Hơn 5 Phần Tử.
Hãy Mô Phỏng Thuật Toán Sắp Xếp Nổi Bọt Cho Một Dãy Số Nguyên Tùy Chọn, Không Ít Hơn 5 Phần Tử.
Em Hãy Thực Hiện Thuật Toán Sắp Xếp Nổi Bọt Để Sắp Xếp 5 Số Sau Đây Theo  Thứ Tự Tăng Dần. Hãy Mô Phỏng Các Bước Sắp Xếp Bằng Hình Vẽ
Em Hãy Thực Hiện Thuật Toán Sắp Xếp Nổi Bọt Để Sắp Xếp 5 Số Sau Đây Theo Thứ Tự Tăng Dần. Hãy Mô Phỏng Các Bước Sắp Xếp Bằng Hình Vẽ
Bài 08. Thuật Toán Sắp Xếp Nổi Bọt (Bubble Sort) | Cấu Trúc Dữ Liệu Và Giải  Thuật - Youtube
Bài 08. Thuật Toán Sắp Xếp Nổi Bọt (Bubble Sort) | Cấu Trúc Dữ Liệu Và Giải Thuật – Youtube
Thuật Toán Sắp Xếp Nổi Bọt (Bubble Sort)
Thuật Toán Sắp Xếp Nổi Bọt (Bubble Sort)
Minh Họa Chi Tiết Thuật Toán Sắp Xếp Nổi Bọt Bằng C++
Minh Họa Chi Tiết Thuật Toán Sắp Xếp Nổi Bọt Bằng C++
Java] Bubble Sort: Thuật Toán Sắp Xếp Nổi Bọt
Java] Bubble Sort: Thuật Toán Sắp Xếp Nổi Bọt
Em Hãy Liệt Kê Các Bước Của Thuật Toán Sắp Xếp Nổi Bọt Để Sắp Xếp Các Số
Em Hãy Liệt Kê Các Bước Của Thuật Toán Sắp Xếp Nổi Bọt Để Sắp Xếp Các Số
Python #50: Thuật Toán Sắp Xếp Nổi Bọt Bubble Sort - Youtube
Python #50: Thuật Toán Sắp Xếp Nổi Bọt Bubble Sort – Youtube
Giải Bài 16 Thuật Toán Sắp Xếp | Giải Tin Học 7 Kết Nối Tri Thức - Tech12H
Giải Bài 16 Thuật Toán Sắp Xếp | Giải Tin Học 7 Kết Nối Tri Thức – Tech12H
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
Bài Tập Java - Sắp Xếp Nổi Bọt (Bubble Sort) Trong Java - Viettuts
Bài Tập Java – Sắp Xếp Nổi Bọt (Bubble Sort) Trong Java – Viettuts
Em Hãy Liệt Kê Các Bước Của Thuật Toán Sắp Xếp Nổi Bọt Để Sắp Xếp Các Số 3,  2, 4, 1, 5
Em Hãy Liệt Kê Các Bước Của Thuật Toán Sắp Xếp Nổi Bọt Để Sắp Xếp Các Số 3, 2, 4, 1, 5
Thuật Toán Sắp Xếp Archives - Học Java
Thuật Toán Sắp Xếp Archives – Học Java
Bài 16. Thuật Toán Sắp Xếp - Bumbii
Bài 16. Thuật Toán Sắp Xếp – Bumbii
Thuật Toán Sắp Xếp Nổi Bọt (Bubble Sort)
Thuật Toán Sắp Xếp Nổi Bọt (Bubble Sort)
Bài 48. Thuật Toán Sắp Xếp Chọn (Selection Sort) – Luyện Code
Bài 48. Thuật Toán Sắp Xếp Chọn (Selection Sort) – Luyện Code
Các Thuật Toán Sắp Xếp Với C#: Sắp Xếp Chọn, Chèn, Nổi Bọt, Nhanh | Tự Học  Ict
Các Thuật Toán Sắp Xếp Với C#: Sắp Xếp Chọn, Chèn, Nổi Bọt, Nhanh | Tự Học Ict
Thuật Toán Sắp Xếp Nổi Bọt (Bubble Sort) Trong C / C++
Thuật Toán Sắp Xếp Nổi Bọt (Bubble Sort) Trong C / C++
Hãy Trình Bày Diễn Biến Từng Bước Của Thuật Toán Sắp Xếp Nổi Bọt Áp Dụng  Cho Dãy Số {15, 8, 45, 21, 11} Để Được Dãy Số Tăng Dần.
Hãy Trình Bày Diễn Biến Từng Bước Của Thuật Toán Sắp Xếp Nổi Bọt Áp Dụng Cho Dãy Số {15, 8, 45, 21, 11} Để Được Dãy Số Tăng Dần.
Giải Tin Học 7 Bài 16 Trang 80 Sgk Kết Nối Tri Thức
Giải Tin Học 7 Bài 16 Trang 80 Sgk Kết Nối Tri Thức
Cấu Trúc Dữ Liệu Và Giải Thuật : Bubble Sort - Sắp Xếp Nổi Bọt - Youtube
Cấu Trúc Dữ Liệu Và Giải Thuật : Bubble Sort – Sắp Xếp Nổi Bọt – Youtube
Cấu Trúc Dữ Liệu Và Giải Thuật: Giải Thuật Sắp Xếp Nổi Bọt (Bubble Sort) -  Writes - Dạy Nhau Học
Cấu Trúc Dữ Liệu Và Giải Thuật: Giải Thuật Sắp Xếp Nổi Bọt (Bubble Sort) – Writes – Dạy Nhau Học
Bài 16. Thuật Toán Sắp Xếp Trang 55, 56 Sbt Tin Học 7 Kết Nối Tri Thức Với  Cuộc Sống | Sbt Tin Học 7 - Kết Nối Tri Thức
Bài 16. Thuật Toán Sắp Xếp Trang 55, 56 Sbt Tin Học 7 Kết Nối Tri Thức Với Cuộc Sống | Sbt Tin Học 7 – Kết Nối Tri Thức
Trong Thuật Toán Sắp Xếp Nổi Bọt Thì Dấu Hiệu Để Biết Dãy Chưa Sắp Xếp Xong  Là Gì
Trong Thuật Toán Sắp Xếp Nổi Bọt Thì Dấu Hiệu Để Biết Dãy Chưa Sắp Xếp Xong Là Gì
Giáo Án Tin Học 7 Cánh Diều Bài 4: Sắp Xếp Nổi Bọt (1 Tiết) | Giáo Án Tin  Học 7 Cánh Diều | Kenhgiaovien.Com
Giáo Án Tin Học 7 Cánh Diều Bài 4: Sắp Xếp Nổi Bọt (1 Tiết) | Giáo Án Tin Học 7 Cánh Diều | Kenhgiaovien.Com

See more here: kientrucannam.vn

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *