#include <stdlib.h>
#include <stdio.h>
void ShellSort701 (int array[], int size) // * ?k = (b?k?1)/2 ?0 = N
{
int step, i, j, tmp;
// Выбор шага
step = 701;
for (i = step; i < size; i++)
// Перестановка элементов внутри подсписка, пока i-тый не будет отсортирован
for (j = i - step; j >= 0 && array[j] > array[j + step]; j -= step)
{
tmp = array[j];
array[j] = array[j + step];
array[j + step] = tmp;
}
}
void ShellSort301 (int array[], int size) // * ?k = (b?k?1)/2 ?0 = N
{
int step, i, j, tmp;
// Выбор шага
step = 301;
for (i = step; i < size; i++)
// Перестановка элементов внутри подсписка, пока i-тый не будет отсортирован
for (j = i - step; j >= 0 && array[j] > array[j + step]; j -= step)
{
tmp = array[j];
array[j] = array[j + step];
array[j + step] = tmp;
}
}
void ShellSort132 (int array[], int size) // * ?k = (b?k?1)/2 ?0 = N
{
int step, i, j, tmp;
// Выбор шага
step = 132;
for (i = step; i < size; i++)
// Перестановка элементов внутри подсписка, пока i-тый не будет отсортирован
for (j = i - step; j >= 0 && array[j] > array[j + step]; j -= step)
{
tmp = array[j];
array[j] = array[j + step];
array[j + step] = tmp;
}
}
void ShellSort57 (int array[], int size) // * ?k = (b?k?1)/2 ?0 = N
{
int step, i, j, tmp;
// Выбор шага
step = 57;
for (i = step; i < size; i++)
// Перестановка элементов внутри подсписка, пока i-тый не будет отсортирован
for (j = i - step; j >= 0 && array[j] > array[j + step]; j -= step)
{
tmp = array[j];
array[j] = array[j + step];
array[j + step] = tmp;
}
}
void ShellSort23 (int array[], int size) // * ?k = (b?k?1)/2 ?0 = N
{
int step, i, j, tmp;
// Выбор шага
step = 23;
for (i = step; i < size; i++)
// Перестановка элементов внутри подсписка, пока i-тый не будет отсортирован
for (j = i - step; j >= 0 && array[j] > array[j + step]; j -= step)
{
tmp = array[j];
array[j] = array[j + step];
array[j + step] = tmp;
}
}
void ShellSort10 (int array[], int size) // * ?k = (b?k?1)/2 ?0 = N
{
int step, i, j, tmp;
// Выбор шага
step = 10;
for (i = step; i < size; i++)
// Перестановка элементов внутри подсписка, пока i-тый не будет отсортирован
for (j = i - step; j >= 0 && array[j] > array[j + step]; j -= step)
{
tmp = array[j];
array[j] = array[j + step];
array[j + step] = tmp;
}
}
void ShellSort4 (int array[], int size) // * ?k = (b?k?1)/2 ?0 = N
{
int step, i, j, tmp;
// Выбор шага
step = 4;
for (i = step; i < size; i++)
// Перестановка элементов внутри подсписка, пока i-тый не будет отсортирован
for (j = i - step; j >= 0 && array[j] > array[j + step]; j -= step)
{
tmp = array[j];
array[j] = array[j + step];
array[j + step] = tmp;
}
}
void ShellSort1 (int array[], int size) // * ?k = (b?k?1)/2 ?0 = N
{
int step, i, j, tmp;
// Выбор шага
step = 1;
for (i = step; i < size; i++)
// Перестановка элементов внутри подсписка, пока i-тый не будет отсортирован
for (j = i - step; j >= 0 && array[j] > array[j + step]; j -= step)
{
tmp = array[j];
array[j] = array[j + step];
array[j + step] = tmp;
}
}
int main(){
int size = 200;
int array[size];
for(int i = 0; i < size; i ++){
}
for(int i = 0; i < size; i++){
}
ShellSort701(array, size);
ShellSort301(array, size);
ShellSort132(array, size);
ShellSort57(array, size);
ShellSort23(array, size);
ShellSort10(array, size);
ShellSort4(array, size);
ShellSort1(array, size);
for(int i = 0; i < size; i++){
}
return 0;
}
CiNpbmNsdWRlIDxzdGRsaWIuaD4KI2luY2x1ZGUgPHN0ZGlvLmg+CgoKdm9pZCBTaGVsbFNvcnQ3MDEgKGludCBhcnJheVtdLCBpbnQgc2l6ZSkgICAgICAgICAgICAgICAvLyAqID9rID0gKGI/az8xKS8yICA/MCA9IE4KewoJaW50IHN0ZXAsIGksIGosIHRtcDsKCQoJLy8g0JLRi9Cx0L7RgCDRiNCw0LPQsAoJCiBzdGVwID0gNzAxOwoJCWZvciAoaSA9IHN0ZXA7IGkgPCBzaXplOyBpKyspIAoJCSAgICAvLyDQn9C10YDQtdGB0YLQsNC90L7QstC60LAg0Y3Qu9C10LzQtdC90YLQvtCyINCy0L3Rg9GC0YDQuCDQv9C+0LTRgdC/0LjRgdC60LAsINC/0L7QutCwIGkt0YLRi9C5INC90LUg0LHRg9C00LXRgiDQvtGC0YHQvtGA0YLQuNGA0L7QstCw0L0KCQkJZm9yIChqID0gaSAtIHN0ZXA7IGogPj0gMCAmJiBhcnJheVtqXSA+IGFycmF5W2ogKyBzdGVwXTsgaiAtPSBzdGVwKQoJCQl7CgkJCQl0bXAgPSBhcnJheVtqXTsKCQkJCWFycmF5W2pdID0gYXJyYXlbaiArIHN0ZXBdOwoJCQkJYXJyYXlbaiArIHN0ZXBdID0gdG1wOwoJCQl9Cn0Kdm9pZCBTaGVsbFNvcnQzMDEgKGludCBhcnJheVtdLCBpbnQgc2l6ZSkgICAgICAgICAgICAgICAvLyAqID9rID0gKGI/az8xKS8yICA/MCA9IE4KewoJaW50IHN0ZXAsIGksIGosIHRtcDsKCQoJLy8g0JLRi9Cx0L7RgCDRiNCw0LPQsAoJCiBzdGVwID0gMzAxOwoJCWZvciAoaSA9IHN0ZXA7IGkgPCBzaXplOyBpKyspIAoJCSAgICAvLyDQn9C10YDQtdGB0YLQsNC90L7QstC60LAg0Y3Qu9C10LzQtdC90YLQvtCyINCy0L3Rg9GC0YDQuCDQv9C+0LTRgdC/0LjRgdC60LAsINC/0L7QutCwIGkt0YLRi9C5INC90LUg0LHRg9C00LXRgiDQvtGC0YHQvtGA0YLQuNGA0L7QstCw0L0KCQkJZm9yIChqID0gaSAtIHN0ZXA7IGogPj0gMCAmJiBhcnJheVtqXSA+IGFycmF5W2ogKyBzdGVwXTsgaiAtPSBzdGVwKQoJCQl7CgkJCQl0bXAgPSBhcnJheVtqXTsKCQkJCWFycmF5W2pdID0gYXJyYXlbaiArIHN0ZXBdOwoJCQkJYXJyYXlbaiArIHN0ZXBdID0gdG1wOwoJCQl9Cn0Kdm9pZCBTaGVsbFNvcnQxMzIgKGludCBhcnJheVtdLCBpbnQgc2l6ZSkgICAgICAgICAgICAgICAvLyAqID9rID0gKGI/az8xKS8yICA/MCA9IE4KewoJaW50IHN0ZXAsIGksIGosIHRtcDsKCQoJLy8g0JLRi9Cx0L7RgCDRiNCw0LPQsAoJCiBzdGVwID0gMTMyOwoJCWZvciAoaSA9IHN0ZXA7IGkgPCBzaXplOyBpKyspIAoJCSAgICAvLyDQn9C10YDQtdGB0YLQsNC90L7QstC60LAg0Y3Qu9C10LzQtdC90YLQvtCyINCy0L3Rg9GC0YDQuCDQv9C+0LTRgdC/0LjRgdC60LAsINC/0L7QutCwIGkt0YLRi9C5INC90LUg0LHRg9C00LXRgiDQvtGC0YHQvtGA0YLQuNGA0L7QstCw0L0KCQkJZm9yIChqID0gaSAtIHN0ZXA7IGogPj0gMCAmJiBhcnJheVtqXSA+IGFycmF5W2ogKyBzdGVwXTsgaiAtPSBzdGVwKQoJCQl7CgkJCQl0bXAgPSBhcnJheVtqXTsKCQkJCWFycmF5W2pdID0gYXJyYXlbaiArIHN0ZXBdOwoJCQkJYXJyYXlbaiArIHN0ZXBdID0gdG1wOwoJCQl9Cn0Kdm9pZCBTaGVsbFNvcnQ1NyAoaW50IGFycmF5W10sIGludCBzaXplKSAgICAgICAgICAgICAgIC8vICogP2sgPSAoYj9rPzEpLzIgID8wID0gTgp7CglpbnQgc3RlcCwgaSwgaiwgdG1wOwoJCgkvLyDQktGL0LHQvtGAINGI0LDQs9CwCgkKIHN0ZXAgPSA1NzsKCQlmb3IgKGkgPSBzdGVwOyBpIDwgc2l6ZTsgaSsrKSAKCQkgICAgLy8g0J/QtdGA0LXRgdGC0LDQvdC+0LLQutCwINGN0LvQtdC80LXQvdGC0L7QsiDQstC90YPRgtGA0Lgg0L/QvtC00YHQv9C40YHQutCwLCDQv9C+0LrQsCBpLdGC0YvQuSDQvdC1INCx0YPQtNC10YIg0L7RgtGB0L7RgNGC0LjRgNC+0LLQsNC9CgkJCWZvciAoaiA9IGkgLSBzdGVwOyBqID49IDAgJiYgYXJyYXlbal0gPiBhcnJheVtqICsgc3RlcF07IGogLT0gc3RlcCkKCQkJewoJCQkJdG1wID0gYXJyYXlbal07CgkJCQlhcnJheVtqXSA9IGFycmF5W2ogKyBzdGVwXTsKCQkJCWFycmF5W2ogKyBzdGVwXSA9IHRtcDsKCQkJfQp9CnZvaWQgU2hlbGxTb3J0MjMgKGludCBhcnJheVtdLCBpbnQgc2l6ZSkgICAgICAgICAgICAgICAvLyAqID9rID0gKGI/az8xKS8yICA/MCA9IE4KewoJaW50IHN0ZXAsIGksIGosIHRtcDsKCQoJLy8g0JLRi9Cx0L7RgCDRiNCw0LPQsAoJCiBzdGVwID0gMjM7CgkJZm9yIChpID0gc3RlcDsgaSA8IHNpemU7IGkrKykgCgkJICAgIC8vINCf0LXRgNC10YHRgtCw0L3QvtCy0LrQsCDRjdC70LXQvNC10L3RgtC+0LIg0LLQvdGD0YLRgNC4INC/0L7QtNGB0L/QuNGB0LrQsCwg0L/QvtC60LAgaS3RgtGL0Lkg0L3QtSDQsdGD0LTQtdGCINC+0YLRgdC+0YDRgtC40YDQvtCy0LDQvQoJCQlmb3IgKGogPSBpIC0gc3RlcDsgaiA+PSAwICYmIGFycmF5W2pdID4gYXJyYXlbaiArIHN0ZXBdOyBqIC09IHN0ZXApCgkJCXsKCQkJCXRtcCA9IGFycmF5W2pdOwoJCQkJYXJyYXlbal0gPSBhcnJheVtqICsgc3RlcF07CgkJCQlhcnJheVtqICsgc3RlcF0gPSB0bXA7CgkJCX0KfQp2b2lkIFNoZWxsU29ydDEwIChpbnQgYXJyYXlbXSwgaW50IHNpemUpICAgICAgICAgICAgICAgLy8gKiA/ayA9IChiP2s/MSkvMiAgPzAgPSBOCnsKCWludCBzdGVwLCBpLCBqLCB0bXA7CgkKCS8vINCS0YvQsdC+0YAg0YjQsNCz0LAKCQogc3RlcCA9IDEwOwoJCWZvciAoaSA9IHN0ZXA7IGkgPCBzaXplOyBpKyspIAoJCSAgICAvLyDQn9C10YDQtdGB0YLQsNC90L7QstC60LAg0Y3Qu9C10LzQtdC90YLQvtCyINCy0L3Rg9GC0YDQuCDQv9C+0LTRgdC/0LjRgdC60LAsINC/0L7QutCwIGkt0YLRi9C5INC90LUg0LHRg9C00LXRgiDQvtGC0YHQvtGA0YLQuNGA0L7QstCw0L0KCQkJZm9yIChqID0gaSAtIHN0ZXA7IGogPj0gMCAmJiBhcnJheVtqXSA+IGFycmF5W2ogKyBzdGVwXTsgaiAtPSBzdGVwKQoJCQl7CgkJCQl0bXAgPSBhcnJheVtqXTsKCQkJCWFycmF5W2pdID0gYXJyYXlbaiArIHN0ZXBdOwoJCQkJYXJyYXlbaiArIHN0ZXBdID0gdG1wOwoJCQl9Cn0Kdm9pZCBTaGVsbFNvcnQ0IChpbnQgYXJyYXlbXSwgaW50IHNpemUpICAgICAgICAgICAgICAgLy8gKiA/ayA9IChiP2s/MSkvMiAgPzAgPSBOCnsKCWludCBzdGVwLCBpLCBqLCB0bXA7CgkKCS8vINCS0YvQsdC+0YAg0YjQsNCz0LAKCQogc3RlcCA9IDQ7CgkJZm9yIChpID0gc3RlcDsgaSA8IHNpemU7IGkrKykgCgkJICAgIC8vINCf0LXRgNC10YHRgtCw0L3QvtCy0LrQsCDRjdC70LXQvNC10L3RgtC+0LIg0LLQvdGD0YLRgNC4INC/0L7QtNGB0L/QuNGB0LrQsCwg0L/QvtC60LAgaS3RgtGL0Lkg0L3QtSDQsdGD0LTQtdGCINC+0YLRgdC+0YDRgtC40YDQvtCy0LDQvQoJCQlmb3IgKGogPSBpIC0gc3RlcDsgaiA+PSAwICYmIGFycmF5W2pdID4gYXJyYXlbaiArIHN0ZXBdOyBqIC09IHN0ZXApCgkJCXsKCQkJCXRtcCA9IGFycmF5W2pdOwoJCQkJYXJyYXlbal0gPSBhcnJheVtqICsgc3RlcF07CgkJCQlhcnJheVtqICsgc3RlcF0gPSB0bXA7CgkJCX0KfQp2b2lkIFNoZWxsU29ydDEgKGludCBhcnJheVtdLCBpbnQgc2l6ZSkgICAgICAgICAgICAgICAvLyAqID9rID0gKGI/az8xKS8yICA/MCA9IE4KewoJaW50IHN0ZXAsIGksIGosIHRtcDsKCQoJLy8g0JLRi9Cx0L7RgCDRiNCw0LPQsAoJCiBzdGVwID0gMTsKCQlmb3IgKGkgPSBzdGVwOyBpIDwgc2l6ZTsgaSsrKSAKCQkgICAgLy8g0J/QtdGA0LXRgdGC0LDQvdC+0LLQutCwINGN0LvQtdC80LXQvdGC0L7QsiDQstC90YPRgtGA0Lgg0L/QvtC00YHQv9C40YHQutCwLCDQv9C+0LrQsCBpLdGC0YvQuSDQvdC1INCx0YPQtNC10YIg0L7RgtGB0L7RgNGC0LjRgNC+0LLQsNC9CgkJCWZvciAoaiA9IGkgLSBzdGVwOyBqID49IDAgJiYgYXJyYXlbal0gPiBhcnJheVtqICsgc3RlcF07IGogLT0gc3RlcCkKCQkJewoJCQkJdG1wID0gYXJyYXlbal07CgkJCQlhcnJheVtqXSA9IGFycmF5W2ogKyBzdGVwXTsKCQkJCWFycmF5W2ogKyBzdGVwXSA9IHRtcDsKCQkJfQp9CgogaW50IG1haW4oKXsKIAlzcmFuZCAodGltZSAoTlVMTCkpOwoKIAlpbnQgc2l6ZSA9IDIwMDsKIAlpbnQgYXJyYXlbc2l6ZV07CiAJcHJpbnRmKCIgQmVmb3JlIFxuIik7CiAJZm9yKGludCBpID0gMDsgaSA8IHNpemU7IGkgKyspewogCQlhcnJheVtpXSA9IHJhbmQoKSUxMDAwOwogCX0KCSBmb3IoaW50IGkgPSAwOyBpIDwgc2l6ZTsgaSsrKXsKIAkJcHJpbnRmKCIlZCBcdCIsIGFycmF5W2ldKTsKIAl9CiAJU2hlbGxTb3J0NzAxKGFycmF5LCBzaXplKTsKIAlTaGVsbFNvcnQzMDEoYXJyYXksIHNpemUpOwogCVNoZWxsU29ydDEzMihhcnJheSwgc2l6ZSk7CiAJU2hlbGxTb3J0NTcoYXJyYXksIHNpemUpOwogCVNoZWxsU29ydDIzKGFycmF5LCBzaXplKTsKIAlTaGVsbFNvcnQxMChhcnJheSwgc2l6ZSk7CiAJU2hlbGxTb3J0NChhcnJheSwgc2l6ZSk7CiAJU2hlbGxTb3J0MShhcnJheSwgc2l6ZSk7CgogCSAJcHJpbnRmKCJcbiBBZnRlciBcbiIpOwoKIAkJZm9yKGludCBpID0gMDsgaSA8IHNpemU7IGkrKyl7CiAJCXByaW50ZigiJWQgXHQiLCBhcnJheVtpXSk7CiAJfQoJcmV0dXJuIDA7Cgl9Cg==