Наредба - сортиране на елементи в масив
Съдържание
наредба - сортиране на елементи в масив
бързо сортиране - метод на Хоор
сортиране чрез пряка размяна - метод на мехурчето
сортиране чрез пряко вмъкване - метод на картоиграча
сортиране чрез пряка селекция - пряк избор
сливане на две наредени редици
Подреждане, сортиране на данни по определен признак, сортиране на елементи в масив е един от основните процеси при обработване на данни. Причината е ускоряване на следващо търсене в същата структура от данни било масив, било последователен файл или файл с директен достъп. Сложността на процеса на сортиране нараства изключително бързо с увеличаване броя на елементите. Не случайно Доналд Кнут отделя толкова голямо внимание на процеса сортиране в многотомния си труд. Нека споменем част от методите за сортиране - алгоритми за сортиране:
сортиране чрез пряко вмъкване - метод на картоиграча;сортиране чрез вмъкване с намаляваща стъпка - алгоритъм на Шел
сортиране чрез пряка размяна - метода на мехурчето;
сортиране чрез клатене
бързо сортиране на Хоор
метод на "зайците и костенурките”
сортиране чрез пряка селекция - пряк избор
пирамидално сортиране на Уйлямс
сортиране чрез трансформация
сортиране чрез множество
сортиране чрез броене
метод на бройните система
сортиране чрез пермутация
паралелно сортиране
сортиране чрез сливане MergeSort - прилагане на метода Разделяй и владей.
алгоритъм за наредба - сортиране
В почти всеки алгоритъм за наредба - сортиране се указва изрично: Не се ползва допълнителна оперативна памет, т.е. над необходимата памет за съхраняване на всички въведени стойности. Тези и аналогичните им алгоритми изпълняват условието: пестят памет, но се увеличава времето за работа, както и сложността на алгоритъма. Най-общо всеки алгоритъм за сортиране изисква сравняване на две стойности с евентуална последваща размяна на местата им.
Тук се разглежда обратната задача: имаме N броя цели числа, за които заделяме по-голям обем памет от необходимата. Описваният алгоритъм за сортиране е с линейна сложност, но в замяна изисква допълнителна памет.Следващата примерна програма използва едномерен масив с M елемента и работи с цели числа от интервала [0..N], където N<M. Броят на числата е P>=M>=N.
Преди началото на въвеждане новите случайни числа се извършва индексиране на целия масив - всички стойности стават равни на 0. Генерират се P броя случайни числа, които може и да се повтарят.
В масив в клетка с номер = новото число се добавя 1. При извеждане съдържанието на масива се извеждат толкова пъти индекса на тази клетка, колкото броя такива числа са били въведени в началния масив.
Следва примерна програма даваща решена задача използваща описания азлгоритъм за сортиране на елементи в масив:
бързо сортиране - алгоритъм на Хоор
Методът бързо сортиране е предложен от К. Хоор през 1962 г. и е един от най-добрите методи за сортиране по отношение на бързодействието. Основната причина за високата му ефективност е, че се разменят местата на елементи от масив намиращи се на големи разстояния помежду си. Самият Хоор твърди за този алгоритъм, че колкото са по-разбъркани стойностите в самото начало, толкова по-бързо се осъществява процесът на сортиране.
Тук се описва алгоритъм за сортиране във възходящ ред на стойностите. Избира се случаен елемент x от декларирания масив (най-често средния елемент на масива). Претърсваме масива отпред към средата до намирането на елемент по-голям или равен на x. След това претърсваме масива от края към средата до намирането на елемент по-малък или равен на x. В случая равенството е необходимо – то се използва като ограничение при проверяване стойностите в масива. Разменят се местата на тези елементи. Алгоритъмът продължава по аналогичен начин процеса на претърсване с размяна докато границите на двете претърсвания на масива отпред и отзад не се “срещнат” в определена позиция от масива. Така се получава условно разделяне на масива на две части – предната се състои само от елементи, по-малки или равни на x, а дясната – от елементи, по-големи или равни на x. Двете части в общия случай не са равни. Сортират се поотделно всяка от двете части на масива. В примерната програма сортирането на всяка от частите на масива се извършва с рекурсивно извикване. При всяко следващо рекурсивно извикване дължината на обработваната част от масива се намалява с 1 Това гарантира, че винаги ще бъде достигнато дъното на рекурсията, т.е. завършване на процеса за сортиране на елементите от началния масив.
Следва примерна програма даваща решена задача за сортиране на елементи в масив по алгоритъм на Хоор:Обяснени и решени задачи с подобни алгоритми, функции и служебни думи са разгледани в страницата с електронни уроци по информатика - програмиране.
Илюстриране работата на характерни алгоритми можете да намерите в предоставените електронни помагала съдържащи решени задачи, примери.