Главная » Java, Структуры данных и алгоритмы » Анализ алгоритма сортировки пузырьковым методом с точки зрения последовательности

0

Предположим, что при реализации последовательности время каждого обращения и перемещения элементов, выполняемых сортирующим алгоритмом, составляет 0(1). Таким образом, время выполнения /-го обхода равно 0(п — / + 1). Значит, общее время выполнения алгоритма пузырьковой сортировки составляет

Согласно утверждению 3.4, имеем

Таким образом, время выполнения алгоритма пузырьковой сортировки составляет 0(п2) при условии, что каждая операция доступа и перемещения элементов выполняется за время 0(1).

// алгоритм пузырьковой сортировки, использующий разряды public static void bubbleSortl(Sequence S) { int n = S.size();

for (int i=0; i < n; i++) // i-ый проход for (int j=l; j < n—i; j++) if ( valAtRank(S, j-1) > valAtRank(S, j) ) S.swapElements(S.atRank(j-l), S atRank(j));

}

// алгоритм пузырьковой сортировки, использующий позиции public static void bubbleSort2(Sequence S) { Position prec, succ; int n = S.size();

for (int i=0; i < n; i++) { // i-ый проход prec = S.firstQ; for (int j=l; j < n-i; j++) succ = S.after(prec); if ( valAtPos(prec) > valAtPos(succ) )

S.swapElements(prec, succ); prec = succ;

}

}

}

private static int valAtRank(Sequence S, int i) { return ((Integer) S.elemAtRank(i)).intVahje();

}

private static int valAtPos(Position p) { return ((Integer) p.element()).intValue();

}

Эта сумма может быть представлена в следующем виде: 0(п + (п-1) +…+ 2 + I),

то есть

Фрагмент кода 5.13. Класс из двух Java-реализаций пузырьковой сортировки последовательности объектов Integer

Фрагмент кода 5.13 содержит две Java-реализаций пузырьковой сортировки последовательности объектов Integer. Реализации отличаются методами доступа и изменения последовательности.

Метод BubbleSortl осуществляет доступ к элементам только с помощью методов atRank и elemAtRank, описанных в методе, применяющем разряды, который может быть использован только в случае реализации последовательности на основе массива, когда atRank и elemAtRank выполняются за время 0(1). В этом случае метод BubbleSortl выполняется за время 0(п2). С другой стороны, если последовательность в данном алгоритме реализована на основе двусвязного списка, наибольшее время выполнения atRank составит 0{п). Это означает, что общее время выполнения алгоритма при реализации на основе двусвязного списка в худшем случае будет 0(я3).

Метод BubbleSort2 осуществляет доступ к элементам только с помощью методов first и after, применяемых в методе с использованием позиций. Данная реализация может применяться как при реализации последовательности на основе массива, так и на основе двусвязного списка. В обоих случаях время выполнения методов first и after постоянно. Таким образом, независимо от способа реализации последовательности время выполнения BubbleSort2 есть 0(я2).

Представленные алгоритмы пузырьковой сортировки подчеркивают значение эффективной реализации АТД. Однако, несмотря на простоту, многие исследователи полагают, что алгоритм пузырьковой сортировки не является эффективным, так как в самом лучшем случае показатель времени представляет квадратичную функцию. Существуют алгоритмы сортировки, время выполнения которых равно 0(п log п), которые, безусловно, эффективнее пузырьковой сортировки. Ряд таких алгоритмов рассматривается в главах 7 и 10.

Источник: Гудрич М.Т. Г93 Структуры данных и алгоритмы в Java / М.Т. Гудрич, Р. Тамассия; Пер. с англ. A.M. Чернухо. — Мн.: Новое знание, 2003. — 671 е.: ил.

По теме:

  • Комментарии