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

  • Автор темы Liori
  • Дата начала
L

Liori

#1
Помогите!
Изучаю сортировку пузыркем и не понимаю вот эту стрчоку

Код:
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, а не нуля?
 
Последнее редактирование:
W

Whatka

#2
Индексация в массивах начинается с 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 внешнюю итерацию - самый тяжёлый элемент опускается,поэтому во внутреннем цикле
нету необходимости проверять последний элемент,после первой итерации, последний и предпоследний после второй и т.д.
 
R

rrrFer

#3
Несколько вопросов. почему N - 1 и почему, пока i>=1, а не нуля?
Внутренний цикл обходит массив и каждый раз помещает один из элементов (наибольший из неотсортированой части) в нужную позицию. Каждый раз отсортированная часть увеличивается как минимум на один элемент. Гарантированно когда внутренний цикл будет выполнен N раз - будет отсортировано N элементов массива.

Поэтому задача внешнего цикла - вызвать внутренний цикл N раз, сделать это можно как угодно. Сравнение выполняется с единицей, т.к. исопльзуется оператор >= , а не >.