CTDL và giải thuật - Giải thuật shell Sort.

Nhập vào số nguyên dương n, tiếp theo là n số nguyên của dãy số a.
Hãy sắp xếp dãy số a thành dãy không giảm (số sau không bé hơn số trước) và in dãy đó ra màn hình, sau mỗi phần tử có đúng một khoảng trắng.

Ví dụ:

  • Test mẫu 1:
     
    Input Output

    5
    1 3 2 5 2

    1 2 2 3 5

    Với a = [1, 3, 2, 5, 2] thì kết quả mong muốn là:
    "1 2 2 3 5 ".
     
  • Test mẫu 2:
     
    Input Output

    4
    3 2 1 4

    1 2 3 4

    Với a = [3, 2, 1, 4] thì kết quả mong muốn là:
    "1 2 3 4 ".

Lý thuyết.

Giới thiệu giải thuật shell Sort.

Shell Sort là một giải thuật sắp xếp mang lại hiệu quả cao dựa trên giải thuật sắp xếp chèn (Insertion Sort). Giải thuật này tránh các trường hợp phải tráo đổi vị trí của hai phần tử xa nhau trong giải thuật sắp xếp chọn (nếu như phần tử nhỏ hơn ở vị trí bên phải khá xa so với phần tử lớn hơn bên trái).

Đầu tiên, giải thuật này sử dụng giải thuật sắp xếp chọn trên các phần tử có khoảng cách xa nhau, sau đó sắp xếp các phần tử có khoảng cách hẹp hơn. Khoảng cách này còn được gọi là khoảng (interval).

interval sẽ nhận giá trị lần lượt là n/2, n/4, n/8 cho đến khi interval = 1.

Giải thuật này khá hiệu quả với các tập dữ liệu có kích cỡ trung bình khi mà độ phức tạp trường hợp xấu nhất và trường hợp trung bình là O(n), với n là số phần tử.

Cách shell Sort hoạt động:

Ví dụ sắp xết dãy a = [9, 1, 3, 7, 8, 4, 2, 6, 5] thành dãy không giảm.

Với interval = 9/2 = 4, ta sẽ chia dãy thành các dãy con với các số cách nhau một khoảng là interval[9, 8, 5], [1, 4], [3, 2] và [7, 6].

Sắp xếp những dãy con này theo cách sắp xếp chèn (Insertion Sort).

Sau khi sắp xếp các dãy con dãy sẽ thành.

 

Với interval = 9/4 = 2, ta sẽ chia dãy thành các dãy con với các số cách nhau một khoảng là interval[9, 8, 5], [1, 4], [3, 2] và [7, 6].

Sau khi sắp xếp các dãy con dãy sẽ thành.

Với interval = 9/4 = 1, lúc này interval = 1 ta áp dụng sắp xếp chèn với cả dãy a:

Dãy sau khi sắp xếp là:

Code mẫu C++:

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

 

Hướng dẫn bài tập.

Code mẫu:

Ngôn ngữ C++:

#include<iostream>

using namespace std;

void printArray(int a[], int n){
    for (int i = 0; i < n; i++){
    	cout << a[i] << " ";
	}
	cout << endl;
}
void shellSort(int a[], int n){
	int interval, i, j, temp;
	for(interval = n/2; interval > 0; interval /= 2){
		for(i = interval; i < n; i++){
			temp = a[i];
			for(j = i; j >= interval && a[j - interval] > temp; j -= interval){
				a[j] = a[j - interval];				
			}
			a[j] = temp;
		}
    }
}
int a[100001];
int main()
{
	int n;
	cin >> n;
	for(int i = 0; i < n; i++){
		cin >> a[i];		
	}
	shellSort(a, n);
	printArray(a, n);
    return 0;
}