Форум программистов, компьютерный форум CyberForum.ru

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

Войти
Регистрация
Восстановить пароль
 
Лжец
31 / 31 / 3
Регистрация: 13.12.2011
Сообщений: 106
#1

Сортировка вставкой (оцените) - C++

03.07.2012, 19:04. Просмотров 636. Ответов 3
Метки нет (Все метки)

Доброго времени суток!

Прошу, оцените реализацию сортировки целочисленного массива методом вставки, есть ли какие-нибудь недостатки и на что стоит обратить внимание?

C++
1
2
3
4
5
6
7
8
9
10
11
12
for(int j=1; j<size; ++j){
 
  int key = arr[j];
  int i = j-1;
 
  while(i >= 0 && arr[i] > key){
    arr[i+1] = arr[i];
    i = i-1;
    arr[i+1] = key;
  }
 
}
В общем, очень хочется чтобы код по-пинал, кто-то знающий, заранее благодарю

Просто лично у меня есть сомнения в правильности использования объявления/инициализации автоматических переменных внутри цикла for, но с другой стороны делать их глобальными/внешними - вроде как неоправданно. Видел много различных реализаций в том числе и со вторым циклом for вместо while, не знаю, возможно это с чем-то связано, насколько вообще верно использовать цикл while или for? Или это в целом безразлично?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.07.2012, 19:04     Сортировка вставкой (оцените)
Посмотрите здесь:

C++ Сортировка двухпутевой вставкой
Сортировка вставкой C++
Сортировка вставкой по ключу в одномерном массиве C++
Сортировка вставкой C++
Сортировка двоичной вставкой C++
Методы сортировки: QuickSort и сортировка вставкой C++
C++ Сортировка вставкой
C++ Сортировка массива вставкой
Сортировка вставкой: объяснить ход действий C++
В чем ошибка? Ссртировка выбором и сортировка вставкой C++
C++ Сортировка вставкой

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
zitxbit
Master C/C++
87 / 739 / 75
Регистрация: 11.04.2012
Сообщений: 971
03.07.2012, 20:30     Сортировка вставкой (оцените) #2
Это вообще не сортировка вставками, - это сортировка выбором с обратным порядком итераций.

Добавлено через 52 секунды
сортировка вставками базируется на выполнении вставки элемента за элементом с большим или меньшим значением.

Добавлено через 15 минут
А так, все впорядке, правильный код.
Leomana
58 / 58 / 5
Регистрация: 29.06.2012
Сообщений: 188
03.07.2012, 20:40     Сортировка вставкой (оцените) #3
zitxbit, Вы что-то путаете. Сортировка написана правильно - это сортировка вставками
Лжец
31 / 31 / 3
Регистрация: 13.12.2011
Сообщений: 106
03.07.2012, 21:25  [ТС]     Сортировка вставкой (оцените) #4
Цитата Сообщение от zitxbit Посмотреть сообщение
Это вообще не сортировка вставками, - это сортировка выбором с обратным порядком итераций.
Эм, вот это новость Я вот, сейчас даже пересмотрел вот эту тему в шапке форума:

Алгоритмы сортировок

Там сказано следующее:

Это сортировка вставками:
C++
1
2
3
4
5
6
7
    for (int i = 1, j; i < size; ++i) // цикл проходов, i - номер прохода
    {
        tmp = a[i]; 
        for (j = i - 1; j >= 0 && a[j] > tmp; --j) // поиск места элемента в готовой последовательности 
            a[j + 1] = a[j];    // сдвигаем элемент направо, пока не дошли
        a[j + 1] = tmp; // место найдено, вставить элемент    
    }
Это сортировка выбором:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
  for(i = 0; i < size; ++i) // i - номер текущего шага
    { 
        pos = i; 
        tmp = arr[i];
        for(j = i + 1; j < size; ++j) // цикл выбора наименьшего элемента
        {
            if (arr[j] < tmp) 
            {
               pos = j; 
               tmp = arr[j]; 
            }
        }
        arr[pos] = arr[i]; 
        arr[i] = tmp; // меняем местами наименьший с a[i]
    }
И исходя из этого - у меня все-таки сортировка вставками, хотя я согласен, обе эти сортировки визуально достаточно похожи, но логика у них все же разная
Yandex
Объявления
03.07.2012, 21:25     Сортировка вставкой (оцените)
Ответ Создать тему
Опции темы

Текущее время: 19:35. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru