Я использую алгоритмы сортировки маркировки, используя java. Когда я сравниваю среднюю сортировку Bubble с сортировкой Selection, используя рандомизированные массивы в диапазоне от 0 до 99, сортировка Bubble работает заметно лучше. В большинстве ссылок на производительность, которые я прочитал, указано, что сортировка по разделам является лучшей из двух.
Это моя реализация Selection:
public static void selectionSort(int[] arr) {
/*
* Selection sort sorting algorithm. Cycle: The minimum element form the
* unsorted sub-array on he right is picked and moved to the sorted sub-array on
* the left.
*
* The outer loop runs n-1 times. Inner loop n/2 on average. this results in
* (?−1)×?2≈?2 best, worst and average cases.
*
*/
// Count outer
for (int i = 0; i < arr.length; i++) {
// Assign the default min index
int min = i;
// Find the index with smallest value
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[min]) {
min = j;
}
}
// Swap index arr[min] with a[i]
int temp = arr[min];
arr[min] = arr[i];
arr[i] = temp;
}
}
Моя сортировка по пузырькам:
public static void optimalBubbleSort(int[] arr) {
/**
* The optimized version will check whether the list
* is sorted at each iteration. If the list is sorted the
* program will exist.
* Thus the best case for the optimized bubble sort
* is O{n). Conversely the above algorithm
* the best case will always be the same as the average case.
*
*/
boolean sorted = false;
int n = arr.length;
while (!sorted) {
sorted = true;
for (int i = 0; i < n - 1; i++) {
if (arr[i] > arr[i + 1]) {
int temp = arr[i + 1];
arr[i + 1] = arr[i];
arr[i] = temp;
sorted = false;
}
}
n--;
}
}
Моя реализация сортировки по пузырькам не оптимизирована для выхода при сортировке списка:
for (int i = 0; i < arr.length - 1; i++) {
/*
* Iteration of the outer loop will ensure
* that at the end the largest element is in the
* (array.lenght-(i+1))th index.
* Thus the loop invariant is that
* In other words, the loop invariant is that
* the subsection bounded by the indices
* [arr.length - i, arr.length] is sorted and
* contains the i biggest elements in array.
*/
for (int j = 0; j < arr.length - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
/*
* In the case where an inversion exists in
* arr[j] > arr[j + 1],
* arr[j] and arr[j + 1] are
* thus swapped.
*/
int temp = arr[j + 1];
arr[j + 1] = arr[j];
arr[j] = temp;
}
}
}
Так я генерирую рандомизированный массив для inout :
int[] random = new int[n];
for (int i = 0; i < n; i++) {
random[i] = randomInteger.nextInt(100);
}
Любая информация о том, почему Bubble сортируется быстрее.