Путаница со следующим кодом сортировки выбора
int i, j, t;
for (i = 0; i < n - 1 ; i++) {
for (j = i + 1; j < n; j++) {
if (a[i] > a[j]) {
t = a[i];
a[i] = a[j];
a[j] = t;
}
}
}
Мой вопрос, является ли приведенный выше код правильным выбором сортировки кода или нет? Я получил этот код из разных книг. Если это неверно, объясните, пожалуйста, почему.
2 ответа
На мой взгляд, вид, показанный в вопросе, является пузырьковой, а не выборочной.
Среди других фрагментов кода, которые я копил в своем архиве, у меня есть испытательный стенд для различных алгоритмов сортировки. Тестовый стенд включает в себя всплывающие подсказки, выбор, вставку и быструю сортировку, а также отслеживает сравнения и обмены.
Код для сортировки пузырьков и выбора сортировки:
static void selection_sort(Data a[], int n)
{
for (int i = 0; i < n - 1; i++)
{
int min = i;
for (int j = i + 1; j < n; j++)
{
inc_comps();
if (a[j] < a[min])
min = j;
}
inc_comps();
if (min != i)
swap(&a[min], &a[i]);
}
}
static void bubble_sort(Data a[], int n)
{
for (int i = n - 1; i > 0; i--)
{
for (int j = 0; j < i; j++)
{
inc_comps();
if (a[j] > a[j+1])
swap(&a[j], &a[j+1]);
}
}
}
Сейчас я не помню, почему внешний цикл сортировки по пузырькам ведет обратный отсчет, а не вверх, но более важным моментом является то, что сортировка выбора заметно отличается от кода, показанного в вопросе, а код в вопросе соответствует пузырьковой сортировке. гораздо ближе.
Вы также можете найти в Википедии алгоритм сортировки, в котором описаны эти и многие другие алгоритмы, а также ссылки на различные источники информации о сортировке.
Испытательный стенд запускает разные алгоритмы с разными шаблонами данных для наборов данных разных размеров. Часть вывода предназначена для 10000 строк данных (тип int):
Number Filler Sorter Compares Swaps Time
10000 Random Quick 151583 88111 PASS 0.000593
10000 Random Bubble 49995000 24895500 PASS 0.143897
10000 Random Insertion 24905489 24895500 PASS 0.028966
10000 Random Selection 50004999 9986 PASS 0.040409
10000 Ascending Quick 151719 90480 PASS 0.000584
10000 Ascending Bubble 49995000 24876354 PASS 0.141219
10000 Ascending Insertion 24886345 24876354 PASS 0.022601
10000 Ascending Selection 50004999 9988 PASS 0.041173
10000 Descending Quick 119881 74247 PASS 0.000251
10000 Descending Bubble 49995000 49995000 PASS 0.081584
10000 Descending Insertion 49995000 49995000 PASS 0.055118
10000 Descending Selection 50004999 5000 PASS 0.050586
10000 Forward Organ Pipe Quick 25000000 25005000 PASS 0.034033
10000 Forward Organ Pipe Bubble 49995000 24995000 PASS 0.070633
10000 Forward Organ Pipe Insertion 25004999 24995000 PASS 0.022398
10000 Forward Organ Pipe Selection 50004999 9987 PASS 0.048300
10000 Reverse Organ Pipe Quick 25005002 16665004 PASS 0.025632
10000 Reverse Organ Pipe Bubble 49995000 24995000 PASS 0.064798
10000 Reverse Organ Pipe Insertion 25000000 24995000 PASS 0.022568
10000 Reverse Organ Pipe Selection 50004999 9886 PASS 0.053838
10000 Uniform Quick 49995000 19998 PASS 0.030855
10000 Uniform Bubble 49995000 0 PASS 0.038719
10000 Uniform Insertion 9999 0 PASS 0.000021
10000 Uniform Selection 50004999 0 PASS 0.041021
Как видно из данных, сортировка выбора оценивается хорошо по количеству свопов, которые она выполняет, но не так хорошо по количеству сравнений. Это дало бы вам возможность подтвердить мои наблюдения о том, что алгоритм в вопросе представляет собой пузырьковую сортировку, а не сортировку выбора.
Да, код правильный. В основном это займет дорого O(n^2) отсортировать массив в порядке возрастания.
На каждом шагу i [0..n-1]Вы помещаете наименьший элемент среди индексов [i..n-1] по указателю i,
Функция подкачки гарантирует, что вы постоянно помещаете меньшее значение из двух сравниваемых значений в i индекс.