Проблема с пузырьковой сортировкой массива

[FiEnDDD]

как сделать чтобы сортировка шла не с 1-го элемента до последнего а с 1-го до последнего упорядоченного , или скажем задать что последний элемент уже отсортирован и не изменять его

Код: Выделить всё

void main ()
{
	const int N=100;
	int a[N],n;
	printf("Enter n<  %d",N);
	scanf("%d",&n);
	printf("\nArray:\n");
	for (int i=0;i<n;i++) //Генерируем массив случайных чисел в 
					//диапазоне [0..50] и выводим на экран
	{
		a[i]=rand()%51;
		printf("%d%s",a[i],"  ");
	}

	printf("\nSotr:\n");
	bool f; int b;
	do
	{
		f=false;
		for(int i=0;i<n-1;i++)// Просматриваем весь массив
			if (a[i]>a[i+1])  
			{
				b=a[i];
				a[i]=a[i+1];
				a[i+1]=b;
				f=true; //Был обмен
			}
	}
	while (f); // Проверяем, был ли хоть один обмен
	for (int i=0;i<n;i++) // Выводим на экран отсортированный
				//массив
		printf("%d%s",a[i],"  ");
		getch();
}

код приложил

[FiEnDDD]

Спасибо большое ! что никто не помог

[somewhere]

Да потому что в требованиях нет логики. Алгоритм не предусматривает уже отсортированного пула. Иными словами, в любой момент времени нельзя достоверно сказать, что конкретный элемент массива уже отсортирован и будет находится здесь до окончания работы.

[Romeo]

somewhere, ты не прав. Смысл пузырьковой сортировки именно в том, что на каждом проходе в конец "выплывает" самый толстый элемент и при следующем проходе мы не должны пытаться проверять хвост. Именно поэтому она называется пузырьковой. Таким образом, на каждой итерации неотсортированная часть массива постоянно уменьшается.

FiEnDDD, для того, чтобы поправить алгоритм, необходимо сделать не do/while и внутри for, а два вложенных for. Внешний for должен уменьшать правую границу, а внутренний for должен бежать он начала, до этой границы. Я достаточно подробно описал, чтобы закодить это самостоятельно?

[somewhere]

Ну да, тупанул =) А все потому, что обычно я сортирую проходами и отдельный элемент у меня в конец не ведется (как в классическом пузырьке). То есть достаточно поменять условие сравнения на противоположное и получится как раз такой метод - за один проход в конец ведутся сразу несколько элементов. Отсюда и недостаток - нет отсортированного пула. Зато для небольших массивов эффективность выше, число проходов меньше. А для больших массивов уже другие сортировки работают, qsort например

[Romeo]

Да, qsort бесспорный лидер. Но до него нужно ещё дойти в лекциях по алгоритмам. Он апофеоз всей теории сортировки

[Сионист]

Это вообще не пузырёк, а подобный ему, но другой алгоритм. Пузырёк выглядит так:

Код: Выделить всё

for (i=0; i<n-1; ++i)
{
 for (j=i+1; j<n; ++j)
 {
  if (a[i]>a[j])
  {
   b=a[i];
   a[i]=a[j];
   a[j]=b;
  }
 }
}

. Внешний цикл перебирает индекс элемента, завершающего часть массива, которая в конце шага этого цикла будет отсортирована, внутренний цикл перебирает кандидатов на перестановку в начало части массива, начинающейся с элемента, чей индекс перебирает внешний цикл. Можно оптимизировать сравнение:
1. Заранее вычислив n-1.
2.

Код: Выделить всё

for (i=n-1; i>0; --i)
{
 for (j=i-1; j>=0; --j)
 {
  if (a[j]>a[i])
  {
   b=a[i];
   a[i]=a[j];
   a[j]=b;
  }
 }
}

. Массив перевёрнут, отсортированная часть растёт от его конца к началу, соответственно внешний цикл перебирает индекс элемента, который в конце шага этого цикла будет начинать отсортированную часть,
соответственно во внутреннем цикле перебираются кандидаты на перестановку в конец части массива, завершаемой элементом, чей индекс перебирается внешним циклом. При беззнаковом индексе вместо

Код: Выделить всё

for (j=i-1; j>=0; --j)

пишется

Код: Выделить всё

for (j=i-1; j<n; --j)

.
3.

Код: Выделить всё

for (i=0; i<n; ++i)
{
 for (j=i+1; j<n; ++j)
 {
  if (a[i]>a[j])
  {
   b=a[i];
   a[i]=a[j];
   a[j]=b;
  }
 }
}

. Внешний цикл один раз доходит до последнего элемента, на последнем шаге внутренний цикл не запускается, соответственно шаг внешнего цикла завершается, ничего не сделав, но зато сравнение происходит без сложения каждый раз. Величина n должна быть строго меньше максимально представимой, иначе в теле внешнего цикла нужен ещё и if для защиты от переполнения индекса внутреннего цикла, что полностью компенсирует оптимизацию и даже может пессимизировать код.

[Сионист]

somewhere, ты не прав. Смысл пузырьковой сортировки именно в том, что на каждом проходе в конец "выплывает" самый толстый элемент и при следующем проходе мы не должны пытаться проверять хвост. Именно поэтому она называется пузырьковой. Таким образом, на каждой итерации неотсортированная часть массива постоянно уменьшается.

Так в коде из стартового поста отсортированная часть тоже уменьшается. А не уменьшается проверяемая.