VPF::Сортировка вставками - Форум программистов

Sergio

Дата 24.10.2006, 21:49 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 843
Регистрация: 28.7.2006
Где: Solar System-> Earth

Репутация: 0
Всего: 1

Здраствуйте. Не имогу понять как роботает сортировка вставками smile

Вот текст из книги:

Сортировка вставками - простой и достаточно эффективный метод сортировки, при котором элементы данных используются в качестве ключей для сравнения. Алгоритм сначала упорядочивает элементы X[0] и X[1], вставляя X[1] перед X[0], если X[0] > X[1]. Затем оставшиеся элементы данных по очереди вставляются в этот упорядоченный набор. После i-й итерации элемент X[i] оказывается в своей правильной позиции и элементы от X[0] до X[i] уже отсортированы.

BreakPointMAN

Дата 24.10.2006, 22:37 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 725
Регистрация: 15.9.2004
Где: Saratov

Репутация: 14
Всего: 24

Это сообщение отредактировал(а) BreakPointMAN - 24.10.2006, 22:40

--------------------

"Разруха не в клозетах, а в головах." © Ф.Ф. Преображенский (М.Булгаков, "Собачье сердце")

Sergio

Дата 24.10.2006, 22:52 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 843
Регистрация: 28.7.2006
Где: Solar System-> Earth

Репутация: 0
Всего: 1

Спасибо большое. Но я всё ровно не могу "роздуплиться" smile

Вот пример:

Код

 
void insertSort(array_type a[], int length) 
{
     int i, j;
     array_type value;        // что это такое??? (что за тип???)

     for(i = 1; i < length; i++) 
      {
         value = a[i];
         for (j = i-1; (j >= 0) && (a[j] > value); j--) 
          {
             a[j+1] = a[j];
          }
         a[j+1] = value;
     }
}

P.S. Я понял про пузырковую сортировку, а эту сортировку не пойму... smile

Помогите плз

Это сообщение отредактировал(а) Sergio - 24.10.2006, 22:54

BreakPointMAN

Дата 24.10.2006, 22:55 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 725
Регистрация: 15.9.2004
Где: Saratov

Репутация: 14
Всего: 24

Цитата(Sergio @ 24.10.2006, 23:52

)

array_type value; // что это такое??? (что за тип???)

int, например...

Добавлено @ 22:58

Цитата(Sergio @ 24.10.2006, 23:52

)

P.S. Я понял про пузырковую сортировку, а эту сортировку не пойму...

Сначала почитай, а потом задавай конкретные вопросы. А по вышеприведенным мной ссылкам информации более, чем достаточно, и вряд ли кто-то сумеет объяснить тебе лучше.

Это сообщение отредактировал(а) BreakPointMAN - 24.10.2006, 22:59

--------------------

"Разруха не в клозетах, а в головах." © Ф.Ф. Преображенский (М.Булгаков, "Собачье сердце")

Rockie

Дата 24.10.2006, 23:19 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1143
Регистрация: 23.4.2006

Репутация: 8
Всего: 31

Sergio, думаю имеется ввиду любой тип, к примеру int или double. где-то в коде возможно что-нибудь такое

Код

#define array_type int

--------------------

Чтобы иметь большой гардероб - надо иметь большой гардероб.

DukeCpp

Дата 25.10.2006, 07:22 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 40
Регистрация: 27.2.2006
Где: St.Petersburg

Репутация: нет
Всего: 1

Цитата(Rockie @ 24.10.2006, 23:19)

Sergio, думаю имеется ввиду любой тип, к примеру int или double. где-то в коде возможно что-нибудь такое

Код

#define array_type int

ну уж искренне верю, что

Код



typedef int array_type;

zhenium

Дата 6.11.2006, 23:21 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 71
Регистрация: 16.10.2006

Репутация: нет
Всего: 2

Продолжу тему.
Люди, посмотрите данный фрагмент кода. Это типа сортировка вставками. Только вот сортирует она как-то по левому!
Была дана на лекции как пример. Поэтому и примера-то толкового нет. Помогите разобраться, в чём здесь ошибка... Очень нужно...

Код


for( ctr_1 = 1; ctr_1 < ELEM; ctr_1++ )
    for( ctr_2 = 0; ctr_2 < ctr_1; ctr_2++ )
    {
        if( strcmp( mass[ctr_1].seria, mass[ctr_2].seria ) > 0 )
        {
            buf = mass[ctr_1];

            for( ctr_3 = ctr_1; ctr_3 < ctr_2; ctr_3-- )
                mass[ctr_3] = mass[ctr_3 - 1];

            mass[ctr_2] = buf;
        }
    }

Xenon

Дата 6.11.2006, 23:27 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Участник Клуба
Сообщений: 1529
Регистрация: 12.4.2006

Репутация: 11
Всего: 50

Код


for( ctr_1 = 1; ctr_1 < ELEM; ctr_1++ )
    for( ctr_2 = 0; ctr_2 < ctr_1; ctr_2++ )
    {
        if( strcmp( mass[ctr_1].seria, mass[ctr_2].seria ) > 0 )
        {
            buf = mass[ctr_1];

            for( ctr_3 = ctr_1; ctr_3 < ctr_2; ctr_3-- )
                mass[ctr_3] = mass[ctr_3 - 1];

            mass[ctr_2] = buf; //mass[ctr_2+1] ?
        }
    }

А так кинь весь код, а то я не очень понимаю что есть что.

Это сообщение отредактировал(а) Xenon - 6.11.2006, 23:29

--------------------

zhenium

Дата 6.11.2006, 23:50 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 71
Регистрация: 16.10.2006

Репутация: нет
Всего: 2

Вот весь код:

Код


/* Zagolovochniy fail */

#include "diod.h"

/* Funkcia void sor_vs( struct diod mass[], int dlina ) */

void sor_vs( struct diod mass[], int dlina )
{
    int      ctr_1 = 0, ctr_2 = 0, ctr_3, x;        // Schetchiki i peremennaya vibora
    struct diod buf;                 // Bufernaya structura

    clrscr();

    for( ctr_1 = 0; ctr_1 < ELEM; ctr_1++ )
        if( mass[ctr_1].tip[0] == '\0' )
            ctr_2++;

    /* Proverka nalichia informacii */

    if( ctr_2 == ELEM )
    {
        puts("\t\tNet dannih dlia sortirovki.\n\n\t\t'Enter' - Vozvrat v glavnoe menu.");

        fflush( stdin );
        getchar();

        return;
    }

    x = menu_3();

    clrscr();

    switch( x )
    {
        case 1:       // Sortirovka po vozrastaniyu
        {
            for( ctr_1 = 1; ctr_1 < ELEM; ctr_1++ )
                for( ctr_2 = 0; ctr_2 < ctr_1; ctr_2++ )
                {
                    if( strcmp( mass[ctr_1].seria, mass[ctr_2].seria ) > 0 )
                    {
                        buf = mass[ctr_1];

                        for( ctr_3 = ctr_1; ctr_3 < ctr_2; ctr_3-- )
                            mass[ctr_3] = mass[ctr_3 - 1];

                        mass[ctr_2] = buf;
                    }
                }
            break;
        }
        case 2:       // Sortirovka po ubivaniyu
        {
            for( ctr_1 = 1; ctr_1 < ELEM; ctr_1++ )
                for( ctr_2 = 0; ctr_2 < ctr_1; ctr_2++ )
                {
                    if( strcmp( mass[ctr_1].seria, mass[ctr_2].seria ) < 0 )
                    {
                        buf = mass[ctr_1];

                        for( ctr_3 = ctr_1; ctr_3 < ctr_2; ctr_3-- )
                            mass[ctr_3] = mass[ctr_3 - 1];

                        mass[ctr_2] = buf;
                    }
                }
            break;
        }
        default:
        {
            puts("\tVy vveli nevernoe znachenie.\n\tPoprobuyte snova.");

            fflush( stdin );
            getchar();
        }
    }

Т.е. я привёл не весь код, а только его первую половину, а дальше идёт вывод таблицы и т.д. Думаю, это роли никакой не даст. А вот сортирует она неправильно. Нужно по возрастанию и убыванию. И ещё ELEM - кол-во элементов в массиве.
P.S. Весь исходник - несколько файлов, поэтому привёл только необходимый.
Заранее благодарю!!!

Rockie

Дата 7.11.2006, 00:10 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1143
Регистрация: 23.4.2006

Репутация: 8
Всего: 31

Цитата(zhenium @ 6.11.2006, 23:50

)

P.S. Весь исходник - несколько файлов, поэтому привёл только необходимый. Заранее благодарю!!!

zhenium, ну и выложил бы несколько файлов. У тебя же там не >10 000 строк. Или ты эту сортировку продаешь? smile

А так ты даже не привел ошибки компилятора, здесь почти все телепаты, но все-таки.

Цитата(zhenium @ 6.11.2006, 23:21

)

buf = mass[ctr_1];

надеюсь buf это указатель? В противном случае так со строковыми массивами не работают.

Цитата(Xenon @ 6.11.2006, 23:27

)

for( ctr_3 = ctr_1; ctr_3 < ctr_2; ctr_3-- ) mass[ctr_3] = mass[ctr_3 - 1];

Здесь ты в цикле выполняешь одно и то же.

добавлено:
да и вообще - что происходит в этом цикле? Что необходимо делать? Если ctr_3 больше ctr_2, то цикл вообще не сработает, если ctr_3 меньше ctr_2 то цикл будет работать вплоть до выхода за предел int-а.

Это сообщение отредактировал(а) Rockie - 7.11.2006, 00:57

--------------------

Чтобы иметь большой гардероб - надо иметь большой гардероб.

zhenium

Дата 7.11.2006, 00:23 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 71
Регистрация: 16.10.2006

Репутация: нет
Всего: 2

В том-то и дело - компиляция идёт просто гладко. Никаких предъяв у него ко мне нет...
buf - не указатель, а структура-буфер.

Цитата

buf = mass[ctr_1];

Это я одну структуры в другую копирую.
Вообще в структуре 5 полей. Надо сортировать по строковому полю. Такая фигня прошла с помощью сортировки выбором, а вот со вставкой я и засел...

P.S. А всю эту прогу я продавать никак не собирался! smile

По учёбе нужно.

Xenon

Дата 7.11.2006, 00:33 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Участник Клуба
Сообщений: 1529
Регистрация: 12.4.2006

Репутация: 11
Всего: 50

Rockie, а, ну да ... я просто мельком глянул smile

Запутанно

Поэтому и попросил весь код кинуть - я не понимаю что какая переменная значит.

--------------------

zhenium

Дата 7.11.2006, 00:40 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 71
Регистрация: 16.10.2006

Репутация: нет
Всего: 2

>>> Xenon

Если какие-то непонятия, то ты спроси, я попробую объяснить...

Xela

Дата 7.11.2006, 03:47 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 62
Регистрация: 2.6.2005

Репутация: нет
Всего: нет

считаем что после i-й итерации алгоритм ставит элементы Х[0],...,X[i-1] на t1,...,ti - е места в массиве Тогда подмассив состоящий из элементов стоящих на t1,...,ti местах основного массива есть упорядоченный массив

zhenium

Дата 7.11.2006, 20:34 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 71
Регистрация: 16.10.2006

Репутация: нет
Всего: 2

Ну разве никто не может помочь мне с моим примером??? smile

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Общие вопросы \| Следующая тема »