Кухня(); Второй сезон - 74/79



74. Сортировка обменами. Дана последовательность чисел а1, а2, ..., аn. Требуется переставить числа в порядке возрастания. Для этого сравниваются два соседних числа аi и ai+1. Если аi > аi+1, то делается перестановка. Так продолжается до тех пор, пока все элементы не станут расположены в порядке возрастания. Составить алгоритм сортировки, подсчитывая при этом количество перестановок.

9 комментариев

profeg
Пузырьковая сортировка?

int[] iArr = {2,3,4,6,89};
int count = 0; // счетчик перестановок
for (int i = 0; i < iArr.length - 1; i++)
    for (int j = 0; j < iArr.length - i - 1; j++)
        if (iArr[j] > iArr[j+1]) 
        {
            int temp = iArr[j];
            iArr[j] = iArr[j+1];
            iArr[j+1] = temp;
            count++;
        }
terranum
Отлично, стоит только заключать в метод, ну что-то типа такого:

    public static void bubbleSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++)
            for (int j = 0; j < arr.length - i - 1; j++)
                if (arr[j] > arr[j + 1]) {
                    arr[j] ^= arr[j + 1];
                    arr[j + 1] ^= arr[j];
                    arr[j] ^= arr[j + 1];
                }
    }
Olegator3
ох стоит подучить логические операции, не знал что с помощью XOR менять можно, если не сложно поясни что ты сделал тут ^=, аж интересно стало, намного лучше чем создавать «пузырек», изящно
terranum
Говорят обычно так не пишут, правильнее создавать дополнительную переменную. Вроде как это на собеседовании спрашивают.
Ну тут смотри какая логика, на сложении проще всего:
int a = 5;
int b = 7;

Надо поменять местами.
a = a + b; // a = 5 + 7 И а тепрь у нас равно 15
b = a - b; // b = 15 - 7 Ок, b уже на своем месте и равно 5
a = a - b; // a = 15 - 5 Все а теперь 7

И с операторами присваивания:
a += b;
b = a - b;
a -= b;

Попробуй с умножением! Понял схему, дальше все на автомате.
Docktor91
а меня порадовало 5+7=15
))))
terranum
lol))) Я же говорю один раз понял как это работает, больше не надо)))
terranum
Фуф я плакал)
profeg
а где подсчет кол-ва перестановок? =)
terranum
Поймал! Есть такой баг)))
Только зарегистрированные и авторизованные пользователи могут оставлять комментарии.