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

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

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

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

13.10.2012, 17:25. Просмотров 531. Ответов 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     Реализация сортировки вставками
Посмотрите здесь:

Реализация блочной сортировки файла C++
C++ Реализовать шаблон сортировки двухпутевыми вставками
C++ Работа с табличными базами данных. Реализация функции сортировки.
C++ Реализация сортировки выбором
Программная реализация древесной сортировки C++
C++ Реализация алгоритма сортировки вставками
Реализация алгоритмов сортировки C++
C++ Реализация сортировки двухпутевыми вставками (Pascal -> C++)
Написать программу: реализация методов сортировки C++
C++ Реализация алгоритма быстрой сортировки quickSort
C++ Реализация алгоритма пузырьковой сортировки
C++ Алгоритм сортировки вставками

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
valeriikozlov
Эксперт C++
4663 / 2489 / 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     Реализация сортировки вставками
Ответ Создать тему
Опции темы

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