Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > Центр помощи > [С++] Сортировка Шелла


Автор: djkarp 25.12.2006, 00:26
1.Сортировка Шелла
Описать заданный вид сортировки
Написать программу выполняющий заданный вид сортировки
для массива из 8 элементов
1.Подсчитать количество подстановок для наилучшего случая
2.Подсчитать количество подстановок для наихудшего случая
3.Подсчитать количество подстановок для набора чисел (15550433)
Оценить время выполнения программы, используя метод подсчета количества выполняемых операторов!
Ребята выручайте пожалуйста, честное слово, остальное сделал осталось только это, как что хз, забыл все напрочь, завтра сдавать ! выручайте плиз

Автор: zabivator 25.12.2006, 00:32
http://algolist.manual.ru/
есть центр помощи. Задолбали уже!

Автор: Pete 25.12.2006, 01:27
http://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%BC%D0%B5%D1%82%D0%BE%D0%B4%D0%BE%D0%BC_%D0%A8%D0%B5%D0%BB%D0%BB%D0%B0, 
http://en.wikipedia.org/wiki/Shell_sort.

Автор: Alexeis 25.12.2006, 01:39

M
alexeis1		Модератор: Название темы должно отражать ее суть!

Автор: zkv 25.12.2006, 04:15
Цитата(zabivator @  25.12.2006,  00:32 Найти цитируемый пост)
Задолбали уже!

терпимее надо быть smile

Автор: V.A.KeRneL 25.12.2006, 05:13
Цитата(zabivator @  25.12.2006, 00:32 Найти цитируемый пост)

http://algolist.manual.ru/

zabivator, Алголист уже какую неделю не работает!.. smile

djkarp, но с такими вопросами, действительно, надо в http://forum.vingrad.ru/Vingrad-help-center.html. 
А лучше с запросом к Википедии: 
http://en.wikipedia.org/wiki/Shell_sort
http://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%BC%D0%B5%D1%82%D0%BE%D0%B4%D0%BE%D0%BC_%D0%A8%D0%B5%D0%BB%D0%BB%D0%B0
И Гуглу: 
http://www.google.com/search?hl=en&q=%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0+%D0%A8%D0%B5%D0%BB%D0%BB%D0%B0&btnG=Google+Search
Вот что показалось самым интересным из найденного лично мне: 
http://www.codenet.ru/progr/alg/sort_search/shl.php

Автор: Earnest 25.12.2006, 08:53
Для домашних заданий, курсовых, существует "Центр Помощи".

Тема перенесена! 

Автор: Alexeis 25.12.2006, 10:22

M
alexeis1		Модератор: дублирование тем запрещено правилами форума. (темы объединил)

Автор: djkarp 25.12.2006, 14:42
Ребята коли она в центре помощи уже, вы не могли бы реально помочь, а то на примере ниче не ясно!

Автор: Rockie 25.12.2006, 15:29
Цитата(djkarp @  25.12.2006,  14:42 Найти цитируемый пост)
Ребята коли она в центре помощи уже, вы не могли бы реально помочь

это деньгами чтоли?.. =)

Цитата(djkarp @  25.12.2006,  00:26 Найти цитируемый пост)
Описать заданный вид сортировки

То же самое, что пузырьковая, только сравниваются не рядом стоящие элемены. Интервалы могут быть разными, с каждой итерацией они уменьшаются(к примеру делятся на 2). Когда интервал равен 1, значит сравниваются рядом стоящие элементы, а это пузырьковая сортировка:

3 4 5 1 2 8 
1 4 5 3 2 8

Здесь длина массива 6, меняем местами элементы, отстоящие друг от друга на 3 позиции (половина массива), потом этот интервал уменьшаем в два раза, и сортируем пузырьковой. 
Если 8 элементов, то сравниваешь эл-ты на расстоянии в 4 элемента, потом в 2, потом пузырьковая сортировка.

Цитата(djkarp @  25.12.2006,  00:26 Найти цитируемый пост)
1.Подсчитать количество подстановок для наилучшего случая

это когда массив отсортирован

Цитата(djkarp @  25.12.2006,  00:26 Найти цитируемый пост)
2.Подсчитать количество подстановок для наихудшего случая

это когда отсортирован в обратном порядке

Автор: djkarp 25.12.2006, 19:36
Конечно спасиб те РОККИ, но только если б я че нить в этом шарил , то я бы не обращался, требуется исходный код всей задачи, вот и прошу может кто нить может помочь?!((

Автор: Rockie 25.12.2006, 21:28
Цитата(djkarp @  25.12.2006,  19:36 Найти цитируемый пост)
Конечно спасиб те РОККИ, но только если б я че нить в этом шарил , то я бы не обращался, требуется исходный код всей задачи, вот и прошу может кто нить может помочь?!((

Сортировка Шелла использует пузырьковую, ее даже комментировать не буду. В программе массив объявлен как глобальный, так как вытаскивал сортировки из своего класса массивов. По-хорошему надо массив и размер в функции _передавать_.
Код
#include <iostream>

#define size 10

int array[size] = {4,6,32,5,8,90,5,3,2,-7};


void DisplayArray()                              // распечатка массива
{
    std::cout<<std::endl;

    for(int i=0;i<size;i++)
      std::cout<<array[i]<<' ';
}


void SortBubble()                                 // пузырьковая
{
    int tmp = 0, flag=1;

    while(flag)                                   // флаг условия Айверсона
    { 
        flag=0;
        for(int i=0;i<size-1;i++)  
          { 
           if(array[i]>array[i+1])      
            { tmp=array[i], array[i]=array[i+1],array[i+1]=tmp, flag=1;
            }
          }
    }
}


void ShellSort()                                  // Шелла
{
    int d=size/2;                                 // начальный интервал в половину массива
    int i=0,tmp=0;

    while(d>1)              
     { 
       if(array[i]>array[i+d])                    // если справа меньший элемент
        { tmp=array[i], array[i]=array[i+d], array[i+d]=tmp;   // меняем эл-ты местами
        }
       i++;                                       // двигаемся дальше по массиву
       if (i+d==size)                             // дошли до конца массива 
        { d/=2;                                   // уменьшаем интервал и повторяем
          i=0;
        }
     }

    SortBubble();                                 // сравниваются рядом стоящие элементы, 
                                                  // добиваем пузырьковой сортировкой
}



int main()
{ 
    DisplayArray();
    ShellSort();
    DisplayArray();

    return 0;
}

Автор: Pete 25.12.2006, 22:15
Цитата(djkarp @  25.12.2006,  15:42 Найти цитируемый пост)
вы не могли бы реально помочь

Прикольно. Я думал, что скопировать готовую прогу с чужого сайта не сложно, но ошибся. Оказывается, надо выкладывать ПРЯМО сюда. И не дай Бог, не будет объяснена какая-то строка (даже та, где последняя фигурная скобочка закрывается  smile ).

Автор: Rockie 25.12.2006, 23:20
Цитата(Pete @  25.12.2006,  22:15 Найти цитируемый пост)
Прикольно. Я думал, что скопировать готовую прогу с чужого сайта не сложно, но ошибся.


Pete, а че прикольного? Ты хочешь сказать я чужую прогу выложил? Алгоритмы могут быть похожи, сортировки ведь в свое время где-то доставал, я ведь не Шелл. =) Но эта программа с моего винта, предъяви сайт с которого я по твоему мнению ее копировал.

Автор: Pete 26.12.2006, 00:15
Заметь, я не тебя процитировал. По данным человеку ссылкам уже лежат готовые проги, можно было их взять. Но он захотел, чтобы непременно сюда код выложили.
Цитата(Rockie @  26.12.2006,  00:20 Найти цитируемый пост)
Ты хочешь сказать я чужую прогу выложил

Ни в коем случае!

Автор: Rockie 26.12.2006, 01:58
Pete, понятно =)

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)