Что за сортировка?

[Malriser]

Здравствуйте, уважаемые форумчане. Наверное столь тупых вопросов не было от родня, но...

Короче, сидя без инета я начал экспериментировать и получилось закодить такой алгоритм:

for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
  if (A[i] > A[j]) swap(A[i], A[j]);

Придумал этот алгоритм сам - работает; интересует вопрос как называется этот алгоритм, ведь 100% он уже есть очень давно. А то мучает вопрос, что за велосипед я создал =D

[rrrFer]

Вроде бы сортировка пузырьком.

[waleri]

Сообщение от rrrFer

сортировка пузырьком.

Только неработающая...
Надо продолжать сортировать пока все элементы не окажутся на своих местах.

[rrrFer]

Только неработающая...
Надо продолжать сортировать пока все элементы не окажутся на своих местах.

хз, вроде бы работающая.
Гарантированно за каждую итерацию внешнего цикла один элемент будет вставать на своем место. В нем столько итераций, сколько элементов в массиве. Значит все элементы окажутся на своих местах. Где я не прав?

[Malriser]

Сообщение от rrrFer

хз, вроде бы работающая.
Гарантированно за каждую итерацию внешнего цикла один элемент будет вставать на своем место. В нем столько итераций, сколько элементов в массиве. Значит все элементы окажутся на своих местах. Где я не прав?

Ты прав - работающая, я проверял на рандомно-заполненном массиве в 100 000 элементов.

Только вот хз, пузырьком ли это.

for(int i = 0; i < a.length - 1; i++)
    for(int j = 0; j < a.length - i - 1; j++)
        if(a[j] > a[j + 1])
            swap(a[j], a[j + 1]);

С википедии, пузырьком, как мы видим, вложенный цикл начинает работу с 0-го элемента, у меня с i+1-го элемента. Следовательно у меня сложность алгоритма меньше чем у пузырька, я не прав? И у меня меняются местами i-ые элементы и j-ые, а не j+1 и j. Так что нет, не пузырьком.

Сообщение от waleri

Только неработающая...
Надо продолжать сортировать пока все элементы не окажутся на своих местах

Работающая, проверь, все отлично работает.



UPD: похожа, https://ru.wikipedia.org/wiki/%D0%A1...80%D0%BE%D0%BC

Это сортировка выбором, только я не нахожу минимальный элемент О-о. Это у меня что, упрощенная сортировка выбором, WTF :D

[waleri]

Сообщение от rrrFer

хз, вроде бы работающая.
Гарантированно за каждую итерацию внешнего цикла один элемент будет вставать на своем место. В нем столько итераций, сколько элементов в массиве. Значит все элементы окажутся на своих местах. Где я не прав?

Да, все верно, недоглядел...
Но оптимально только для случаев, когда надо все элементы переставить, т.е. когда массив задом-наперед.

[rrrFer]

waleri
Да никогда не оптимально, че уж там ))

Это сортировка выбором, только я не нахожу минимальный элемент О-о.

У тебя испорченная сортировка выбором. Лучше искать минимальный элемент, чем переставлять элементы.

Кстати, о сортировках можешь тут почитать: http://pro-prof.com/archives/1462 - пузырьком, выбором и вставками. В конце там ссылки на быструю сортировку и сортировку слиянием. Есть тьма модификаций всяких алгоритмов (их в научной литературе только можно несколько тысяч найти), начиная от эффективных и распараллеливаемых. заканчивая всякой эзотерикой типа гномьей сортировки.

Че тебе далась то эта сортировка вообще?

[Smitt&Wesson]

интересует вопрос как называется этот алгоритм

Это однозначно сортировка пузырьком. Отличие Вашего алгоритма, от того, что привёл Malriser в том, что у Вас разность адресов формируется при инициализации цикла for, а у Malriser эта разница осуществляется внутри цикла при помощи инкремента одного из индексов.
Я вообще не понимаю, зачем здесь два Фора? Вот алгоритм, который работает почти на треть быстрее, чем классический.

bool x = true;
    while(x)
    {
    x = false;
    for(int i=0; i< n; i++)
      if(array[i] > array[i+1])
      {
        swap(array[i], array[i+1]);
        x = true;
      }
    }