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

By Admin 24/03/2024 0

Bách khoa toàn thư cởi Wikipedia

Sắp xếp nổi bọt
Mô phỏng bố trí nổi bọt
Phân loạiGiải thuật chuẩn bị xếp
Cấu trúc dữ liệuNgẫu nhiên
Hiệu suất tình huống tệ nhấtTrung bình
Độ phức tạp không khí tình huống tệ nhấtKhông tốn tăng vùng nhớ
Tối ưuKhông
Một ví dụ về bố trí nổi lớp bọt. Bắt đầu từ vựng trí thứ nhất của list (bên trái), đối chiếu những cặp số cùng nhau, còn nếu không đích thị trật tự nhỏ-lớn thì hòn đảo địa điểm. Sau khi chạy cho tới cuối list, nối tiếp chạy lại từ vựng trí đầu list cho tới khi triển khai xong đối chiếu và hòn đảo địa điểm.
Sắp xếp nổi lớp bọt màu sắc đang được chỉnh sửa
Sắp xếp nổi lớp bọt màu sắc đang được chỉnh sửa

Sắp xếp nổi bọt (tiếng Anh: bubble sort) là 1 trong thuật toán bố trí đơn giản và giản dị, với thao tác cơ phiên bản là đối chiếu nhị thành phần kề nhau, nếu như bọn chúng ko đứng đích thị trật tự thì thay đổi điểm (swap). cũng có thể tổ chức kể từ bên trên xuống (bên trái ngược sang) hoặc kể từ bên dưới lên (bên cần sang). Sắp xếp nổi bọt còn mang tên là sắp xếp vày đối chiếu trực tiếp. Nó dùng luật lệ đối chiếu những thành phần nên là 1 trong giải thuật bố trí loại đối chiếu.

Bạn đang xem: thuật toán sắp xếp nổi bọt

Giải thuật[sửa | sửa mã nguồn]

Sắp xếp kể từ bên trên xuống[sửa | sửa mã nguồn]

Giả sử mặt hàng cần thiết bố trí với n thành phần. Khi tổ chức kể từ bên trên xuống, tao đối chiếu nhị thành phần đầu, nếu như thành phần đứng trước to hơn thành phần đứng sau thì thay đổi điểm bọn chúng lẫn nhau. Tiếp tục thực hiện vì vậy với cặp thành phần loại nhị và loại thân phụ và nối tiếp cho tới cuối tập trung tài liệu, tức là đối chiếu (và thay đổi điểm nếu như cần) thành phần loại n-1 với thành phần loại n. Sau đoạn này thành phần ở đầu cuối đó là thành phần lớn số 1 của mặt hàng.

Sau tê liệt, quay trở lại đối chiếu (và thay đổi chố nếu như cần) nhị thành phần đầu cho tới khi bắt gặp thành phần loại n-2....

Ghi chú: Nếu nhập một phiên duyệt, ko cần thay đổi điểm bất kể cặp thành phần này thì list và đã được bố trí hoàn thành.

Xem thêm: năng lượng không tái tạo

Sắp xếp kể từ bên dưới lên[sửa | sửa mã nguồn]

Sắp xếp kể từ bên dưới lên đối chiếu (và thay đổi điểm nếu như cần) chính thức từ các việc đối chiếu cặp thành phần loại n-1 và n. Tiếp theo đòi là đối chiếu cặp thành phần loại n-2 và n-1,... cho tới khi đối chiếu và thay đổi điểm cặp thành phần loại nhất và loại nhị. Sau đoạn này thành phần nhỏ nhất và đã được nổi lên địa điểm bên trên nằm trong (nó tương tự hình hình ảnh của những "bọt" khí nhẹ nhõm rộng lớn được nổi lên trên). Tiếp theo đòi tổ chức với những thành phần kể từ thứ hai cho tới loại nm.

Mã giả[sửa | sửa mã nguồn]

Sắp xếp kể từ bên 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 bọn chúng ko đích thị loại tự
        swap(L[j], L[j + 1]) //đổi điểm bọn chúng mang đến nhau
      endif
    endfor
   endfor
endprocedure

Sắp xếp kể từ bên 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 bọn chúng ko đích thị loại tự
        swap(L[j], L[j + 1]) //đổi điểm bọn chúng mang đến nhau
      endif
    endfor
   endfor
endprocedure

Giảm giảm sút vòng duyệt[sửa | sửa mã nguồn]

Nếu nhập một phiên duyệt này tê liệt với cùng một i cố định và thắt chặt khi vòng lặp j kết thúc giục tuy nhiên không nhất thiết phải thay đổi điểm cặp thành phần này, tức là từng cặp thành phần kề nhau đang được đứng đích thị trật tự thì mặt hàng và đã được bố trí và ko cần thiết tổ chức vòng lặp tiếp sau. Do tê liệt hoàn toàn có thể người sử dụng một cờ nhằm trấn áp việc này. Ta với một quãng mã fake của thuật toán nổi lớp bọt như sau:

Xem thêm: bác hồ bao nhiêu tuổi

procedure bubble_sort3(list L, number n)
  i:= n
  while i > 1 do
    has_swapped:= 0 //khởi tạo ra lại độ quý hiếm cờ
    for number j from 1 to (i - 1)
      if L[j] > L[j + 1] //nếu bọn chúng ko đích thị loại tự
        swap(L[j], L[j + 1]) //đổi điểm bọn chúng mang đến nhau
        has_swapped:= 1 //có thay đổi điểm tối thiểu một phiên, list ko bố trí xong
      endif
    endfor  
    if has_swapped = 0 //nếu không tồn tại phiên thay đổi nơi nào, list đang được bố trí xong
      exit
     else //nếu với tối thiểu một phiên thay đổi điểm, list ko bố trí xong
      i = i - 1
    endif
  enddo
endprocedure

Ghi chú: Cũng hoàn toàn có thể ko nhớ dùng cho tới phát triển thành i, khi tê liệt từng phiên đánh giá đều cần duyệt từ trên đầu cho tới cuối mặt hàng.

Thời gian dối tính[sửa | sửa mã nguồn]

Với từng i = 1,2,..,n-1 tao cần thiết i luật lệ đối chiếu. Do tê liệt số tối đa những phiên đối chiếu và thay đổi điểm nhập giải thuật là

Do tê liệt chừng phức tạp của giải thuật cỡ O().

Mã thiệt ví dụ[sửa | sửa mã nguồn]

Viết vày 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 đồ sộ n - 1 do
            for j:= i + 1 đồ sộ 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 đồ sộ n do
        readln(a[i]);
        
    BubbleSort;
    
    for i:= 1 đồ sộ n do
        write(a[i], ' ');
        
    readln
END.

Viết vày Java[sửa | sửa mã nguồn]

    private static void bubbleSort(int[] unsortedArray, int length) {
        int temp, counter, index;
        
        for(counter=0; counter<length-1; counter++) { //Loop once for each element in the array.
            for(index=0; index<length-1-counter; index++) { //Once for each element, minus the counter.
                if(unsortedArray[index] > 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 vày C++[sửa | sửa mã nguồn]

#include <bits/stdc++.h> 
using namespace std; 
long long a[N], n;//Thay N là số thành phần nhập mảng 

template<class T,class Cmp = less<T> >
void bubblesort(T *L,T *R,Cmp ss= less<T>())  //sap *L,*(L+1)...*(R-1)
{
    for(T *i=L;i<R;i++)
        for(T *j=R-1;j>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<<a[i]<<" "; 
}

Viết vày 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]."<br>";
}

Viết vày Python[sửa | sửa mã nguồn]

list = []
list_final = []
num = int(input("how many number you want đồ sộ 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)

Xem thêm[sửa | sửa mã nguồn]

  • Sắp xếp chèn
  • Sắp xếp chọn
  • Sắp xếp vun đống
  • Sắp xếp nhanh
  • Sắp xếp trộn

Tham khảo[sửa | sửa mã nguồn]