0 / 0 / 1
Регистрация: 22.09.2012
Сообщений: 34
1

Реализация сортировки вставками

13.10.2012, 17:25. Показов 893. Ответов 3
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
На algolist нашёл исходник (вопросы после исходников):

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
template<class T>
void selectSort(T a[], long size) {
  long i, j, k; 
  T x;
 
  for( i=0; i < size; i++) {    // i - номер текущего шага
    k=i; x=a[i];
 
    for( j=i+1; j < size; j++)  // цикл выбора наименьшего элемента
      if (  a[j] < x ) {
        k=j; x=a[j];            // k - индекс наименьшего элемента
      }
 
    a[k] = a[i]; a[i] = x;      // меняем местами наименьший с a[i]
  }
}
Нашёл ещё и 2-ой вариант:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
void select_my(int nums[], int size){
    int i, j;     //управляющие переменные
    int minPtr;   //индекс минимального элемента в массиве
 
    for(i = 0; i < size - 1; i++){   //внешний цикл
        minPtr = i + 1;
        for(j = i + 2; j < size; j++)   //внутренний цикл
            if(nums[j] < nums[minPtr])
                minPtr = j;
        if(nums[minPtr] < nums[i])
            swap(nums[minPtr], nums[i]);
    }
}
Вот вопросы:
1. Мне кажется 1 - ый алгоритм написан некоректно, т.к. количество проходов внешнего цикла на 1 больше, чем надо. Во вторых , мне кажется там слишком много присваиваний? Правильно ли я думаю, что алгоритм написан плохо?
2. Правильно ли сделано, что внутренний цикл начинается с индекса i + 2?

3. Какой из этих исходников можно использовать? А какой отбросить?
Или искать другую реализацию?
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
13.10.2012, 17:25
Ответы с готовыми решениями:

Реализация алгоритма сортировки вставками
Мне нужно сделать лабу тема вверху... перед этим прочитал тему ...

Реализация сортировки двухпутевыми вставками (Pascal -> C++)
Добрый вечер. Помогите перевести корректно кусок кода на c++. Реализация сортировки двухпутевыми...

Демонстрация сортировки вставками
Библиотечный метод Продемонстрируйте работу метода сортировки вставками по возрастанию. Для этого...

Модификация сортировки вставками
Сама задача формулируется на скрине. П.5.18.Правил Запрещено размещать задания и решения в виде...

3
Эксперт С++
4727 / 2548 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
13.10.2012, 17:31 2
Цитата Сообщение от ogcjm Посмотреть сообщение
Мне кажется 1 - ый алгоритм написан некоректно, т.к. количество проходов внешнего цикла на 1 больше, чем надо.
ну исправьте сами (будет работать все равно правильно).

Цитата Сообщение от ogcjm Посмотреть сообщение
Во вторых , мне кажется там слишком много присваиваний?
можно было сделать и меньше (но сортировка все равно правильно выполняется).

Цитата Сообщение от ogcjm Посмотреть сообщение
равильно ли сделано, что внутренний цикл начинается с индекса i + 2?
правильно.

Цитата Сообщение от ogcjm Посмотреть сообщение
Какой из этих исходников можно использовать? А какой отбросить?
любой из приведенных правильный. Поэтому ответ: любой.

Цитата Сообщение от ogcjm Посмотреть сообщение
Или искать другую реализацию?
как хотите.
1
320 / 270 / 128
Регистрация: 24.05.2012
Сообщений: 629
13.10.2012, 17:41 3
C++
1
2
3
4
5
6
7
#include <algorithm>
 
template <typename T>
void SelectionSort(T a[ ], unsigned n) {
    for (unsigned i = 0; i < n - 1; i++)
        std::iter_swap(a + i, std::min_element(a + i, a + n));
}
Добавлено через 1 минуту
ogcjm, а чем Вас std::sort не устраивает?
1
0 / 0 / 1
Регистрация: 22.09.2012
Сообщений: 34
13.10.2012, 17:41  [ТС] 4
Цитата Сообщение от valeriikozlov Посмотреть сообщение
любой из приведенных правильный. Поэтому ответ: любой.
.
1.Про 2-ой алгоритм говорится на wikipedia ,что он неустойчивый?
2.Я имел ввиду под словом "правильный" более быстрый, пусть даже чуть чуть?
0
13.10.2012, 17:41
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
13.10.2012, 17:41
Помогаю со студенческими работами здесь

Алгоритм сортировки вставками
Привет, всем! В алгоритме непонятна одна строчка: #include&lt;iostream&gt; #include&lt;cstdlib&gt; ...

Реализовать шаблон сортировки двухпутевыми вставками
Помогите пожалуйста в решении нескольких задач: 1)Линейные списки (стек, очередь, линейный...

Продемонстрировать работу метода сортировки вставками по возрастанию
Помогите, прошу вас, вот есть задача: Продемонстрируйте работу метода сортировки вставками по...

Время работы сортировки вставками для разных размерностей массива
Друзья, подскажите: в чём проблема? Нужны временные показания работы сортировки с различными...

Отсортировать каждый из 4 массивов 4 способами сортировки (пузырьковая, вставками, пирамидальная, быстрая )
Собственно задание на скрине #include &quot;stdafx.h&quot; #include &lt;iostream&gt; #include &quot;math.h&quot; ...

Почему стандартная сортировка вектора std::sort намного быстрее сортировки вставками/пузырьком?
Здравствуйте, объясните, пожалуйста, как реализована std::sort. Ясно, что через итераторы, но...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru