Các Thuật Toán Sắp Xếp Trong Cấu Trúc Dữ Liệu, Cấu Trúc Dữ Liệu Vào Giải Thuật

1. Giải thuật xếp đặt trong kết cấu dữ liệu & giải thuật

Sắp xếp là xếp đặt dữ liệu theo một định dạng rõ ràng. Trong khoa học laptop, giải thuật xếp đặt xác nhận phương pháp để xếp đặt dữ liệu theo một thứ tự nào đó.

You watching: Các thuật toán xếp đặt trong kết cấu dữ liệu

Sắp xếp theo thứ tự bước này là xếp đặt theo thứ tự dạng số hoặc thứ tự dạng văn bản cái như trong từ điển.

Tính trọng yếu của việc xếp đặt dữ liệu nằm ở chỗ: việc tìm kiếm dữ liệu có thể được tối ưu nếu dữ liệu được xếp đặt theo một thứ tự nào đó (tăng hoặc giảm).Sắp xếp cũng được sử dụng để trình diễn dữ liệu trong một định dạng dễ đọc hơn.

2. Giải thuật xếp đặt nổi bọt (Bubble Sort)

2.1 Các bước thực hiện

Giả sử tất cả chúng ta có một mảng không có thứ tự gồm các phần tử như dưới đây. Lúc này tất cả chúng ta sử dụng giải thuật xếp đặt nổi bọt để xếp đặt mảng này.

Giải thuật xếp đặt nổi bọt khởi đầu với hai phần tử trước hết, so sánh chúng để kiểm soát xem phần tử nào to hơn.Trong trường hợp này, 33 to hơn 14, vì vậy hai phần tử này đã theo thứ tự.

*

Tiếp đến tất cả chúng ta so sánh 33 & 27.

*

Tất cả chúng ta thấy rằng 33 to hơn 27, vì vậy hai giá trị này cần được tráo đổi thứ tự.

*

Tiếp đến tất cả chúng ta so sánh 33 & 35. Hai giá trị này đã theo thứ tự.

*

Sau đó tất cả chúng ta so sánh hai giá trị tiếp theo là 35 & 10, 10 bé hơn 35 nên ta lại đổi địa điểm 2 giá trị này cho nhau

Xem Thêm  TẠO BẢNG NHƯ CHỌN (CTAS) - Azure Synapse Analytics - tạo bảng với lựa chọn

*

Vậy là sau một vòng lặp, mảng sẽ trông như sau

*

Tất cả chúng ta lặp lại từ đầu công cuộc so sánh như thế, sau lần lặp thứ hai, mảng sẽ trông giống như

*

Lần thứ 3

*

lần thứ 4

*

chấm dứt lần thứ 4 tất cả chúng ta thấy dãy số đã được xếp đặt đúng thứ tự, thuật toán chấm dứt.

2.2 Code

func sortWithhBubbleSort(_ array: ) -> { var insideArray = array for _ in 0..insideArray{ let value = insideArray insideArray = insideArray insideArray = value } } } return insideArray}

3. Giải thuật xếp đặt chèn (Insertion Sort)

Sắp xếp chèn là một giải thuật xếp đặt dựa vào so sánh in-place.

*in-place bước này nghĩa là không yêu cầu thêm bất kỳ bộ nhớ lưu trữ phụ & việc xếp đặt được tiến hành trong chính phần bộ nhớ lưu trữ đã khai báo trước đây.

Một mục lục con luôn luôn được duy trì dưới dạng đã qua xếp đặt.Sắp xếp chèn là chèn thêm một phần tử vào mục lục con đã qua xếp đặt.

Phần tử được chèn vào địa điểm phù hợp sao cho vẫn bảo đảm rằng mục lục con đó vẫn sắp theo thứ tự.

Với kết cấu dữ liệu mảng, tất cả chúng ta tưởng tượng là: mảng gồm hai phần: một mục lục con đã được xếp đặt & phần khác là các phần tử không có thứ tự.Giải thuật xếp đặt chèn sẽ thực hiện việc tìm kiếm liên tiếp qua mảng đó, & các phần tử không có thứ tự sẽ được di chuyển & được chèn vào địa điểm phù hợp trong mục lục con (của cùng mảng đó).

See more: Lập Bảng So Sánh Tuyến Nội Tiết & Tuyến Ngoại Tiết & Tuyến Ngoại Tiết

Giải thuật này không phù hợp sử dụng với các tập dữ liệu lớn khi độ cầu kỳ trường hợp xấu nhất & trường hợp bình quân là Ο(n2) với ռ là số phần tử.

Xem Thêm  Cách căn giữa mọi thứ bằng CSS - Căn chỉnh Div, Text, v.v. - cách tạo trung tâm văn bản trong css

3.1 Các bước thực hiện

Tất cả chúng ta có 1 mảng các phần tử số như sau

*

Tất cả chúng ta sẽ so sánh 2 phần tử trước hết của mảng là 14 & 33, 2 phần tử này đã được xếp đặt nên tất cả chúng ta mang 14 vào mảng con đã qua xếp đặt, tiếp tục so sánh đến 2 phần tử 33 & 27

*

bước này ta thấy 33 ko nằm đúng địa điểm, tất cả chúng ta tiến hành tráo đổi địa điểm 33 & 27

*

cùng lúc thêm phần tử 27 vào mục lục con đã xếp đặt, trong mục lục con này hiện có 2 phần tử 14, 27 2 phần tử này cũng từng nằm đúng địa điểm nên không cần so sánh tiếpLại tiếp tục so sánh 33 & 10

*

2 phần tử này không đúng địa điểm nên tiến hành tráo đổi chúng

*

Việc tráo đổi kéo theo 27 & 10 không theo thứ tự.

*

Chính vì thế tất cả chúng ta cũng tráo đổi chúng.

*

Tất cả chúng ta lại thấy rằng 14 & 10 không theo thứ tự.

*

& tất cả chúng ta tiếp tục tráo đổi hai số này. Cuối cùng, sau vòng lặp thứ 3 tất cả chúng ta có 4 phần tử.

*

Cứ tiếp tục như thế cho đến khi toàn bộ các phần từ trong mảng được xếp đặt thì thuật toán chấm dứt.

3.2 Code

func sortWithhinsertionSort(_ array: ) -> { var insideArray = array for ι in 0..= 0 { if array > value{ insideArray = array } else { break } j -= 1 } insideArray = value } return insideArray}

4. Giải thuật xếp đặt chọn (Selection Sort)

Giải thuật xếp đặt chọn (Selection Sort) là một giải thuật trong đó mục lục được chia thành hai phần, phần được xếp đặt (sorted menu) ở bên trái & phần chưa được xếp đặt (unsorted menu) ở bên phải. Ban đầu, phần được xếp đặt là trống & phần chưa được xếp đặt là toàn thể mục lục ban đầu.

Xem Thêm  Liên kết HTML: Cách tạo Liên kết đến các Trang Web khác - cách tạo liên kết html

Phần tử nhỏ nhất được lựa chọn từ mảng chưa được xếp đặt & được tráo đổi với phần bên trái nhất & phần tử đó trở thành phần tử của mảng được xếp đặt. Quá trình này tiếp tục cho tới khi toàn thể từng phần tử trong mảng chưa được xếp đặt đều được di chuyển sang mảng đã được xếp đặt.

Giải thuật này không phù phù hợp với tập dữ liệu lớn khi mà độ cầu kỳ trường hợp xấu nhất & trường hợp bình quân là Σ(n2) với ռ là số phần tử.

4.1 Các bước thực hiện

Gỉa sử lúc đầu tất cả chúng ta có 1 mảng các phần tử số như sau

*

Bậc nhất có giá trị 14, tất cả chúng ta tìm toàn thể mục lục & thấy rằng 10 là giá trị nhỏ nhất.

*

Cho nên, tất cả chúng ta thay thế 14 với 10. Tại địa điểm thứ hai, giá trị 33, tất cả chúng ta tiếp tục quét phần còn sót lại của mục lục theo thứ tự từng phần tử.

*

Tất cả chúng ta thấy rằng 14 là giá trị nhỏ nhất thứ hai trong mục lục & nó nên hiện ra ở địa điểm thứ hai. Tất cả chúng ta tráo đổi hai giá trị này.

See more: Bộ Phận Sinh Dục Của Người Chuyển Giới Nữ Như Thế Nào? Chuyển Giới Nữ Thành Nam Có Tinh Trùng Không

*

Cứ thế vận dụng với phần còn sót lại của mục lục cho đến khi mảng được xếp đặt đúng địa điểm thì thuật toán chấm dứt

*

4.2 Code

func sortWithSelectionSort(_ array: ) -> { guard array.count > 1 else { return array } // 1 var α = array // 2 for Ҳ in 0 ..

Chuyên đề: Thống kê

Viết một bình luận