Есть ли имя для моего алгоритма сортировки?
В школьном задании я должен был создать алгоритм сортировки.
Я сделал следующее:
//array "ints" has already been declared
int s = 0;
for(int i=0;i<ints.length;i++) {
for(int j=i+1; j<ints.length; j++) {
if (ints[i]>ints[j]) {
s = ints[j];
ints[j]=ints[i];
ints[i]=s;
}
}
}
Учитель назвал описанный выше алгоритм «сортировкой пузырьком». Однако из того, что я могу найти (в Google), приведенный выше код - это пузырьковая сортировка нет и пузырьковая сортировка больше похожа на приведенный ниже код: (вероятно, не самая эффективная его версия, но что угодно)
//array "ints" has already been declared
int sub = 0;
int swaps = 100;
if (ints.length>1) {
while(swaps>0) {
swaps=0;
for(int i=0; i<ints.length-1; i++) {
if (ints[i]>ints[i+1]) {
sub = ints[i+1];
ints[i+1]=ints[i];
ints[i]=sub;
swaps++;
}
}
}
}
Я уверен, что на самом деле не изобретал нового алгоритма сортировки, но я не могу найти ни одного алгоритма сортировки, использующего тот же процесс, что и код, который я написал.
Есть ли название моего алгоритма?
Обратите внимание, что он сравнивает несмежные значения и процесс сортировки, и алгоритм не обязательно завершается после раунда прохождения алгоритма без замены. Оба они указывают, что это пузырьковая сортировка нет. Возможно, это сортировка выбора версии.
Я не хочу знать, насколько это эффективно; Я работаю над тем, чтобы выяснить это самостоятельно.
@ PM77-1 о. У меня сложилось впечатление, что пузырьковая сортировка сравнивает только значения соседний, такие как здесь.
Существует более одного способа реализации пузырьковой сортировки. Пузырьковая сортировка — это просто всплытие младших значений вверх.
@ Шрини, спасибо. Так что ссылка, которую я упомянул, неверна, чтобы сказать «Пузырьковая сортировка многократно сравнивает соседние элементы массива.»? Или они говорят, что пузырьковая сортировка их так работает?
См. похожий вопрос, возможно: Какой из них является пузырьковой сортировкой или они оба?
Хорошо, я понимаю, к чему вы клоните. Это не сортировка пузырьком традиционный. То, что вы реализовали, я бы сказал, похоже на небольшую модификацию пузырьковой сортировки под названием Сортировка выбором, точнее здесь. Вы перебираете вложенные массивы, чтобы найти минимум в сортировке выбором.
@ Шрини, не могли бы вы добавить это в ответ?
На мой взгляд, это больше похоже на сортировку выбором с большим количеством лишних свопов.
@unlut вопрос, который вы связали, имеет противоречивые ответы :(
@maraca да, я не думал, что это очень эффективно. Основываясь на ссылке из unlut, я предполагаю, что это больше похоже на сортировку выбором.
@firephil из первой ссылки, которую вы дали - пузырьковая сортировка «сравнивает соседние пары». Мой алгоритм (вероятно, модифицированная сортировка выбора) может сравнивать несмежные значения.
@firephil, что доказывают эти ссылки? Все примеры пузырьковой сортировки просто сравнивают и меняют местами элементы соседний, как сказал Brandon_J в самом начале.
@firephil да, но это не в моем примере.
но ints[i]>ints[j] не является, как я уже сказал, какой-то странной сортировкой на месте, которая требует лишних свопов.
@firephil и i и j не всегда отличаются только одним ( ints[i]>ints[i+1] не то же самое, что ints[i]>ints[j] )
@firephil, а затем j++, несколько раз, если это большой массив. (что марака говорит ниже)
@firephil не смотрите ближе, только на первой итерации внутреннего цикла
И я знаю, что этот вопрос является основным; дело в том, что (помимо моего понимания того, что compsci является базовым банкоматом), легко перейти от имени алгоритма к алгоритму. Сложнее перейти от алгоритма к названию алгоритма.
@Brandon_J, вы можете назвать это гибридной сортировкой пузырьковым выбором, это не чистая сортировка выбором или пузырьковая сортировка
@firephil возможно. Основная процедура кажется намного ближе к сортировке выбором IMO.
Ответы 1
Похоже, что это модифицированный сортировка выбором, как указали Марака и Срини.
См., например, эта анимационная страница. Пузырьковая сортировка (с заданной длиной массива/списка) занимает больше или меньше времени в зависимости от того, почти отсортирован массив или нет. Сортировка выбором (с заданной длиной массива/списка) принимает точно такое же количество времени независимо от того, как изначально был отсортирован список. Мой алгоритм в основном похож на сортировку выбором, за исключением того, что в нем много лишних/ненужных свопов.
Когда я выучил эту идиому в школе, профессор назвал ее сортировкой отбором. Оба из них являются довольно ужасными алгоритмами сортировки, но есть веский аргумент, является ли это худшей сортировкой выбором или худшей пузырьковой сортировкой.
Это пузырьковая сортировка является.