Кажется, я не могу найти удовлетворительное решение этого вопроса здесь или в другом месте, хотя ссылка Сентила движется в правильном направлении.
Этот вопрос изначально меня озадачил, так как пузырьСортировка может быть оптимизирована путем досрочного завершения внешнего цикла после прохождения подмассива (или связанного списка и т. д.), который не может выполнить обмен значениями.Выбор сортировки не может помочь таким образом, так почему он выигрывает?Оба слабые в общем использовании - O (n ^ 2) - так почему же не тот, который можно хотя бы немного улучшить лучше?
Ответ, основанный исключительно на проверке моих собственных и других реализаций,является то, что пузырьковая сортировка делает обмен значениями (чтение, запись, запись) в КАЖДОМ ОДНОМ ХРИСТЕ СРАВНЕНИЯ.Выбор сортировки просто записывает новое граничное значение (мин для восходящей сортировки, макс для убывания), а затем заменяет его в конце прохода.
void swapInt(int *ptr1, int *ptr2) {
int temp;
temp = *ptr1;
*ptr1 = *ptr2;
*ptr2 = temp;
}
/* compare and swap over a shrinking sub-array */
void bubbleSortArray(int a[], const int aSize) {
int unsorted, i, iMax = (aSize - 1);
do {
unsorted = 0;
for (i = 0; i < iMax; i++) {
if ( a[i] > a[i + 1] ) {
unsorted = 1;
/* swap every time comparison is true */
swapInt(&a[i], &a[i + 1]);
}
}
--iMax;
} while (unsorted);
}
/* compare to find min value, write it before shrinking the sub-array */
void selectSortArray(int a[], const int aSize) {
int i, j, mindex;
for (i = 0; i < (aSize - 1); i++) {
mindex = i;
for (j = (i + 1); j < aSize; j++) {
if ( a[j] < a[mindex] ) mindex = j;
}
/* swap after inner loop terminates */
swapInt(&a[i], &a[mindex]);
}
}