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


 

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

82273. Вненаучное социальное знание. Взаимодействие социальных, гуманитарных наук и вненаучного знания в экспертизах социальных проектов и программ 39.26 KB
  Взаимодействие социальных гуманитарных наук и вненаучного знания в экспертизах социальных проектов и программ. Эйнштейн ищут основания знания в философии и художественной литературе. Антифундаменталистская тенденция просматривается в истолковании всех важнейших областей научного познания: математического естественнонаучного гуманитарного. В то время как сциентизм базируется на абсолютизации рациональнотеоретических компонентов знания антисциентизм опирается на ключевую роль этических правовых культурных ценностей по отношению к идеалу...
82274. Дисциплинарная структура социально –гуманитарного знания и междисциплинарные исследования. Дифференциация и интеграция знаний 37 KB
  В дальнейшем проблематика связанная с первым типам междисциплинарности практически полностью стала изучаться в рамках исследований по классификации науки и ее развития. При этом главная Наука как социальный институт задача состоит в том чтобы преодолеть в процессе исследований отмеченное в свое время И. Эта задача пусть и не всегда в явной форме стоит перед участниками междисциплинарных исследований любого масштаба . Успешное осуществление междисциплинарных исследований предполагает одновременное решение трех видов проблем:...
82275. Переопределение парадигм и предметно- тематических направлений, появление новых областей исследования 38.77 KB
  В ходе развития науки в последней трети XX в. Ее фундамент составляют ставшие общенаучными принципы развития и системности. Такое понимание процессов развития исходит из синергетики. Вопервых принцип развития эволюции в современной науке получил статус фундаментальной мировоззренческой и методологической константы.
82276. Роль СГН и вненаучного знания в экспертизах социальных проектов и программ 32.11 KB
  Социальногуманитарные науки являются социальнокультурным феноменом изменяются вместе с обществом. Социальногуманитарные науки необходимы для разработки стратегии развития общества для понимания человеком своего места в социальной среде. Социальная политика всегда нуждается в социальной науке так как первая лишь излагает определенные идеалы а вторая мысленно упорядочивает факты и предлагает варианты действий М. Социальногуманитарные науки развиваются в настоящее время по следующим основным направлениям: сближение с...
82277. Изменения дисциплинарной структуры социально-гуманитарного знания в современных условиях. Смена лидирующих дисциплин 35.88 KB
  Вместе с тем региональные и функциональные различия науки обусловленные уровнем экономического технологического развития природными ресурсами вносят определенную спецификацию в совокупный потенциал развития науки. Одним из бесспорных мировоззренческих итогов науки начала XXI в. В основе научного мировоззрения лежит представление о возможности научного постижения сущности многообразных явлений современного мира о том что прогресс развития человечества связан с достижениями науки. Острые споры ведутся вокруг проблемы взаимоотношений...
82278. Возрастание роли гуманитарных знаний в современном обществе. «Сообщество знания». Значение опережающих социальных исследований для решения социальных проблем и предотвращения социальных рисков 31.17 KB
  Значение опережающих социальных исследований для решения социальных проблем и предотвращения социальных рисков. В этом состоит значение основополагающих социальных исследований. Важнейшими функциями социальных наук в современном обществе является критика действительности и ее проблематизация. Изучаются явления лежащие на стыке социальных и экономических сфер жизнедеятельности общества.
82279. Проблема глобализации в социально-гуманитарных науках 32.66 KB
  Учение интенсивно развивается и в рамках биологии исследование механизмов эволюции на молекулярном клеточном организменном уровнях. Для того чтобы описать движущие силы эволюции любого объекта нашего мира был создана синергетика новая междисциплинарная область Н исследований новое направление решения Н проблем. В настоящее время в Н в целом и в синергетике в частности используется принцип нелинейности многовариантности альтернативности путей темпов эволюции необратимости эволюции возможность непредсказуемых изменений. Поновому...
82280. Философия как интегральная форма научных знаний об обществе, культуре и человеке. (Аристотель, Гегель, Гоббс) 36.04 KB
  Ее называли наукоучением метанаукой наукой о науке а в западной традиции эпистемологией учением о знании или философией науки. Философия фундаментальное основание теоретической науки. Философия науки это область лежащая на границе философии и конкретного научного математического естественнонаучного гуманитарного социального технического знания. Как известно существуют различные науки: математика естествознание гуманитарные социальные и технические науки.
82281. Донаучные, ненаучные и вненаучные знания об обществе и культуре. Природа , общество и культура в социальном познании 36.36 KB
  Появление научного знания не отменило и не упразднило не сделало бесполезными другие формы знания. Каждой форме общественного сознания: науке философии мифологии политике религии и т. соответствуют специфические формы знания.