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

Алгоритмы сортировки: прямые, улучшенные (Сортировка с помощью прямого включения (метод простых вставок))

26.02.2013, 10:24. Показов 4607. Ответов 1
Метки нет (Все метки)

Задание 1.

Сортировка с помощью прямого включения (метод простых вставок).

Методические указания к выполнению задания 1
Описать алгоритм сортировки. Проанализировать его эффективность. Написать программу сортировки данных с использованием указанного алгоритма.

Зарание большое спасибо за помощь.
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
26.02.2013, 10:24
Ответы с готовыми решениями:

Сравнение методов сортировки массивов: метод прямого включения и Шелла
Задание: Написать учебно-демонстрационную программу, которая сравнивает методы прямого включения и...

Сравнительный анализ Методов Сортировки(метод прямого выбора,метод слиянием,сортировка подсчетом)
Ввод данных: 1. с клавиатуры, 2.с файла (C:\Users\'NAME'\Desktop), 3.случайным образом количество...

Сравнение быстрого и прямого включения методов сортировки
Есть массив, размер которого задает пользователь. Затем этот массив копируется на две одинаковые...

Написать программу сортировки методом простых вставок
Написать программу сортировки методом простых вставок элементов массива, имеющих четные индексы.

1
...
1804 / 1268 / 935
Регистрация: 12.02.2013
Сообщений: 2,063
26.02.2013, 19:02 2
Лучший ответ Сообщение было отмечено Neigi как решение

Решение

Цитата Сообщение от Neigi Посмотреть сообщение
Проанализировать его эффективность.
Мне вот интересно как можно проанализировать его эффективность если не сравнивать с другими алгоритмами? Ведь всё познаётся в сравнении.

Программа генерирующая текстовый файл со случайными числами:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <ctime>
 
int main(int argc, const char* argv[])
{
   srand(time(NULL));
 
   if (argc != 3)
   {
      std::cerr << "Usage: program <file.txt> <count>" << std::endl;
      system("PAUSE");
      return EXIT_FAILURE;
   }
 
   int count = atoi(argv[2]);
 
   std::ofstream f(argv[1]);
 
   if (!f.is_open())
   {
      std::cerr << "Error: file " << argv[1] << " not opened ..." << std::endl;
      return EXIT_FAILURE;
   }
 
   for (; count; --count)
   {
      int value = (rand() << 16) + rand();
      f << value << std::endl;
   }
 
   f.close();
 
   return EXIT_SUCCESS;
}
Использование:
Код
$ program.exe <file.txt> <count>
где, <file.txt> - файл в который заносятся числа, а <count> - количество чисел.

Сама программа:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <iostream>
#include <fstream>
#include <iomanip>
#include <string>
#include <vector>
#include <cstdlib>
#include <ctime>
 
bool LoadData(const std::string& fname, std::vector<int>& array, int count)
{
   std::ifstream f(fname.c_str());
 
   if (!f.is_open())
   {
      return false;
   }
 
   if (count == -1)
   {
      count = 0x7FFFFFFF;
   }
 
   int value;
   array.clear();
   for (; count && !f.eof(); --count)
   {
      f >> value;
      array.push_back(value);
   }
 
   f.close();
 
   return true;
}
 
void Swap(int& a, int& b)
{
   int tmp = a;
   a = b;
   b = tmp;
}
 
void Sort(std::vector<int>& array)
{
   for (unsigned i = 1; i < array.size(); ++i)
   {
      for (unsigned j = i; (j > 0) && (array[j] < array[j-1]); --j)
      {
         Swap(array[j], array[j-1]);
      }
   }
}
 
int main(int argc, const char* argv[])
{
   if (argc != 2)
   {
      std::cerr << "Usage: program <file.txt>" << std::endl;
      system("PAUSE");
      return EXIT_FAILURE;
   }
 
   std::vector<int> array;
   int count = -1;
 
   std::cout << "   count  |  clock    " << std::endl;
   std::cout << "----------+-----------" << std::endl;
 
   while (LoadData(argv[1], array, count) && count)
   {
      clock_t start = clock();
      Sort(array);
 
      std::cout << std::setw(10) << array.size() << "|"
                << std::setw(10) << clock() - start
                << std::endl;
 
      count = array.size() / 2;
   }
 
   return EXIT_SUCCESS;
}
Использование:
Код
$ program.exe <file.txt>
где, <file.txt> - файл с числами.

Результат выполнения представлен в виде таблицы:
Алгоритмы сортировки: прямые, улучшенные (Сортировка с помощью прямого включения (метод простых вставок))


Первая колонка - количество элементов, вторая колонка - время в миллисекундах.

Исходники + бинарники: program.7z

Некоторые пояснения:
  • файл используется для того, чтобы можно было анализировать выполнение алгоритма при статических значениях;
  • работу с файлом и загрузкой данных в вектор можно было сделать намного эффективней, но в рамках задачи это не столь важно.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
26.02.2013, 19:02
Помогаю со студенческими работами здесь

Сортировка нечисловой последовательности методом включения (простых вставок)
Помогите, пожалуйста, составить программу, выполняющую следующие операции: 1. ввод с клавиатуры...

Сортировка методом прямого включения ( исправление метода сортировки )
Условие: Сгенерируйте случайным образом 20 целых чисел и поместите их в типизированный файл. ...

Отсортировать массив тремя методами: прямого включения, прямого обмена, быстрой сортировки
Есть программа которая сортирует массив из 100 элементов в диапазоне от 1 до 1000. Программа...

Алгоритмы сортировки обменом (метод «пузырька», челночная сортировка)
Сортировка данных. Алгоритмы сортировки обменом (метод «пузырька», челночная сортировка). Сравнение...


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

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

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