36546

Алгоритмы обработки одномерных массивов.Сортировка.Сравнить 2 метода

Доклад

Информатика, кибернетика и программирование

Первый шаг сортировки методом пузырька 1Сравниваем первый и второй элементы массива. 2Сравниваем второй и третий элементы массива. 3Cравниваем предпоследний N1 и последний N элементы массива. Повторяем вышеуказанные действия для части массива начиная с 1 позиции до N1 шаг 2.

Русский

2013-09-22

30 KB

2 чел.

Алгоритмы обработки одномерных массивов.Сортировка.Сравнить 2 метода

Метод пызырька.

Основная идея сортировки (например, по возрастанию) методом пузырька очень простая. Предположим, что у нас N элементов в массиве и индекс каждого элемента лежит в промежутке от 1 до N.

Первый шаг сортировки методом пузырька

1)Сравниваем первый и второй элементы массива. Если первый элемент больше, чем второй, то меняем их местами.

2)Сравниваем второй и третий элементы массива. Если второй элемент больше, чем третий, то меняем их местами.

3)Cравниваем предпоследний (N-1) и последний (N) элементы массива. Если предпоследний элемент больше, чем последний, то меняем их местами.

В результате самым последним элементом в массиве у нас окажется самый большой элемент.

Повторяем вышеуказанные действия для части массива, начиная с 1 позиции до N-1 (шаг 2).

Второй шаг сортировки методом пузырька

1(Сравниваем первый и второй элементы массива. Если первый элемент больше, чем второй, то меняем их местами.

2(Сравниваем второй и третий элементы массива. Если второй элемент больше, чем третий, то меняем их местам

3)Cравниваем элемент N-2 и элемент N-1 массива. Если (N-2)-й элемент больше, чем элемент N-1, то меняем их местами.

В результате предпоследний элемент в массиве у нас тоже будет на своем, "отсортированном" месте.

Метод включения

Одним из наиболее простых и естественных методов внутренней сортировки является сортировка с простыми включениями. Идея алгоритма очень проста. Пусть имеется массив ключей a[1], a[2], ..., a[n]. Для каждого элемента массива, начиная со второго, производится сравнение с элементами с меньшим индексом (элемент a[i] последовательно сравнивается с элементами a[i-1], a[i-2] ...) и до тех пор, пока для очередного элемента a[j] выполняется соотношение a[j] > a[i], a[i] и a[j] меняются местами. Если удается встретить такой элемент a[j], что a[j] <= a[i], или если достигнута нижняя граница массива, производится переход к обработке элемента a[i+1] (пока не будет достигнута верхняя граница массива).

Легко видеть, что в лучшем случае (когда массив уже упорядочен) для выполнения алгоритма с массивом из n элементов потребуется n-1 сравнение и 0 пересылок. В худшем случае (когда массив упорядочен в обратном порядке) потребуется n?(n-1)/2 сравнений и столько же пересылок. Таким образом, можно оценивать сложность метода простых включений как O(n2).

Дальнейшим развитием метода сортировки с включениями является сортировка методом Шелла, называемая по-другому сортировкой включениями с уменьшающимся расстоянием. Мы не будем описывать алгоритм в общем виде, а ограничимся случаем, когда число элементов в сортируемом массиве является степенью числа 2. Для массива с 2n элементами алгоритм работает следующим образом. На первой фазе производится сортировка включением всех пар элементов массива, расстояние между которыми есть 2(n-1). На второй фазе производится сортировка включением элементов полученного массива, расстояние между которыми есть 2(n-2). И так далее, пока мы не дойдем до фазы с расстоянием между элементами, равным единице, и не выполним завершающую сортировку с включениями. Применение метода Шелла к массиву, используемому в наших примерах, показано в таблице 2.2.

В общем случае алгоритм Шелла естественно переформулируется для заданной последовательности из t расстояний между элементами h1, h2, ..., ht, для которых выполняются условия h1 = 1 и h(i+1) < hi. Дональд Кнут показал, что при правильно подобранных t и h сложность алгоритма Шелла является O(n(1.2)), что существенно меньше сложности простых алгоритмов сортировки.


 

А также другие работы, которые могут Вас заинтересовать

50011. Методы оценки надежности конструкций 260.5 KB
  Он заключался в том что для любого волокна конструкции должно было выполняться условие k S Sдоп где Sдоп допускаемое напряжение; S напряжение в волокне определяемое методами строительной механики; k коэффициент запаса. В этом методе коэффициент запаса для всех конструкций из данного материала был одинаков что не отвечало фактической работе таких комплексных материалов какими являются железобетон и каменная кладка компоненты которых имеют различные механические характеристики и в соответствии с этим в различной степени и с...
50013. ИНФОРМАЦИОННЫЙ ПОТОК 26.5 KB
  Это особенно заинтересовано обеспокоено окончательным использованием этой информации или как основание для решения или действия или как ввод к другой системе или деятельность inhere немного сомнения что успех специфического приложения зависит тяжело от полного знания информационного потока в течение стадии планирования. Характеристики информации Хотя мы передаем информацию в некоторой физической форме напечатанные слова звуки ударил кулаком платы информация непосредственно Не материален. Даже при том что мы не можем видеть или...
50014. ВИЗНАЧЕННЯ СТАЛОЇ СТЕФАНА–БОЛЬЦМАНА 205 KB
  Прилади і матеріали Оптичний пірометр із зникаючою ниткою електрична лампочка розжарення регулятор напруги ватметр блок живлення пірометра акумуляторна батарея В даній лабораторній роботі для знаходження сталої СтефанаБольцмана застосовується метод порівняння потужності електричного струму яка витрачається на розжарення вольфрамової нитки електричної лампочки і потужності теплового випромінювання з поверхні цієї нитки. Прилади для вимірювання температури нагрітих тіл за інтенсивністю їх теплового випромінювання в оптичному...
50016. Анализ пропускной способности каналов систем электрической связи 61 KB
  Расчет учебного времени № п п Учебные вопросы занятия Время мин I. Методические рекомендации преподавателю по подготовке и проведению практического занятия Методическая разработка занятия предназначена для преподавателе проводящих занятия с курсантами обучающимся по специальности Эксплуатация многоканальных телекоммуникационных систем средств и комплексов и...
50017. Анализ пропускной способности каналов систем электрической связи 61.5 KB
  Анализ пропускной способности дискретного канала. На основе изученных на предыдущих занятиях и самостоятельной работе пропускной способности дискретного канала и инженерных методов расчета ее в среде MthCD произвести расчет и анализ пропускной способности дискретного канала. Пропускная способность дискретного mичного канала определяется выражением: где: V скорость модуляции [Бод] p вероятность ошибки сигналов в канале m число вариантов кодовых символов основание кода например m=2 4 8 16 . Пропускная способность двоичного...
50018. Кодирование сообщений 217.5 KB
  Анализ пропускной способности дискретного канала. Анализ пропускной способности непрерывного канала. Задание и указания обучающимся по подготовке к выполнению практического занятия На самостоятельной работе повторить: количество информации переданной по дискретному и непрерывному каналам...
50019. Теория передачи информации 62 KB
  Расчет пропускной способности дискретного канала. На основе изученных на предыдущих занятиях и самостоятельной работе пропускной способности дискретного канала и инженерных методов расчета ее в среде MthCD произвести расчет и анализ пропускной способности дискретного канала. Пропускная способность дискретного mичного канала определяется выражением: где: V скорость модуляции [Бод] p вероятность ошибки сигналов в канале m число вариантов кодовых символов основание кода например m=2 4 8 16 . Пропускная способность двоичного...