Модераторы: Poseidon
  

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> [Java] Сортировка вставкой и бинарный поиск места, для вставки 
V
    Опции темы
Kefir
Дата 16.9.2006, 12:47 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


«Hakuna Matata»
***


Профиль
Группа: Комодератор
Сообщений: 1878
Регистрация: 25.1.2003
Где: Tampere, Suomi

Репутация: 2
Всего: 87
Собственно, сабж. Надо к понедельнику сделать на Яве, а я туплю нипадецки. Вот что написал:
Код

    public static void sort (List a) {
        if(a.size() < 2) return; // если лист менее чем из 2х элементов - задача решена
        for(int i = 1; i < a.size(); i++) { // длина всего этого дела равна длине листа, нулевой элемент оставляем, т.к. его не с чем сравнивать
            Comparable b = (Comparable)a.remove(i); // получаем элемент который будем вставлять и заодно удаляем его со старого места в листе
            int j = -1;
            int l = 0; // левая граница бинарного поиска
            int r = i; // правая граница
            while (l <= r) { // тут в цикле сам поиск, в котором собственно и проблема. описание проблемы см. после кода
                j = (l + r) / 2;
                if(b.compareTo( (Comparable) a.get(j) ) == 0) break;
                if(b.compareTo( (Comparable) a.get(j) ) > 0) l = j + 1;
                else r = j - 1;
            }
            a.add(j, b);
        }
        return;
    }

Так вот проблема такова - есть лист из N элементов. Их надо отсортировать вставкой. Во вставке есть место, где надо найти индекс куда вставлять элемент, так вот этот индекс надо найти при помощи бинарного поиска. Т.е. это уже не поиск получается, а что-то другое, т.к. необязательно, что в листе будет равный элемент.
Криво объяснил, но всё-же - как найти индекс куда вставлять элемент бинарным поиском, если искомый эдемент не обязательно сожержится в уже отсортированном листе?

На примере - есть у нас отсортированный рая чисел 1, 4, 5, 7, 10. Нам надо вставить туда 6 между 5 и 7. Индекс куда всявлять = 3. как найти этот индекс бинарным поиском. Вотъ. (примеры желательно на Java / C++, хотя и другие подойдут smile)


--------------------
.NET: WPF и Silverlight / Мой твиттер / Мой подкаст / Мой блог
PM MAIL WWW Skype   Вверх
LSD
Дата 16.9.2006, 12:57 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Leprechaun Software Developer
****


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

Репутация: 9
Всего: 538
Это учебная или реальная задача? Потому как в Java уже есть готовые классы и для сортировки и для бинарного поиска (кстати можно посмотреть их код). А приведеный код не очень эффективен с точки зрения производительности.


--------------------
Disclaimer: this post contains explicit depictions of personal opinion. So, if it sounds sarcastic, don't take it seriously. If it sounds dangerous, do not try this at home or at all. And if it offends you, just don't read it.
PM MAIL WWW   Вверх
Kefir
Дата 16.9.2006, 13:12 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


«Hakuna Matata»
***


Профиль
Группа: Комодератор
Сообщений: 1878
Регистрация: 25.1.2003
Где: Tampere, Suomi

Репутация: 2
Всего: 87
учебный. нас основам учат и вот задание такое дали. я бы сразу явовские методы заюзал, если бы не задание написать самому.


--------------------
.NET: WPF и Silverlight / Мой твиттер / Мой подкаст / Мой блог
PM MAIL WWW Skype   Вверх
LSD
Дата 16.9.2006, 13:26 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Leprechaun Software Developer
****


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

Репутация: 9
Всего: 538
Тогда вот бинарный поиск:
Код
  public static int binarySearch(Object[] a, int low, int high, int key)
  {
    while(low <= high)
    {
      int mid = (low + high) >> 1;
      Comparable midVal = (Comparable) a[mid];
      int cmp = midVal.compareTo(key);

      if(cmp < 0)
        low = mid + 1;
      else if(cmp > 0)
        high = mid - 1;
      else
        return mid;
    }
    return low;
  }

Возвращает или позицию элемента в списке, если он есть, или номер куда его надо вставить, соответсвенно элемент в этой позиции надо сдвинуть в конец списка.


--------------------
Disclaimer: this post contains explicit depictions of personal opinion. So, if it sounds sarcastic, don't take it seriously. If it sounds dangerous, do not try this at home or at all. And if it offends you, just don't read it.
PM MAIL WWW   Вверх
Kefir
Дата 16.9.2006, 14:11 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


«Hakuna Matata»
***


Профиль
Группа: Комодератор
Сообщений: 1878
Регистрация: 25.1.2003
Где: Tampere, Suomi

Репутация: 2
Всего: 87
My hero!  smile 
 smile  smile 


--------------------
.NET: WPF и Silverlight / Мой твиттер / Мой подкаст / Мой блог
PM MAIL WWW Skype   Вверх
  
 Ответ в темуСоздание новой темы Создание опроса
Правила форума "Центр помощи"

ВНИМАНИЕ! Прежде чем создавать темы, или писать сообщения в данный раздел, ознакомьтесь, пожалуйста, с Правилами форума и конкретно этого раздела.
Несоблюдение правил может повлечь за собой самые строгие меры от закрытия/удаления темы до бана пользователя!


  • Название темы должно отражать её суть! (Не следует добавлять туда слова "помогите", "срочно" и т.п.)
  • При создании темы, первым делом в квадратных скобках укажите область, из которой исходит вопрос (язык, дисциплина, диплом). Пример: [C++].
  • В названии темы не нужно указывать происхождение задачи (например "школьная задача", "задача из учебника" и т.п.), не нужно указывать ее сложность ("простая задача", "легкий вопрос" и т.п.). Все это можно писать в тексте самой задачи.
  • Если Вы ошиблись при вводе названия темы, отправьте письмо любому из модераторов раздела (через личные сообщения или report).
  • Для подсветки кода пользуйтесь тегами [code][/code] (выделяйте код и нажимаете на кнопку "Код"). Не забывайте выбирать при этом соответствующий язык.
  • Помните: один топик - один вопрос!
  • В данном разделе запрещено поднимать темы, т.е. при отсутствии ответов на Ваш вопрос добавлять новые ответы к теме, тем самым поднимая тему на верх списка.
  • Если вы хотите, чтобы вашу проблему решили при помощи определенного алгоритма, то не забудьте описать его!
  • Если вопрос решён, то воспользуйтесь ссылкой "Пометить как решённый", которая находится под кнопками создания темы или специальным флажком при ответе.

Более подробно с правилами данного раздела Вы можете ознакомится в этой теме.

Если Вам помогли и атмосфера форума Вам понравилась, то заходите к нам чаще! С уважением, Poseidon, Rodman
 
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Центр помощи | Следующая тема »

Подписаться на тему | Подписка на этот форум | Скачать/Распечатать тему


 




[ Время генерации скрипта: 0.0472 ]   [ Использовано запросов: 22 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
 По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.