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)), что существенно меньше сложности простых алгоритмов сортировки.


 

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

30408. Неолитическая революция. Динамика развития цивилизации, этапы ее развития на историческом примере 33.35 KB
  Падают темпы роста производительности общественного труда разражается новый кризис завершающий фазу зрелости. В основе прогресса лежали ступени общественного разделения труда сделавшие возможным производство прибавочного продукта. Выделение скотоводов и земледельцев →новые орудия труда обмен продуктами труда. Признаки кризиса: недостаток орудий труда зависимость от источников сырья падение производительности труда и численности населения сложившаяся система экономических отношений не удовлетворяла запросы производителей...
30409. Переходный период цивилизаций: основные этапы и итоги 30.38 KB
  В духовной сфере зарождаются новые открытия экономические общественно-политические теории. Формируются новые технологии. Механизмы старой цивилизации рушатся а новые еще не установлены. Во время перехода на всех этажах пирамиды сталкиваются старые и новые.
30410. Переходный этап в развитии цивилизации на историческом примере перехода от неолитической к раннеклассовой 28.5 KB
  Переходный этап в развитии цивилизации на историческом примере Переходный период от неолитической к раннеклассовой глобальной цивилизации на примере древних обществ Междуречья Уже в 4тыс. Достижения неолитической цивилизации позволили шумерам увеличить свою численность а с конца 4 тыс.о к началу 3 тыс. В первой половине 3 тыс.
30411. Основные особенности и достижения глобальной неолитической цивилизации 32.9 KB
  Произошла неолитическая катастрофа т. Неолитическая революция переход от эпизодического выращивания злаков и приручения животных к регулярному воспроизводству продуктов питания на основе земледелия и скотоводства т. Неолитическая революция положила начало формированию неолитической цивилизации и всей человеческой цивилизации в целом. Неолитическая революция предложила два выхода: 1.
30412. Методы ценообразования в туризме 45.5 KB
  количество отправлений туристов достич нулевую рентабельность работать не в убыток определить истинную цену тура рассчитать норму прибыли. Издержки бывают: Постоянные не зависят от объема работы ТО аренда зарплата коммунальные платежи интернет Переменные они меняются от тура к туру и зависят от объема работы ТО. неизвестно скольуо человек будет в группе Стоимость тура для сопровождающего Стоимость обслуживания тура это затраты рабочего времени сотрудников фирмы и денежные расходы на организацию продаж Норма прибыли...
30413. Основные направления инновации в туризме 38 KB
  большая часть инноваций в туризме связанна с инновациями в транспорте. Другим направлением инноваций в туризме являются информационные технологии которые позволяют решать большинство проблем по бронированию туров способствует более эффективной работе фирм.
30414. Сегментация туристского рынка 41.5 KB
  Обычно выделяют: А ВИП клиенты Б Туркласс В Эконом класс Эти группы определяются в каждом регионе по своему т. Члены фокусгруппы должны иметь одинаковые потребности и возможности. Члены фокусгруппы должны быть активными покупателями туристических услуг и не охвачены конкурентами.
30415. Статистическая информация 39 KB
  Характерной особенностью статистической информации являются: Массовость Периодичность Получение и обработка Возможность хранения Статистическую информацию принято классифицировать: По принадлежности к отраслям экономики статистика туризма По месту возникновения государственная статистика статистика конкретного предприятия По периодичности ежегодная ежеквартальная Статистика туризма исследует информацию которая характеризует все процессы происходящие в туристической индустрии.