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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 10, средняя оценка - 4.70
osen'
5 / 5 / 1
Регистрация: 09.10.2010
Сообщений: 49
#1

Метод Шелла - C++

24.10.2010, 01:02. Просмотров 1352. Ответов 19
Метки нет (Все метки)

попробовала написать это в С++, но что-то не так. можете подсказать
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
#include <iostream.h>
#include <conio.h>
#include <stdio.h>
#include <math.h>
int main(int argc, char* argv[])
{
        int i,n,j,inc,x;
        cin>>n;
        int *A= new int [n];
        randomize();
        for (i=0;i<n;i++)
        {
        A[i]=rand()%20;
        cout<<A[i]<<" ";
        }
        for (inc=n/2;inc>=1;inc=inc/2)
        {
                while (inc>0)
                {
                        for (i=inc+1;i<=n;i++)
                        {
                                j=i-inc;
                                while (j>0)
                                {
                                        if (A[j]>A[j+inc])
                                        {
                                                x=A[j];
                                                A[j]=A[j+inc];
                                                A[j+inc]=x;
                                        }
                                }
                                
                        }
                }
        }
        for (i=0;i<n;i++)
        {
        cout<<A[i];
        }
        getch();
        return 0;
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.10.2010, 01:02
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Метод Шелла (C++):

Не сходится теория и практика метод Шелла и метод простого выбора - C++
Здравствуйте! Помогите пожулуйста найти ошибке в коде, Я уже не знаю где ее искать. У меня метод простого выбора работает по показателям...

Метод Шелла - C++
Ошибка после сортировки методом Шелла. По примеру сайта http://kvodo.ru/sortirovka-shella.html В чем ошибка? #include...

Метод Шелла - C++
Помогите пожалуста решить задачу. Провести сортировку последовательности а1, … , аn методом Шелла. ЗАранее спасибо.

Метод Шелла - C++
Помогите найти ошибку. Задание - Провести сортировку последовательности а1, … , аn методом Шелла. Вот что получилось. ...

Метод Шелла - C++
Проверить упорядочены ли элементы строк матрицы. Если нет, то упорядочить их в порядке убывания методом Шелла.

Метод сортировки Шелла - C++
помогите дописать программу в case 6 СТРОИТЕЛЬНАЯ КОМПАНИЯ (поля: заказчик, вид строительных работ, продолжительность работ,...

19
osen'
5 / 5 / 1
Регистрация: 09.10.2010
Сообщений: 49
27.10.2010, 23:25  [ТС] #16
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
for (inc=n/2;inc>=1;inc=inc/2)              //для приращения inc,начиная от inc=n/2, с шагом inc/2 пока inc>=1 выполнять цикл
        {
                 for (i=inc+1;i<=n;i++)         //для элемента i, начиная от i=inc+1, с шагом 1 пока i<=n выполнять цикл
 
                        {
                                j=i-inc;              //находим j - номер элемента массива, с к-м будет сравниваться i-й элемент
                                    if (A[j]>A[j+inc])  //сравниваем i-й и j-й элементы
                                        {
                                                x=A[j];      //меняем местами i-й и j-й элементы, если j-й элемент больше i-го  
 
                                                A[j]=A[j+inc];
                                                A[j+inc]=x;
                                        }
                                                              
                        
                }
        }
я его немного изменила, удалила цикл while(inc>0),по-моему, он не нужен
0
alexzak
84 / 57 / 1
Регистрация: 07.08.2010
Сообщений: 185
27.10.2010, 23:43 #17
Такое описание никуда не годится. Как ты можешь понять смысл этих циклов, когда ты их описываешь дословно? В чем смысл первого цикла, в чем смысл второго?

Заодно посмотри описание сортировки шелла:

http://ru.wikipedia.org/wiki/%D0%A1%...BB%D0%BB%D0%B0
0
osen'
5 / 5 / 1
Регистрация: 09.10.2010
Сообщений: 49
28.10.2010, 00:58  [ТС] #18
Я просто хотела более подробно описать, эта первая моя "серьезная" работа, до этого я писала только самые элементарные программки. Я читала о сортировке (не просто же так я писала, когда переводила этот код из паскаля, я старалась разобраться).В чем состоит суть сортировки я понимаю, вроде бы, а может и не правильно понимаю.
Если мой массив состоит из n элементов, то значение приращения inc для первого прохода равно половине элементов массива в случае если n-четное, в случае нечетного n берется целое от деления n на 2. Далее для элементов от i=inc+1 до n (для каждого элемента отдельно) я нахожу j элемент (он находится на расстоянии inc от i-го элемента), с которым и сравниваю значение i-го элемента и в случае если j больше, меняю их местами. Потом беру следующее значение приращения inc,равное половине или целому от деления от предыдущего приращения, и так до тех пор, пока приращениие не станет равно 1. В конце концов массив должен отсортироваться.
Просто ни в одном из примеров, которые я рассматривала, я не поняла, чему равно приращение, поэтому решила использовать деление на 2. В идеале это должно быть 1,3,5,9, если я не ошибаюсь или приращение рассчитывается по спец.формулам, к-е оказались для меня тяжелыми в реализации.
Может и правда, я не правильно поняла смысл сортировки, объсните, пожалуйста.
0
alexzak
84 / 57 / 1
Регистрация: 07.08.2010
Сообщений: 185
28.10.2010, 08:50 #19
Ты в принципе понимаешь правильно. Одна неточность только в том, что по j должен быть цикл, где j пробегает от i до числа меньшего чем inc, и в нём нужно обменивать элементы больший с меньшим. Так как у тебя этого цикла не было, то алгоритм работал неправильно. И inc можно уменьшать не в два раза а в 2.2 для большей эффективности алгоритма. В общем будет где-то так:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
    for (int inc = n / 2; inc > 0; inc = inc * 5 / 11)
    {
        for (int i = inc; i < n; ++i)  // идём вверх от inc до n
        {
            int temp = a[i];
 
            int j = i;
            for (; j >= inc && a[j - inc] > temp; j -= inc)
                            // идём в обратном направлении,
                            // сдвигая temp вниз, пока возможно,
                            // а остальные элементы, которые больше temp, вверх
            {
                a[j] = a[j - inc];
            }
 
            // в этом месте выполяется условие a[j - inc] > temp,
            // или j - самый нижний элемент для шага inc.
            // заканчиваем перемещение (сдвиг) temp
            a[j] = temp;
        }
    }
Вместо обмена можно ещё двигать меньший элемент вниз по массиву, пока он не встретит более меньший (т.е. элементы будут в отсортированном порядке). Это и делается в коде выше.
1
osen'
5 / 5 / 1
Регистрация: 09.10.2010
Сообщений: 49
28.10.2010, 20:21  [ТС] #20
спасибо большое, вот только при нахождении inc=inc*5/11 у меня массив не полностью сортируется, а при inc=inc/2 все нормально. Поэтому решила для нахождения приращения оставить деление на 2.
0
28.10.2010, 20:21
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.10.2010, 20:21
Привет! Вот еще темы с ответами:

Метод сортировки Шелла - C++
Написать программу которая реализует метод сортировки Шелла. Сгенерировать три массива 100, 1.000 и 10.000 элементов типа integer...

Сортировка, метод шелла - C++
Всем доброй ночи, задача, дан список студентов и у каждого 5 оценок, отсортировать сумму оценок по убыванию и данные в новый файл, вот мой...

Метод Шелла, алгоритм обмена - C++
Помогите написать программы. 1. Упорядочить заданный список целых значений методом Шелла. 2. Доно массив записей,каждый из которых...

Не получается обнаружить ошибку(метод Шелла) - C++
Проблема в том что я написала программу на паскале,а преподаватель попросил перевести на си,и теперь не могу понять где эта ошибка,выводит...


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

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

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