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

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

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

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

03.07.2012, 19:04. Просмотров 655. Ответов 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? Или это в целом безразлично?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.07.2012, 19:04
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Сортировка вставкой (оцените) (C++):

Сортировка вставкой - C++
Всем привет. Задали задание написать код сортировки вставкой. Писал код по блок-схеме. Код получился нерабочий. Помогите найти ошибку. ...

Сортировка вставкой - C++
while(mc!=m) {nov=n; for(is=0;is&lt;n;is++){ for (i=nov;i&lt;n;i++){if (vmatr&lt;sk2){sk2=vmatr;c=i;}} nov++; if(sk2==vmatr){continue;} for...

Сортировка вставкой - C++
В файле input.txt содержатся сведения о группе студентов в формате:номер группы, фамилия, имя, год рождения, оценки по пяти предметам. ...

Сортировка вставкой - C++
(желательно ближе к си) Определить массив из 50 вещественных чисел: x = 10*Cos( i/10), i= 1, 2, . . . 50. Отсортировать массив по...

Сортировка вставкой - C++
1)Дан массив состоящий из n элементов (n&lt;=100) Отсортировать методом вставки и вывести пятый минимум. Добавлено через 1 час 42 минуты ...

Сортировка двухпутевой вставкой - C++
Народ, вот тут написал сортировку двухпутевой вставкой с разными вариантами ввода массива. Суть не в сортировке, она работает. Третий пункт...

3
zitxbit
88 / 740 / 75
Регистрация: 11.04.2012
Сообщений: 971
03.07.2012, 20:30 #2
Это вообще не сортировка вставками, - это сортировка выбором с обратным порядком итераций.

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

Добавлено через 15 минут
А так, все впорядке, правильный код.
0
Leomana
58 / 58 / 5
Регистрация: 29.06.2012
Сообщений: 188
03.07.2012, 20:40 #3
zitxbit, Вы что-то путаете. Сортировка написана правильно - это сортировка вставками
1
Лжец
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]
    }
И исходя из этого - у меня все-таки сортировка вставками, хотя я согласен, обе эти сортировки визуально достаточно похожи, но логика у них все же разная
0
03.07.2012, 21:25
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.07.2012, 21:25
Привет! Вот еще темы с ответами:

Сортировка двоичной вставкой - C++
Доброе время суток. Есть программа на pascal, выполняющая сортировку массива по убыванию, нужно переписать на с++. Программа на паскале...

Сортировка массива вставкой - C++
Доброго времени суток. У меня вот такая задача: Вариант 13; Задание на русском: 1) заполнить массив А(40) случайными целыми...

Методы сортировки: QuickSort и сортировка вставкой - C++
Помогите добавить сортировки в программу. Упорядочить по неубыванию массив структур по заданному ключу. Ключ: возраст. Методы...

Сортировка вставкой: объяснить ход действий - C++
помогите разобрать сами действия сортировки, что они значат Добавлено через 17 секунд int main() { int n = 10, i = 0, a=0; ...


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

Или воспользуйтесь поиском по форуму:
4
Ответ Создать тему
Опции темы

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