Ошибка сортировки при двусторонней вставке
Я пытаюсь сделать двустороннюю вставку сортировки. Он должен принимать самое первое значение в массиве, а затем сортировать следующие числа в массиве, сравнивая его с этим первым значением. Если число больше, оно помещается позади первого в массиве, если оно меньше, оно помещается впереди.
Вот изображение, которое иллюстрирует процесс.
Массив здесь равен 6 5 3 1 8 7 2 4, чтение сверху вниз — это каждый шаг процесса сортировки. Он сравнивает число 6 с остальными числами, а затем размещает их соответственно.
Пока у меня есть этот код:
void twowaysort(int n, int a[])
{
int j;
int first = a[0];
for (int i = 1; i < n; i++) {
if (a[i] > first) {
j = i + 1;
while (j <= n - 1 && a[j] < a[j - 1]) {
swap(a[j - 1], a[j]);
j = j + 1;
}
}
if (a[i] < first) {
j = i - 1;
while (j >= 0 && a[j] > a[j + 1]) {
swap(a[j + 1], a[j]);
j = j - 1;
}
}
}
}
Хотя это работает с приведенным выше массивом, похоже, он не может отсортировать следующее: 13 93 58 33 58 63 11 41 87 32. Это заставляет меня поверить, что где-то есть ошибка.
Любая помощь будет оценена.
Решение
Я реализовал это с помощью вектора, я сохраняю позицию начального числа, затем вставляю влево, если число меньше или вправо, если число больше. Затем числа идут влево или вправо, пока они не станут больше или меньше.
Надеюсь это поможет
int poz = 0; //starting value position
vector<int> b;
b.push_back(a[0]);//first value
for (int i = 1; i < n; i++)
{
if (a[i] > prad) //if greater
{
vector<int>::iterator it = b.begin() + poz; //position of starting element
it = b.insert(it + 1, a[i]); //insertion to the right
int t = poz + 1; //position of the inserted element
while (t + 1 < b.size() && b[t] > b[t + 1])
{
swap(b[t], b[t + 1]);
t++; //we go right until our number is greater
}
}
else //same here but instead of going right we go left until the value is lower
{
vector<int>::iterator it = b.begin() + poz;
it = b.insert(it, a[i]);
poz++;
int t = poz - 1;
while (t > 0 && b[t] < b[t - 1])
{
swap(b[t], b[t - 1]);
t--;
}
}
}
Другие решения
Первое, что я заметил, это то, что хотя выбранное значение отсутствует, соответствующего выбранного индекса нет. Так что это должно было быть добавлено и использовано.
Во-вторых, выбранное значение является только границей. И каждый раз, когда сортируемое в данный момент значение всплывает вниз.
В общем, это всего лишь стандартная сортировка вставок. (Это если я правильно понял алгоритм.)
Переименованы переменные i а также j в to_sort_idx а также look_at_idx,
void twowaysort( int a_size, int a[] )
{
if ( a_size < 2 )
return;
int selected_idx = 0;
int selected_value = a[ selected_idx ];
for ( int to_sort_idx = 1; to_sort_idx < a_size; to_sort_idx++ )
{
if ( a[ to_sort_idx ] > selected_value )
{
int look_at_idx = to_sort_idx;
while ( look_at_idx > selected_idx && a[ look_at_idx ] < a[ look_at_idx - 1] )
{
std::swap( a[ look_at_idx -1 ], a[ look_at_idx ] );
--look_at_idx;
}
}
else //if ( a[ to_sort_idx ] <= selected_value )
{
int look_at_idx = to_sort_idx - 1;
while ( look_at_idx >= 0 && a[ look_at_idx ] > a[ look_at_idx + 1 ] )
{
std::swap( a[ look_at_idx ], a[ look_at_idx + 1] );
--look_at_idx;
}
++selected_idx;
}
}
}
Проблема здесь в том, что ваш алгоритм делает только один проход в массиве, где меняются целые числа. Из-за перестановки 93 в обратном направлении при первом проходе вторая итерация рассматривает [2], которое теперь составляет 33 (а не 58). Таким образом, вы по существу пропустили обработку 58. Этот алгоритм только частично сортирует массив. Вы должны сделать несколько проходов здесь, чтобы получить то, что вы хотите …
void twowaysort(int n, int a[])
{
int j;
int first;
for (int k = 0; k < n; ++k)
{
first = a[0];
for (int i = 1; i < n; i++)
{
if (a[i] > first)
{
j = i + 1;
while (j <= n - 1 && a[j] < a[j - 1])
{
swap(a[j - 1], a[j]);
j = j + 1;
}
}
if (a[i] < first)
{
j = i - 1;
while (j >= 0 && a[j] > a[j + 1])
{
swap(a[j + 1], a[j]);
j = j - 1;
}
}
}
}
}
выход: 11 13 32 33 41 58 58 63 87 93