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

Тема в разделе "Общие вопросы по С и С++", создана пользователем Liori, 1 дек 2014.

  1. Liori

    Liori New Member

    Регистрация:
    30 ноя 2014
    Сообщения:
    3
    Симпатии:
    0
    Помогите!
    Изучаю сортировку пузыркем и не понимаю вот эту стрчоку

    Код ( (Unknown Language)):
    for(int i=N-1;i>=1;i--)
    в коде

    Код (C++):
    for(int i=N-1;i>=1;i--)
    for(int j=0;j<i;j++)
    {
    if(A[j]>A[j+1])
    {// меняем местами элементы
    int temp(0);
    temp=A[j];
    A[j]=A[j+1];
    A[j+1]= temp;

    }
    }
    Понимаю внутренний цикл так: пробегаем от нулевого элемента до того, что уже стоит в конце(который оказался максимальным), если левый элемент больше, чем правый, меняем их местами.
    Внешний цикл понимаю так: от элемента, который оказался максимальным, пробегаем до первого элемента, но поскольку это "пробегание" справа налево, используем декремент.
    Несколько вопросов. почему N - 1 и почему, пока i>=1, а не нуля?
     
    #1 Liori, 1 дек 2014
    Последнее редактирование модератором: 17 фев 2015
  2. Whatka

    Whatka Well-Known Member

    Регистрация:
    9 окт 2011
    Сообщения:
    433
    Симпатии:
    4
    Индексация в массивах начинается с 0.

    То есть
    Код (C++):
    int* a = new int[10];
    будет создавать массив для 10 элементов,но индексы будут от 0 до 9.

    Вот "классический" вариант сортировки:
    Код (C++):
    for(int i = 0; i < N -1; i++)
    for(int j = 0; j < N - i -1; j++)
    if(a[j] > a[j + 1])
    swap(a[j], a[j + 1]);
    суть: все лёгкие элементы поднимаются вверх,а тяжёлые опускаются соответственно вниз.
    За 1 внешнюю итерацию - самый тяжёлый элемент опускается,поэтому во внутреннем цикле
    нету необходимости проверять последний элемент,после первой итерации, последний и предпоследний после второй и т.д.
     
  3. rrrFer

    rrrFer Well-Known Member
    Команда форума C\C++ Team

    Регистрация:
    6 сен 2011
    Сообщения:
    1.324
    Симпатии:
    36
    Внутренний цикл обходит массив и каждый раз помещает один из элементов (наибольший из неотсортированой части) в нужную позицию. Каждый раз отсортированная часть увеличивается как минимум на один элемент. Гарантированно когда внутренний цикл будет выполнен N раз - будет отсортировано N элементов массива.

    Поэтому задача внешнего цикла - вызвать внутренний цикл N раз, сделать это можно как угодно. Сравнение выполняется с единицей, т.к. исопльзуется оператор >= , а не >.
     
Загрузка...
Похожие Темы - Сортировка пузырьком
  1. vera2014
    Ответов:
    0
    Просмотров:
    1.069
  2. FCDK
    Ответов:
    0
    Просмотров:
    1.263
  3. ленарано
    Ответов:
    1
    Просмотров:
    1.102
  4. Creder
    Ответов:
    0
    Просмотров:
    1.344
  5. kingl
    Ответов:
    0
    Просмотров:
    1.072

Поделиться этой страницей