VPF::Что есть "обмен" в сортировке Бинарными вставками?

Avaj

Дата 9.10.2008, 15:41 (ссылка)

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

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 212
Регистрация: 14.7.2008
Где: Владивосток.

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

Что называется обменом в сортировке Бинарными вставками?

Вот, например в Сортировке выбором явно видно, что происходит обмен - два элемента меняются местами. Или в Быстрой сортировке тоже есть явный обмен.

А что же можно назвать обменом в сортировке Бинарными вставками? Ведь там, насколько я понимаю, элемент "вставляется", а стоящие за ним "сдвигаются" вправо.

Приведу код:

Код


for(i=1;i<n;i++){
    x = a[i];
    left = 0;
    right = i;
    while(left<right){
        m=(left+right)/2;
        if(a[m]<=x) left = m+1;
        else right = m;
    }
    for(j=i;j>right;j--) a[j] = a[j-1];
    a[right] = x;
}

Akina

Дата 9.10.2008, 15:57 (ссылка)

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

Загрузка ...

Советчик

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

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

А где это в алгоритме сортировки бинарными вставками говорится об обменах?

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

О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума.

Avaj

Дата 10.10.2008, 07:18 (ссылка)

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

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 212
Регистрация: 14.7.2008
Где: Владивосток.

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

Я и сам не знаю , но у меня в лабораторной работе задание такое - "Посчитать кол-во обменов и число сравнений". ну т.е. проанализировать алгоритм. Вот теперь думаю - какие обмены?

Akina

Дата 10.10.2008, 07:49 (ссылка)

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

Загрузка ...

Советчик

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

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

В таком случае можно смело говорить, что:

количество обменов = 0
количество сравнений = Sum(RoundUp(Log2(1...ElementsCount)))

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

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