Сравнение эффективности методов сортировки массивов Метод прямого выбора и метод сортировки с помощью дерева

  • Просмотров 4517
  • Скачиваний 449
  • Размер файла 33
    Кб

Лабораторная работа № 1 Сравнить эффективность методов сортировки массивов: Метод прямого выбора и метод сортировки с помощью дерева. Сортировка с помощью прямого выбора Этот прием основан на следующих принципах: 1. Выбирается элемент с наименьшим ключом. 2. Он меняется местами с первым элементом ai. 3. Затем этот процесс повторяется с оставшимися n-1 элементами, n-2 элементами и т.д. до тех пор, пока не останется один, самый большой

элемент. Процесс работы этим методом с теми же восемью ключами, что и в табл. 2.1, приведен в табл. 2.2. Алгоритм формулируется так: FORi:=ITO n-1 DO присвоить k индекс наименьшего из a[i],,, a[nJ; поменять местами a[i] и a[j]; end Такой метод – его называют прямым выбором – в не­котором смысле противоположен прямому включению. При прямом включении на каждом шаге рассматри­ваются только один очередной элемент исходной последовательности и все

элементы готовой последо­вательности, среди которых отыскивается точка вклю­чения; при прямом выборе для поиска одного эле­мента с наименьшим ключом просматриваются все элементы исходной последовательности и найденный помещается как очередной элемент в готовую после­довательность. Полностью алгоритм прямого выбора приводится в прогр. 2.3. Таблица 2.2. Пример сортировки с помощью прямого выбора Начальные ключи 44 55 12 42 94 18 06 67 06

55 12 42 94 18 44 67 06 12 55 42 94 18 44 67 06 12 18 42 94 55 44 67 05 12 18 42 94 55 44 67 05 12 13 42 44 55 94 67 06 12 18 42 44 55 94 67 06 12 18 42 44 55 67 94 PROCEDURE StraightSfcleclion; VAR i,j,k: index; x: item; BEGIN FORi:=1 TO n-1 DO k:= i; x := a[i]; FORj:= i+1TO n DO IF a[j]<xTHEN k:=j; X:= a[k] END BND; а[k] := а[i]; a[i] ; = x END END StraightSelection Прогр. 2.3. Сортировка с помощью прямого выбора, Анализ прямого выбора. Число сравнений ключей (С), очевидно, не зависит от начального порядка клю­чей. Можно сказать, что в этом смысле поведение этого метода менее естественно, чем

поведение пря­мого включения. Для С имеем с = (n2 - n)/2 Число перестановок минимально Mmin=3*(n-l) (2.6) в случае изначально упорядоченных ключей и макси­мально Mmax = n2/4 +3(n-1) если первоначально ключи располагались в обратном порядке. Для того чтобы определить Mavg, мы должны рассуждать так. Алгоритм просматривает массив, сравнивая каждый элемент с только что обнаружен­ной минимальной величиной; если он меньше первого, то выполняется