Одномерный массив. Пузырьковая сортировка.

Пузырьковая сортировка — это самая простая для человеческого восприятия сортировка, но очень неэффективная с точки зрения быстродействия. Тем не менее, в самом начале своего пути вы просто обязаны познакомиться с пузырьковой сортировкой.
  • Сортировка — это процесс перестановки чего-либо по какому-то признаку. Например, фамилии можно отсортировать по алфавиту, группу чисел по возрастанию или убыванию, учеников какой-то группы по успеваемости.
Под сортировкой массива понимают перестановку элементов массива любым заранее оговорённым образом: или по возрастанию/убыванию, или же с левой стороны массива положительные числа, идущие по возрастанию, а с правой отрицательные числа, идущие по возрастанию и т. п.
Начинается знакомство с сортировками с самых простых сортировок, при этом элементы, как правило, сортируются по убыванию или по возрастанию. В этой теме будет приведён пример сортировки массива по возрастанию.
Чтобы приступить к сортировке обычного массива, вы должны как минимум уметь менять переменные:

Нужно уметь не просто присваивать значения, а уметь взаимодействовать с уже существующими значениями переменных. Обычно создаётся временная переменная, которую используют как резерв для хранения значений. Эту маленькую задачу вам на самостоятельный разбор. Просто добавьте ещё одну переменную и заставьте её взаимодействовать с существующими: сначала нужно сохранить в резерве существующее значение, потом вытащить из резерва сохранённое значение.
Кроме умения использовать временную переменную для резервирования значений, нужно хотя бы немного представлять, что такое массив. Нужно понимать, что такое индексы массива, границы массива, значения массива.
Основа пузырьковой сортировки — сдвиг правильного элемента в край массива:

Смысл показанного кода в том, чтобы вы поняли основу движения в пузырьковой сортировке. Если анализировать массив слева-направо (что я и делаю), то самый левый элемент постепенно впрыгивая вправо по ячейкам сдвигается в правильную для себя позицию, в правый край. Прыжки происходят, когда условием сравнения определяется, что элемент находится не на своём месте.
Более полный код пузырьковой сортировки:

После каждого обхода массива, сдвигавшего некоторый элемент в правильную позицию, процесс сдвига происходит заново, только первоначальная позиция только что пододвинутого элемента больше не учитывается. Происходит сдвиг точки отсчёта и процесс повторяется. Таким образом точка отсчёта сдвигается по всему массиву. Это всё достигается путём оборачивания сдвига одного элемента в цикл. Вот и всё.
Особенно внимательным надо быть к границам массива. Поскольку в моём коде процесс происходит слева-направо, а элемент сравнивается с правостоящим, то при обходе массива нужно бежать к предпоследнему элементу, а не последнему. Последний элемент учтётся как правостоящий, в противном случае последний элемент массива будет сравнен с элементом, стоящим за пределами массива, а в этом ничего хорошего нет. При сдвиге некоторого элемента в край переменная j обозначает правостоящий элемент. Поскольку изначально она непосредственный сосед, то она при каждом новом проходе (после вставки некоторого элемента в свой край) принимает значение i+1, потом она становится вторым соседом, третьим соседом и т. д. Поскольку она правый сосед, то её учитывать надо вместе с последним элементом массива.
Распознавание границ массива — это хороший навык, который должен у вас появиться. Это одна из причин, почему стоит изучать пузырьковую сортировку, она хорошо способствует пониманию выхода за пределы или неполного захвата массива при анализе. Как сортировка — пузырьковая сортировка в реальных задачах не применяется вообще, потому что очень долго работает на больших массивах, предпочтение отдают другим видам сортировок.

3 комментария на «“Одномерный массив. Пузырьковая сортировка.”»

  1. Just Learn:

    Зачем  в цикле написано N-1?

    • Потому что N+1 (который по факту получается во вложенном цикле из-за начала не в нуле, а единице) будет учтён. Если не отнимать эту самую единицу, то мы вылезем ровно на 1 элемент за границу массива.
      1 2 3
      Сравниваются 1/2, 2/3; Чтобы закончить на двойке, мы (в показанном в примере случае) останавливаемся не на N, а на N-1, иначе (при остановке во внешнем цикле на N) выходит, что надо сравнить тройку с чем-то неизвестным, находящимся вне массива, за тройкой.
      Вот как-то так.

  2. андрей:

    void __fastcall TForm1::N14Click(TObject *Sender)
    {
    AnsiString a;
    for (int k=1;k<StringGrid1->RowCount; k++)
    for (int i=1;i<StringGrid1->RowCount-k; i++)
    if (StrToInt(StringGrid1->Cells[1][i])>StrToInt(StringGrid1->Cells[1][i+1]))
    for (int j=1; j<=StringGrid1->ColCount;j++)
    {a=StringGrid1->Cells[j][i+1];
    StringGrid1->Cells[j][i+1]=StringGrid1->Cells[j][i];
    StringGrid1->Cells[j][i]=a;
    }
    }

    как тут сделать чтобы сортировка была от буквы А до Я, мне нужно сделать так чтобы ФИО преподавателей сортировалось методом омена

     

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Поиск

 
     

Случайная книга в электронном формате

https://www.litres.ru/denis-kolisnichenko/php-5-6-i-mysql-6-razrabotka-web-prilozheniy/?lfrom=15589587
Яндекс.Метрика