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

[Liori]

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

for(int i=N-1;i>=1;i--)

в коде

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, а не нуля?

 

[Whatka]

Индексация в массивах начинается с 0.

То есть

int* a = new int[10];

будет создавать массив для 10 элементов,но индексы будут от 0 до 9.

Вот "классический" вариант сортировки:

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

 

[rrrFer]

Несколько вопросов. почему N - 1 и почему, пока i>=1, а не нуля?

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

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

 

[Anonimyc]

Один из простейших типов сортировки)