Cấu trúc dữ liệu vào giải thuật - 1 số giải thuật sắp xếp

1. Giải thuật sắp xếp trong cấu trúc dữ liệu & giải thuật

Sắp xếp là sắp xếp dữ liệu theo một định dạng cụ thể. Trong khoa học máy tính, giải thuật sắp xếp xác định cách để sắp xếp dữ liệu theo một thứ tự nào đó.

Sắp xếp theo thứ tự ở đây là sắp xếp theo thứ tự dạng số hoặc thứ tự dạng chữ cái như trong từ điển.

Tính quan trọng của việc sắp xếp 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 sắp xếp theo một thứ tự nào đó (tăng hoặc giảm). Sắp xếp cũng được sử dụng để biểu diễn dữ liệu trong một định dạng dễ đọc hơn.

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

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

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

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, 10 nhỏ hơn 35 nên ta lại đổi vị trí 2 giá trị này cho nhau

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

Chúng ta lặp lại từ đầu quá trình so sánh như vậy, sau lần lặp thứ hai, mảng sẽ trông giống như

Lần thứ 3

lần thứ 4

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

2.2 Code

func sortWithhBubbleSort(_ array: [Int]) -> [Int]{
    var insideArray = array
    for _ in 0..<insideArray.count{
        for jIndex in 0..<(insideArray.count-1){
            if insideArray[jIndex]>insideArray[jIndex+1]{
                let value = insideArray[jIndex+1]
                insideArray[jIndex+1] = insideArray[jIndex]
                insideArray[jIndex] = value
            }
        }
    }
    return insideArray
}

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

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

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

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

Phần tử được chèn vào vị trí thích hợp sao cho vẫn đảm bảo rằng danh sách con đó vẫn sắp theo thứ tự.

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

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 độ 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ử.

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

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

Chúng ta sẽ so sánh 2 phần tử đầu tiên của mảng là 14 và 33, 2 phần tử này đã được sắp xếp nên chúng ta đưa 14 vào mảng con đã qua sắp xếp, tiếp tục so sánh đến 2 phần tử 33 và 27

ở đây ta thấy 33 ko nằm đúng vị trí, chúng ta tiến hành tráo đổi vị trí 33 và 27

đồng thời thêm phần tử 27 vào danh sách con đã sắp xếp, trong danh sách con này hiện có 2 phần tử 14, 27 2 phần tử này cũng đã nằm đúng vị trí nên không cần so sánh tiếp Lại tiếp tục so sánh 33 và 10

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

Việc tráo đổi dẫn đến 27 và 10 không theo thứ tự.

Vì thế chúng ta cũng tráo đổi chúng.

Chúng ta lại thấy rằng 14 và 10 không theo thứ tự.

Và 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 chúng ta có 4 phần tử.

Cứ tiếp tục như vậy cho đến khi tất cả các phần từ trong mảng được sắp xếp thì thuật toán kết thúc.

3.2 Code

func sortWithhinsertionSort(_ array: [Int]) -> [Int] {
    var insideArray = array

    for i in 0..<array.count {
        let value = array[i]
        var j = i - 1
        while j >= 0 {
            if array[j] > value{
                insideArray[j+1] = array[j]
            } else {
                break
            }
            j -= 1
        }
        insideArray[j+1] = value
    }

    return insideArray
}

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

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

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

Giải thuật này không phù hợp với 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à O(n2) với n là số phần tử.

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

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

Vị trí đầu tiên có giá trị 14, chúng ta tìm toàn bộ danh sách và thấy rằng 10 là giá trị nhỏ nhất.

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

Chúng ta thấy rằng 14 là giá trị nhỏ nhất thứ hai trong danh sách và nó nên xuất hiện ở vị trí thứ hai. Chúng ta tráo đổi hai giá trị này.

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

4.2 Code

func sortWithSelectionSort(_ array: [Int]) -> [Int] {
    guard array.count > 1 else { return array }  // 1
    
    var a = array                    // 2
    
    for x in 0 ..< a.count - 1 {     // 3
        
        var lowest = x
        for y in x + 1 ..< a.count {   // 4
            if a[y] < a[lowest] {
                lowest = y
            }
        }
        
        if x != lowest {               // 5
            a.swapAt(x, lowest)
        }
    }
    return a
}