|
|
|
сделать стартовой | добавить в избранное |
 |
|
Сортировка массива методом Шелла |
Забавная пачка "5000 дублей". 
Ручка "Шприц", желтая. 
Пакеты с замком "Extra зиплок" (гриппер), комплект 100 штук (150x200 мм). Отчёт по практике Выполнили: cт.гр. 97ЭЭ3 Толмач М., Ерегин П., Синева Т. Пензенский государственный университет, Кафедра "Экономическая кибернетика" Пенза 1998 г. Задание Цель работы: изучить метод Шелла для сортировки строкового массива и применить этот метод на практике. Заданием на практическую работу является разработка программы на языке программирования Borla d С v.3.1. для сортировки массива строк по их индексному значению. Значения элементов массива и их индексы задаются пользователем с клавиатуры. Введение В настоящее время индустрия производства компьютеров и программного обеспечения для них является одной из наиболее важных сфер экономики развитых стран. Ежегодно в мире продаются десятки миллионов компьютеров. Только в США объем продаж компьютеров составляет десятки миллионов долларов и постоянно продолжает расти. В чем же причины такого стремительного роста индустрии персональных компьютеров и их сравнительная выгодность для многих деловых применений? Простота использования, обеспеченная с помощью диалогового способа взаимодействия с компьютером. Относительно высокие возможности по переработке информации, наличие программного обеспечения, а так же мощных систем для разработки нового программного обеспечения. Язык С - универсальный язык общего назначения, область приложений которого - программирование систем в самом широком смысле. Кроме этого, С успешно используется как во многих приложениях, так и в мощных операционных системах. 1 Входные данные Входными данными в программе является число элементов массива, значение индекса каждого элемента и строковые элементы массива. Все эти данные вводятся пользователем с клавиатуры по запросу программы. Число элементов массива не должно превышать 32767. Индексы элементов массива должны быть целочисленными значениями. 2 Выходные данные Выходными данными в программе является исходный и отсортированный методом Шелла массив, которые выводятся на экран по запросу пользователя. 3 Архитектура программы Данная программа разработана на языке программирования С и состоит из следующих функциональных модулей: 1) me u - обработчик меню; 2) i pu - ввод данных; 3) ou pu - вывод данных; 4) sor - сортировка Шелла; 5) Основная программа. 1.Функция me u: Осуществляет вывод на экран меню , опрос клавиатуры в бесконечном цикле и передвижение цветного курсора по пунктам меню. При нажатии клавиши ‘Esc’ возвращает -1, при нажатии клавиши с номером пункта меню возвращает этот номер, при нажатии клавиши ‘E er’ возвращает номер текущего пункта меню. Параметры для вызова функции me u: x,y – координаты меню на экране, cap – содержимое меню. 2.Функция i pu : Осуществляет ввод индексов и элементов массива с клавиатуры, возвращает количество введенных элементов. Параметры для вызова функции mas[] –указатель на массив, s – номер первого вводимого элемента. 3.Функция ou pu : Осуществляет вывод содержимого массива на экран. Параметры для вызова функции mas[] –указатель на массив, um – число элементов массива. 4.Функция sor : Осуществляет сортировку массива по индексам элементов методом Шелла. Сортировка методом Шелла заключается в следующем: сначала отдельно группируются и сортируются элементы, отстоящие друг от друга на расстоянии 9.
После первого прохода элементы перегруппировываются и вновь сортируются элементы, отстоящие друг от друга на расстоянии 5, затем сортируются элементы,. отстоящие друг от друга на расстоянии 3, и наконец , на четвертом проходе идет обычная или одинарная сортировка. Параметры для вызова функции mas[] –указатель на массив, um – число элементов массива. 5. Основная программа: Осуществляет установку цветов, очистку экрана, вызов, функции обработки меню и в зависимости от возвращенного значения вызов одной из следующих функций: i pu , ou pu , sor . Список литературы 1. Вирт Н. Алгоритмы и структуры данных: Пер с англ. -М.: Мир,1989. - 360 с., ил. 2.Бьярн Страуструп. Язык программирования С . в двух частях. Пер. с англ. Киев:"ДиаСофт",1993.-296 с. ил. ПРИЛОЖЕНИЕ 1 Распечатка программы #i clude &l ;s dio.h> #i clude &l ;s dlib.h> #i clude &l ;co io.h> #i clude &l ;s ri g.h> // Данные одного элемента массива s ruc o e elem { i ; // Индекс char s ; // Данные }; // Обработка меню i me u(i x,i y,char cap ); // Ввод данных i i pu (o e elem mas[],i s ); // Вывод данных void ou pu (o e elem mas[],i um); // Сортировка Шелла void sor (o e elem mas[],i um); // Обработка меню i me u(i x,i y,char cap ) { i ,m; // Счетчики i um; // Количество пунктов i k; // Выбранный пункт char p ; // Временный указатель на символ char c; // Считанный с клавиатуры символ // Вычисляем количество пунктов um=s rle (cap )/20; // Курсор на нулевой элемент k=0; // Бесконечный цикл обработки for (;;) { // Вывод меню p =cap ; for ( =0; &l ; um; ) { go oxy(x,y ); // Закраска пункта, на который указывает курсор if ( ==k) { // Закраска ex backgrou d(12); ex color(14); } else { // Нормальный ex backgrou d(3); ex color(1); } cpri f("%d) ", 1); for (m=0;m&l ;20;m ) cpri f("%c", (p )); } ex backgrou d(3); ex color(1); // Опрос клавиатуры c=ge ch(); if (!c) c=ge ch(); // Проверка, не нажата ли клавиша с цифрой if (((c-'1')>=0)&&((c-'1')&l ; um)) { // Установка указателя в зависимости от нажатой цифры k=c-'1'; // Запись в буфер клавиатуры символа E ER u ge ch(13); } else { // Анализ swi ch(c) { // Вверх case (72): if (k>0) k--; else k= um-1; break; // Вниз case (80): if (k&l ;( um-1)) k ; else k=0; break; // Выход по ESC - возвращается -1 case (27): re ur -1; // Выход по E ER - возвращается номер пункта case (13): re ur k; } } } } // Ввод данных // Возвращаемое значение - количество введенных элементов // Входные параметры - указатель на массив и номер первого вводимого элемента i i pu (o e elem mas[],i s ) { clrscr(); // Очистка массива i x; // Индекс i um; // Количество введенных элементов i ; // Счетчик char a; // Данные // Ввод количества элементов pri f(" Число вводимых элементов: "); sca f("%d",& um); pri f(" Вводите строчки формата X: Слово "); // Ввод элементов for ( =0; &l ; um; ) { sca f("%d:%s",&x,a); mas.s ,a); }; re ur um; } // Вывод массива // Входные параметры - указатель на массив и количество элементов void ou pu (o e elem mas[],i um) { clrscr(); i ; // Счетчик pri f(" Содержимое массива: "); pri f(" Индекс Содержимое "); // Вывод элементов for ( =0; &l ; um; ) pri f("%5d %s ",mas.s
); // Ожидание ESC go oxy(1,24); pri f(" Нажмите ESC для продолжения . "); while (ge ch()!=27); } // Сортировка Шелла void sor (o e elem mas={9,5,3,1}; // Шаги сортировки i fs,m ,p; // Первый, минимальный и текущий элементы i ; // Счетчик o e elem prm; // Временная переменная // Цикл сортировки for ( =0; &l ;4; ) { fs=0; // Начинать сортировать с начала // Перебор всего массива while (fs&l ; um) { // Поиск минимального элемента p=fs; m =fs; while (p&l ; um) { if (mas; } // Если минимальный элемент отличается от начального, поменять их местами if (m >fs) { prm. =mas. =mas. =prm. ; s rcpy(mas; // Переход к следующему элементу } } } // Основная программа void mai () { o e elem mas; // Массив i um; // Количество элементов i s ; // Выбранный пункт меню ex backgrou d(0); ex color(15); clrscr(); do { // Вывод меню s =me u(30,5," Ввод данных " " Добавление данных " " Вывод данных " " Сортировка Шелла " " Выход из программы " "x0"); ex backgrou d(0); ex color(15); // Выполнение действий в зависимости от выбранного пункта swi ch(s ) { // Ввод данных case (0): um=i pu (mas,0); break; // Добавление данных case (1): um =i pu (mas, um); break; // Вывод массива case (2): ou pu (mas, um); break; // Сортировка case (3): sor (mas, um); break; } // Выход по ESC или последнему пункту } while ((s &l ;4)&&(s !=-1)); clrscr(); } ПРИЛОЖЕНИЕ 2 Результаты работы программы Меню: 1) Ввод данных 2) Добавление данных 3) Вывод данных 4) Сортировка Шелла 5) Выход из программы 1) Ввод данных: Число вводимых элементов: 8 Вводите строчки формата X: Слово 0:sig 1001:else 3000:yes 1535:bu 1:pas 412:cell 99:aler 2888:objec 3) Вывод данных: Содержимое массива: Индекс Содержимое 0 sig 1001 else 3000 yes 1535 bu 1 pas 412 cell 99 aler 2888 objec Нажмите ESC для продолжения . 2) Добавление данных: Число вводимых элементов: 1 Вводите строчки формата X: Слово 10000:hello 4) Сортировка Шелла 3) Вывод данных: Содержимое массива: Индекс Содержимое 0 sig 1 pas 99 aler 412 cell 1001 else 1535 bu 2888 objec 3000 yes 10000 hello Нажмите ESC для продолжения . 5) Выход из программы ПРИЛОЖЕНИЕ 3 Блок–схема алгоритма программы
В то же время, избавляя программиста от необходимости задумываться о низкоуровневом распределении памяти, в котором нуждаются алгоритмы, они невольно создают предпосылки для написания неэффективного кода. Неэффективность кода может быть обусловлена причинами двоякого рода: 1. Вычислительная неэффективность алгоритма. Этот вид неэффективности наблюдается в тех случаях, когда спроектированный вами алгоритм предусматривает интенсивные вычисления или выполнение большего количества циклов, чем это объективно необходимо, от чего можно было бы избавиться, используя более эффективные алгоритмы. В качестве классического примера можно привести сортировку массива данных. Иногда у вас может появляться возможность выбирать между несколькими возможными вариантами алгоритмов сортировки, отдельными частными случаями которых могут, например, быть алгоритмы "порядка N" (линейная зависимость времени вычислений от количества сортируемых элементов), "порядка N*Log(N)" (зависимость времени вычислений от количества сортируемых элементов отличается от линейной, но остается все же лучшей, чем экспоненциальная) или "порядка N^2" (экспоненциальная зависимость времени вычислений от количества сортируемых элементов)
1. Сортировка массивов методом вставок
2. Сортировка данных в массиве
3. Методы мониторинга короткопериодных деформаций массива горных пород
4. Методы работы с массивами на языке BASIC
9. Массивы в языках Pascal и Basic
10. Электронное устройство счета и сортировки
11. Электронное устройство счета и сортировки
12. Твердые бытовые отходы (ТБО), их складирование, сепарация и сортировка по группам
14. Быстрые алгоритмы сортировки
16. Массивы
Подвесные качели "Тарзанка". 
Велосипед трехколесный. 
Магнитная мозаика "Техника". 17. Модуль для работы с ассоциативными массивами в C++ Builder
18. Массивы в языках Pascal и Basic
19. Интервальные типы данных. Оператор TYPE. Массивы
20. Простейшие бифункциональные природные соединения - мостик к массиву природных соединений
21. Лесные массивы и их значение в экономике Японии
27. Обработка массивов данных в среде Turbo Pascal
28. Работа над массивами с помощью языка С++
29. Разработка систем хранения информации на RAID-массивах
30. Выражения и условный оператор IF. Операторы циклов. Массивы и подпрограммы
31. Выявление функциональной зависимости в массиве данных
32. Механизация и автоматизация работ по контролю и сортировке деталей
Швабра для пола, с отжимом. 
Игра "Городки". 
Конструктор "Цветной", 65 деталей. 33. Проектирование системы электроснабжения для жилого массива
35. Изучение миксомицетов среднего Урала, выращенных методом влажных камер
36. Методы исследования в цитологии
37. МЕТОДЫ ИЗУЧЕНИЯ ЭВОЛЮЦИИ ЧЕЛОВЕКА
41. Статистика населения. Методы анализа динамики и численности и структуры населения
42. Гамма – каротаж. Физические основы метода
44. Методы выделения мономинеральных фракций
45. Основні методи боротьби з інфляцією
46. Предмет, метод, источники Административного права
47. Методы осуществления государственной власти
48. Метод гражданско правового регулирования
Настольная игра "Юный Свинтус" (новая версия). 
Спиннер трехлучевой "Элит", перламутровый (в железной квадратной коробке). 
Самоклеящиеся этикетки, A4, 210x297 мм. 49. Формы и методы государственного регулирования экономики в Казахстане
50. Математические методы и модели в конституционно-правовом исследовании
51. Методы комплексной оценки хозяйственно-финансовой деятельности
52. Цикл-метод обучения. (Методика преподавания эстонского языка)
53. Эффективные методы изучения иностранных языков
57. Концепция поэта и поэзии П.Б.Шелли
58. Mozart: Symphony #40 in G Minor, K.550 Моцарт: Симфония №40 в си-минор, К. 550
59. Цивилизационные методы в изучении истории
60. Методы компьютерной обработки статистических данных. Проверка однородности двух выборок
61. Методичка по Internet Explore
63. Разработка методов определения эффективности торговых интернет систем
Копилка "Лаванда", 16x21 см. 
Набор детской посуды "Авто", 3 предмета. 
Диванчик раскладной "Кошечка". 65. Метод деформируемого многогранника
66. Обучение начальных курсов методам программирования на языке Turbo Pascal
68. Модифицированный симплекс-метод с мультипликативным представлением матриц
69. Методы приобретения знаний в интеллектуальных системах
73. Интегрирование методом Симпсона
74. Защита цифровой информации методами стеганографии
79. Численные методы. Двойной интеграл по формуле Симпсона
80. Численные методы
Бусы-прорезыватели "Фруктовый микс". 
Трикотажная пеленка кокон "Bambola" (цвет: розовый). 
Универсальный бокс, средний (3 секции). 82. Метод конечных разностей или метод сеток
83. "Комплект" заданий по численным методам
84. Аксиоматический метод. Логическое строение геометрии
85. Расчет дифференциального уравнения первого, второго и третьего порядка методом Эйлера
89. РЕШЕНИЕ СИСТЕМ ЛИНЕЙНЫХ ДИФФЕРЕНЦИАЛЬНЫХ УРАВНЕНИЙ ПЯТИТОЧЕЧНЫМ МЕТОДОМ АДАМСА – БАШФОРТА
90. Вычисление интегралов методом Монте-Карло
91. Построение решения задачи Гурса для телеграфного уравнения методом Римана
92. СИНГУЛЯРНОЕ РАЗЛОЖЕНИЕ В ЛИНЕЙНОЙ ЗАДАЧЕ МЕТОДА НАИМЕНЬШИХ КВАДРАТОВ
93. Методы и приемы решения задач
94. Приближенный метод решения интегралов. Метод прямоугольников (правых, средних, левых)
95. Вычислительные методы алгебры (лекции)
96. Решение транспортной задачи методом потенциалов
Гель для укрепления зубов R.O.C.S. "Medical Minerals" для детей и подростков, со вкусом клубники, 45. 
Кино-хлопушка. 
Папка для тетрадей "Чемпионат мира по футболу 2018. Талисман", красная, А4. 97. Составление и решение нестандартных уравнений графоаналитическим методом
98. Некоторые дополнительные вычислительные методы
99. Метод прогонки решения систем с трехдиагональными матрицами коэффициентов
