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

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

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

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

03.07.2012, 16:52. Просмотров 750. Ответов 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();
 
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.07.2012, 16:52     Заполнение массива методом Седжвика
Посмотрите здесь:

Заполнение массива C++
Заполнение массива от -5 до 5. C++
C++ 6-я глава книги "Фундаментальные алгоритмы C++" Роберта Седжвика
C++ Книги Седжвика
C++ Заполнение массива
C++ Заполнение массива
Заполнение массива C++
C++ Нечетные элементы массива отсортировать методом пузырька, а четные методом прямого доступа
C++ Заполнение массива
Заполнение массива C++
Заполнение массива C++
Заполнение массива от 'А' до 'Я' и 'а' до 'я' C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
zitxbit
Master C/C++
 Аватар для zitxbit
87 / 739 / 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
Yandex
Объявления
03.07.2012, 19:55     Заполнение массива методом Седжвика
Ответ Создать тему
Опции темы

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