Страница 1 из 1
Проблема с пузырьковой сортировкой массива
Добавлено: 07 июл 2015, 18:27
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();
}
код приложил
Re: нужен совет (Пузырьковая сортировка массива)
Добавлено: 10 июл 2015, 00:26
FiEnDDD
Спасибо большое ! что никто не помог
Re: нужен совет (Пузырьковая сортировка массива)
Добавлено: 10 июл 2015, 08:57
somewhere
Да потому что в требованиях нет логики. Алгоритм не предусматривает уже отсортированного пула. Иными словами, в любой момент времени нельзя достоверно сказать, что конкретный элемент массива уже отсортирован и будет находится здесь до окончания работы.
Re: нужен совет (Пузырьковая сортировка массива)
Добавлено: 10 июл 2015, 09:42
Romeo
somewhere, ты не прав. Смысл пузырьковой сортировки именно в том, что на каждом проходе в конец "выплывает" самый толстый элемент и при следующем проходе мы не должны пытаться проверять хвост. Именно поэтому она называется пузырьковой. Таким образом, на каждой итерации неотсортированная часть массива постоянно уменьшается.
FiEnDDD, для того, чтобы поправить алгоритм, необходимо сделать не do/while и внутри for, а два вложенных for. Внешний for должен уменьшать правую границу, а внутренний for должен бежать он начала, до этой границы. Я достаточно подробно описал, чтобы закодить это самостоятельно?
Re: нужен совет (Пузырьковая сортировка массива)
Добавлено: 10 июл 2015, 10:27
somewhere
Ну да, тупанул =) А все потому, что обычно я сортирую проходами и отдельный элемент у меня в конец не ведется (как в классическом пузырьке). То есть достаточно поменять условие сравнения на противоположное и получится как раз такой метод - за один проход в конец ведутся сразу несколько элементов. Отсюда и недостаток - нет отсортированного пула. Зато для небольших массивов эффективность выше, число проходов меньше. А для больших массивов уже другие сортировки работают, qsort например
Re: нужен совет (Пузырьковая сортировка массива)
Добавлено: 10 июл 2015, 10:30
Romeo
Да, qsort бесспорный лидер. Но до него нужно ещё дойти в лекциях по алгоритмам. Он апофеоз всей теории сортировки
Re: Проблема с пузырьковой сортировкой массива
Добавлено: 19 авг 2015, 14:37
Сионист
Это вообще не пузырёк, а подобный ему, но другой алгоритм. Пузырёк выглядит так:
Код: Выделить всё
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;
}
}
}
. Массив перевёрнут, отсортированная часть растёт от его конца к началу, соответственно внешний цикл перебирает индекс элемента, который в конце шага этого цикла будет начинать отсортированную часть,
соответственно во внутреннем цикле перебираются кандидаты на перестановку в конец части массива, завершаемой элементом, чей индекс перебирается внешним циклом. При беззнаковом индексе вместо
пишется
.
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 для защиты от переполнения индекса внутреннего цикла, что полностью компенсирует оптимизацию и даже может пессимизировать код.
Re: нужен совет (Пузырьковая сортировка массива)
Добавлено: 19 авг 2015, 14:39
Сионист
Romeo писал(а):somewhere, ты не прав. Смысл пузырьковой сортировки именно в том, что на каждом проходе в конец "выплывает" самый толстый элемент и при следующем проходе мы не должны пытаться проверять хвост. Именно поэтому она называется пузырьковой. Таким образом, на каждой итерации неотсортированная часть массива постоянно уменьшается.
Так в коде из стартового поста отсортированная часть тоже уменьшается. А не уменьшается проверяемая.