Для чего нужен второй цикл в алгоритме?

Question

[Goddamnboy]

Вот сортировка пузырьком на C++. Для чего нужен второй цикл "for"(с переменной j) в ней ?

for (int i = 0; i < size - 1; i++) {
		for (int j = 0; j < size - i - 1; j++) {   //<- для чего он??
			if (arr[j] > arr[j + 1]) {
				temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
		}
	}

Comments

[Евгений Самсонов]

Чтобы сложность алгоритма была квадратичная, иначе слишком все просто. Шутка :) Просто разберитесь, как работает алгоритм по шагам, тогда поймете, зачем нужен второй цикл

[RabraBabr]

Как вы думаете за один проход весь массив отсортируется или только одно число вытолкнется в конец массива?

[Модератор]

Goddamnboy дорогой пользователь, настоятельно рекомендуем еще раз обратить самое пристальное внимание на п. 3.1 регламента работы сервиса (и, в особенности, на его последний абзац). В противном случае, ваши вопросы будут удаляться по причине тег-спама, а систематические нарушения приведут к блокировке учетной записи.

[RabraBabr]

Хотя хотите с одним циклом их есть у меня:

spoiler

int size=10;
	int arr[size]{0,6,4,9,3,25,8,1,11,4};
	bool success=false;
	bool change=false;
	int current=0;
	int next=current+1;
	int temp=0;
	
	while (!success)
	{
		if (arr[current] > arr[next])
		{
			temp=arr[current];
			arr[current]=arr[next];
			arr[next]=temp;
			change=true;
		}
		
		if (next<size)
		{
			current++;
		}
		else
		{
			current=0;
			
			if (change)
			{
			    change=false;
			}
			else
			{
			    success=true;
			}
		}
		
		next=current+1;
	}

Answer 1

[Developer]

Второй цикл нужен для того, чтобы сложность алгоритма была О(n^2)
:)

Answer 2

[Dimonchik]

чтобы было нескучно первому

Answer 3

[bkosun]

Алгоритм состоит из повторяющихся проходов по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются N-1 раз или до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — массив отсортирован. При каждом проходе алгоритма по внутреннему циклу, очередной наибольший элемент массива ставится на своё место в конце массива рядом с предыдущим «наибольшим элементом», а наименьший элемент перемещается на одну позицию к началу массива («всплывает» до нужной позиции, как пузырёк в воде — отсюда и название алгоритма).

https://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%80%D...

Answer 4

[Александр Скуснов]

Внутренний цикл - подъём одного пузырька. Внешний - поднять все пузырьки.