Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Yentroistok
1 / 1 / 0
Регистрация: 25.02.2012
Сообщений: 59
#1

Заполнение массива методом Седжвика - C++

03.07.2012, 16:52. Просмотров 791. Ответов 1
Метки нет (Все метки)

Можно ли как-то заполнить массив методом Седжвика по другому, что бы не было столько нулей, сколько сейчас.(ну т.е. чтобы значительно меньше).

или если массив заполняется рандомно, то как сделать так, чтобы сортировка Шелла работала?

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <stdio.h>
#include <conio.h>
#include <iostream>
using namespace std;
 
//--------------------------------------------------------------------------------------------------------------------------
/* Рассчитывает последовательность
   приращений рекомендуюмую при больших
   размерах сортируемой последовательности */
int increment(long inc[], long size) {
    int i = 0;
    inc[i] = 1;
 
    do {
        i++;
        inc[i] = 3*inc[i-1] + 1;
    } while (inc[i] < size);
 
    return (i < 2) ? 0 : i-2;
}
//--------------------------------------------------------------------------------------------------------------------------
template<class T>
void shellSort(T inc[], long size) {
    /* максимальное количество рассчитываемых
       приращений = 20 */
    long d, i, j, dseq[20];
    int di;
 
    /* Рассчитываем последовательность
       приращений */
    di = increment(dseq, size);
 
    while (di >= 0) {
        /* Приращение на данном шаге */
        d = dseq[di--];
 
        /* этот цикл делает проход "пузырька" в том числе и
           для последней последовательности, когда d=1, поэтому
           вызывать в конце InsertSort или какую-либо другую
           элементарную сортировку - не требуется */
        for (i = d; i < size; i++) {
            T tmp = inc[i];
            for (j = i-d; (j >= 0) && (inc[j] > tmp); j -= d) {
                inc[j+d] = inc[j];
            }
            inc[j+d] = tmp;
        }
    }
    /* Не требуется вызывать InsertSort или BubbleSort
       т.е. ко всей последовательности во вложенном цикле
       уже был применен метод пузырька */
}
 
void main ()
{   
    long a[1000] = {};
    increment(a, 1000);
    shellSort(a, 1000);
    for (int i = 0; i < 1000; i++)
        cout << a[i] << " ";
 
    _getch();
 
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.07.2012, 16:52
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Заполнение массива методом Седжвика (C++):

Книги Седжвика - C++
вечер добрый есть ли существенная разница между этими книгами? 1) http://www.ozon.ru/context/detail/id/1425749/ 2)...

Нечетные элементы массива отсортировать методом пузырька, а четные методом прямого доступа - C++
Дан одномерный массив, в нем нечетные элементы отсортировать методом пузырька, а четные методом прямого доступа(или прямого включения, могу...

Сортировка массива пузырьковым методом и методом вставки - C++
нужно написать программу которая будет делать сортировку этими способами в массиве 3x10, две кнопки, таблица (3х10), собственно...

6-я глава книги "Фундаментальные алгоритмы C++" Роберта Седжвика - C++
Разбираю 6-ю главу книги Роберт Седжвик: Фундаментальные алгоритмы C++. Части 1-4 Расматриваются простые методы сортировки, любых типов...

ввод двумерного массива,ввод размерности массива,заполнение массива случайными числами - C++
#include &quot;stdafx.h&quot; #include &quot;locale.h&quot; #include &quot;stdlib.h&quot; #include &quot;math.h&quot; void main() { setlocale(LC_ALL,&quot;rus&quot;); int...

Заполнение массива значениями из символьного массива - C++
есть массив символов char z;есть целочисленный массив int b;каждый символ z это цифра 0-9 нужно в b записать символ z(не код символа а...

1
zitxbit
88 / 740 / 75
Регистрация: 11.04.2012
Сообщений: 971
03.07.2012, 19:55 #2
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <stdio.h>
#include <conio.h>
#include <iostream>
 
//--------------------------------------------------------------------------------------------------------------------------
/* Рассчитывает последовательность
   приращений рекомендуюмую при больших
   размерах сортируемой последовательности */
int increment(long inc[], long size) {
    int i = 0;
    inc[i] = 1;
 
    do {
        i++;
        inc[i] = abs(3*inc[i-1] + 1);
    } while (i < size);
 
    return (i < 2) ? 0 : i-2;
}
 
template<class T> void shellSort(T inc[], long size)
{
    for (int q = size-1; q >= 0; q--)
         for (int i = 0, d = q; i + d < size; i++)
             if (inc[i] < inc[i+d]) std::swap<T>(inc[i],inc[i+d]);
}
 
using namespace std;
 
int main()
{
    long a[1000] = {};
    increment(a, 1000);
    shellSort<long>(a, 1000);
    for (int i = 0; i < 1000; i++)
        cout << a[i] << " ";
 
    _getch();
 
    return 0;
}
http://liveworkspace.org/code/a608c6...96b9dae293601b
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.07.2012, 19:55
Привет! Вот еще темы с ответами:

Заполнение массива - C++
Помогите, пожалуйста, решить такую задачу: Нужно заполнить массив 6*6 цифрами от 1 до 36 по следующей схеме: 1 2 4 7 11 16 3 ...

Заполнение массива - C++
Подскажите пожалуйста, как заполнить массив в такой закономерности: Например дано число 6:••• Пример для числа 4:••• ...

Заполнение массива - C++
Извините, что флудю, просто в старой теме уже не отвечают. data::data(int f){ if (f==1) ...

Заполнение массива - C++
Заполнить массив двадцатью первыми натуральными числами, делящимися нацело на 13 или на 17 и находящимися в интервале, левая граница...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru