Rate this post

Thuật toán Shell Sort là một thuật toán sắp xếp dựa trên Insertion Sort với sự nâng cao để tăng tốc độ sắp xếp. Nó sử dụng một số bước sắp xếp nhỏ hơn với các khoảng cách giữa các phần tử để trải qua một số vòng lặp, sau đó giảm khoảng cách đến 0 để hoàn thành việc sắp xếp.

Các bài viết liên quan:

Ví dụ Shell Sort trong c++

Đây là một ví dụ về thuật toán Shell Sort trong C++:

#include <iostream>

void shellSort(int arr[], int n) {
  for (int gap = n / 2; gap > 0; gap /= 2) {
    for (int i = gap; i < n; i++) {
      int temp = arr[i];
      int j;
      for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
        arr[j] = arr[j - gap];
      }
      arr[j] = temp;
    }
  }
}

int main() {
  int arr[] = {12, 34, 54, 2, 3};
  int n = sizeof(arr) / sizeof(arr[0]);

  std::cout << "Mảng trước khi sắp xếp: \n";
  for (int i = 0; i < n; i++) {
    std::cout << arr[i] << " ";
  }

  shellSort(arr, n);

  std::cout << "\nMảng sau khi sắp xếp: \n";
  for (int i = 0; i < n; i++) {
    std::cout << arr[i] << " ";
  }
  return 0;
}

Kết quả:

Mảng trước khi sắp xếp: 
12 34 54 2 3 
Mảng sau khi sắp xếp: 
2 3 12 34 54

Giải thích đoạn code trên

Đoạn code trên giải thích thuật toán Shell Sort trong C++.

Định nghĩa hàm shellSort: hàm này sẽ nhận một mảng arr và độ dài của mảng n làm tham số.
Vòng lặp for đầu tiên: vòng lặp này sẽ tạo ra các bước sắp xếp với các khoảng cách giữa các phần tử. Khoảng cách ban đầu được tính bằng n/2 và sau mỗi lần lặp sẽ giảm đến nửa.
Vòng lặp for thứ hai: vòng lặp này sẽ chạy từ gap đến n và tìm vị trí phù hợp để chèn phần tử vào.
Vòng lặp for thứ ba: vòng lặp này sẽ chạy từ j đến gap và so sánh với phần tử trước đó để tìm vị trí phù hợp để chèn phần tử. Nếu phần tử trước đó lớn hơn phần tử hiện tại, nó sẽ được di chuyển đến vị trí phù hợp và vòng lặp sẽ tiếp tục.
Cuối cùng, hàm shellSort sẽ kết thúc khi khoảng cách giữa các phần tử đạt 0.
Hàm main: hàm này sẽ tạo ra một mảng arr và gọi hàm `shellSort

Độ phức tạp thuật toán Shell Sort

Độ phức tạp thời gian của thuật toán Shell Sort là O(n^(3/2)) trung bình và O(n * log^2 n) tối đa. Nó phụ thuộc vào khoảng cách giữa các phần tử được sắp xếp và cách chọn khoảng cách đó. Tuy nhiên, trong một số trường hợp, Shell Sort có thể chạy nhanh hơn các thuật toán sắp xếp khác như Insertion Sort hoặc Bubble Sort.

Algorithm, C/C++

Thuật toán Shell Sort là gì ?

Ví dụ Shell Sort trong c++

Độ phức tạp thuật toán Shell Sort

Trả lời Hủy