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

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

Войти
Регистрация
Восстановить пароль
 
ogcjm
0 / 0 / 0
Регистрация: 22.09.2012
Сообщений: 34
#1

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

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

На 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. Какой из этих исходников можно использовать? А какой отбросить?
Или искать другую реализацию?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.10.2012, 17:25     Реализация сортировки вставками
Посмотрите здесь:

Реализация сортировки двухпутевыми вставками (Pascal -> C++) - C++
Добрый вечер. Помогите перевести корректно кусок кода на c++. Реализация сортировки двухпутевыми вставками. k:=(1+n) div 2; b:=a;...

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

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

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

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

Реализация алгоритмов сортировки - C++
Массив данных заполнять случайным образом. Рассмотреть массивы данных с элементов типа long и char. Использовать перезагрузку функций для...

Реализация сортировки выбором - C++
Есть одномерный массив, который необходимо отсортировать по возрастанию алгоритмом выбора и выводить на экран каждые изменения во время...

Реализация блочной сортировки файла - C++
Здравствуйте! Есть задача,как следствие ее нужно решить)) Я прекрасно знаю и понимаю,что никто за меня решать здесь не собирается.Но...

Программная реализация древесной сортировки - C++
Программная реализация древесной сортировки Указания: - использовать динамический массив - реализовать графическое представление...

Реализация алгоритма быстрой сортировки quickSort - C++
это алгоритм быстрой сортировки quickSort прошу напишите значение строк файл исходного кода qs.cpp : #include &quot;stdafx.h&quot;...


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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
valeriikozlov
Эксперт C++
4669 / 2495 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
13.10.2012, 17:31     Реализация сортировки вставками #2
Цитата Сообщение от ogcjm Посмотреть сообщение
Мне кажется 1 - ый алгоритм написан некоректно, т.к. количество проходов внешнего цикла на 1 больше, чем надо.
ну исправьте сами (будет работать все равно правильно).

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

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

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

Цитата Сообщение от ogcjm Посмотреть сообщение
Или искать другую реализацию?
как хотите.
Кот Ангенс
317 / 267 / 38
Регистрация: 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 не устраивает?
ogcjm
0 / 0 / 0
Регистрация: 22.09.2012
Сообщений: 34
13.10.2012, 17:41  [ТС]     Реализация сортировки вставками #4
Цитата Сообщение от valeriikozlov Посмотреть сообщение
любой из приведенных правильный. Поэтому ответ: любой.
.
1.Про 2-ой алгоритм говорится на wikipedia ,что он неустойчивый?
2.Я имел ввиду под словом "правильный" более быстрый, пусть даже чуть чуть?
Yandex
Объявления
13.10.2012, 17:41     Реализация сортировки вставками
Ответ Создать тему
Опции темы

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