Shell Sort

Trong hướng dẫn này, bạn sẽ tìm hiểu cách thức hoạt động của shell sort. Ngoài ra, bạn sẽ tìm thấy các ví dụ làm việc của loại trình bao trong C, C ++, Java và Python.

Shell sort là một thuật toán sắp xếp đầu tiên các phần tử cách xa nhau và liên tiếp giảm khoảng thời gian giữa các phần tử được sắp xếp. Nó là một phiên bản tổng quát của sắp xếp chèn.

Trong loại trình bao, các phần tử tại một khoảng thời gian cụ thể được sắp xếp. Khoảng cách giữa các phần tử được giảm dần dựa trên trình tự được sử dụng. Hiệu suất của loại trình bao phụ thuộc vào loại trình tự được sử dụng cho một mảng đầu vào nhất định.

Một số trình tự tối ưu được sử dụng là:

  • Trình tự ban đầu của Shell: N/2 , N/4 ,… , 1
  • Gia số của Knuth: 1, 4, 13,… , (3k - 1) / 2
  • Gia số của Sedgewick: 1, 8, 23, 77, 281, 1073, 4193, 16577… 4j+1+ 3·2j+ 1
  • Gia số của Hibbard: 1, 3, 7, 15, 31, 63, 127, 255, 511…
  • Gia số Papernov & Stasevich: 1, 3, 5, 9, 17, 33, 65,…
  • Pratt: 1, 2, 3, 4, 6, 9, 8, 12, 18, 27, 16, 24, 36, 54, 81… .

Shell Sort hoạt động như thế nào?

  1. Giả sử, chúng ta cần sắp xếp mảng sau. Mảng ban đầu
  2. Chúng tôi đang sử dụng trình tự ban đầu của trình bao (N/2, N/4,… 1) làm các khoảng trong thuật toán của chúng tôi.
    Trong vòng lặp đầu tiên, nếu kích thước mảng là N = 8sau đó, các phần tử nằm trong khoảng thời gian N/2 = 4được so sánh và hoán đổi nếu chúng không theo thứ tự.
    1. Phần tử thứ 0 được so sánh với phần tử thứ 4.
    2. Nếu phần tử thứ 0 lớn hơn phần tử thứ 4 thì phần tử thứ 4 đầu tiên được lưu trữ trong tempbiến và 0thphần tử (tức là phần tử lớn hơn) được lưu trữ ở 4thvị trí và phần tử được lưu trữ trong tempđược lưu trữ ở 0thvị trí. Sắp xếp lại các phần tử ở khoảng thời gian n / 2
      Quá trình này tiếp tục cho tất cả các phần tử còn lại. Sắp xếp lại tất cả các phần tử ở khoảng thời gian n / 2
  3. Trong vòng lặp thứ hai, một khoảng thời gian N/4 = 8/4 = 2được lấy và một lần nữa các phần tử nằm trong khoảng thời gian này được sắp xếp. Sắp xếp lại các phần tử ở khoảng thời gian n / 4
    Bạn có thể nhầm lẫn ở điểm này. Tất cả các phần tử trong mảng nằm ở khoảng thời gian hiện tại được so sánh.
    Các yếu tố ở 2ndvị trí thứ 4 và được so sánh với nhau. Các yếu tố ở 0thvị trí thứ 2 và vị trí cũng được so sánh. Tất cả các phần tử trong mảng nằm ở khoảng thời gian hiện tại được so sánh.
  4. Quá trình tương tự diễn ra đối với các phần tử còn lại. Sắp xếp lại tất cả các phần tử ở khoảng thời gian n / 4
  5. Cuối cùng, khi khoảng là N/8 = 8/8 =1thì các phần tử của mảng nằm ở khoảng 1 được sắp xếp. Mảng bây giờ đã được sắp xếp hoàn toàn. Sắp xếp lại các phần tử ở khoảng thời gian n / 8

Thuật toán sắp xếp Shell

 shellSort (mảng, kích thước) cho khoảng i <- size / 2n xuống 1 cho mỗi khoảng "i" trong mảng sắp xếp tất cả các phần tử ở khoảng "i" end shellSort

Ví dụ về Python, Java và C / C ++

Python Java C C ++ 
# Shell sort in python def shellSort(array, n): # Rearrange elements at each n/2, n/4, n/8,… intervals interval = n // 2 while interval> 0: for i in range(interval, n): temp = array(i) j = i while j>= interval and array(j - interval)> temp: array(j) = array(j - interval) j -= interval array(j) = temp interval //= 2 data = (9, 8, 3, 7, 5, 6, 4, 1) size = len(data) shellSort(data, size) print('Sorted Array in Ascending Order:') print(data)
// Shell sort in Java programming import java.util.Arrays; // Shell sort class ShellSort ( // Rearrange elements at each n/2, n/4, n/8,… intervals void shellSort(int array(), int n) ( for (int interval = n / 2; interval> 0; interval /= 2) ( for (int i = interval; i  = interval && array(j - interval)> temp; j -= interval) ( array(j) = array(j - interval); ) array(j) = temp; ) ) ) // Driver code public static void main(String args()) ( int() data = ( 9, 8, 3, 7, 5, 6, 4, 1 ); int size = data.length; ShellSort ss = new ShellSort(); ss.shellSort(data, size); System.out.println("Sorted Array in Ascending Order: "); System.out.println(Arrays.toString(data)); ) ) 
// Shell Sort in C programming #include // Shell sort void shellSort(int array(), int n) ( // Rearrange elements at each n/2, n/4, n/8,… intervals for (int interval = n / 2; interval> 0; interval /= 2) ( for (int i = interval; i  = interval && array(j - interval)> temp; j -= interval) ( array(j) = array(j - interval); ) array(j) = temp; ) ) ) // Print an array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) ( printf("%d ", array(i)); ) printf(""); ) // Driver code int main() ( int data() = (9, 8, 3, 7, 5, 6, 4, 1); int size = sizeof(data) / sizeof(data(0)); shellSort(data, size); printf("Sorted array: "); printArray(data, size); ) 
// Shell Sort in C++ programming #include using namespace std; // Shell sort void shellSort(int array(), int n) ( // Rearrange elements at each n/2, n/4, n/8,… intervals for (int interval = n / 2; interval> 0; interval /= 2) ( for (int i = interval; i  = interval && array(j - interval)> temp; j -= interval) ( array(j) = array(j - interval); ) array(j) = temp; ) ) ) // Print an array void printArray(int array(), int size) ( int i; for (i = 0; i < size; i++) cout << array(i) << " "; cout << endl; ) // Driver code int main() ( int data() = (9, 8, 3, 7, 5, 6, 4, 1); int size = sizeof(data) / sizeof(data(0)); shellSort(data, size); cout << "Sorted array: "; printArray(data, size); )

Phức tạp

Shell sort là một thuật toán sắp xếp không ổn định vì thuật toán này không kiểm tra các phần tử nằm giữa các khoảng.

Thời gian phức tạp

  • Độ phức tạp của trường hợp xấu nhất : nhỏ hơn hoặc bằng Độ phức tạp của trường hợp tồi tệ nhất đối với loại trình bao luôn nhỏ hơn hoặc bằng . Theo Định lý Poonen, độ phức tạp trong trường hợp xấu nhất đối với loại trình bao là hoặc hoặc hoặc cái gì đó ở giữa.O(n2)
    O(n2)
    Θ(Nlog N)2/(log log N)2)Θ(Nlog N)2/log log N)Θ(N(log N)2)
  • Độ phức tạp của trường hợp tốt nhất : O(n*log n)
    Khi mảng đã được sắp xếp, tổng số lần so sánh cho mỗi khoảng (hoặc khoảng tăng) bằng kích thước của mảng.
  • Độ phức tạp của trường hợp trung bình : O(n*log n)
    Nó ở xung quanh .O(n1.25)

Độ phức tạp phụ thuộc vào khoảng thời gian được chọn. Các độ phức tạp trên khác nhau đối với các trình tự gia tăng khác nhau được chọn. Trình tự tăng tốt nhất chưa được biết.

Không gian phức tạp:

Sự phức tạp về không gian đối với loại trình bao là O(1).

Ứng dụng phân loại Shell

Shell sort được sử dụng khi:

  • gọi một ngăn xếp là chi phí. thư viện uClibc sử dụng cách sắp xếp này.
  • đệ quy vượt quá một giới hạn. máy nén bzip2 sử dụng nó.
  • Sắp xếp chèn không hoạt động tốt khi các phần tử gần nhau ở xa nhau. Sắp xếp Shell giúp giảm khoảng cách giữa các phần tử gần nhau. Do đó, sẽ có ít số lần hoán đổi được thực hiện hơn.

thú vị bài viết...