Всем добрый вечер. У меня есть программа по сортировкам на стадии бета-версии. Суть отсортировать строки исходного массива по возрастанию. И есть одна проблема с сортировкой методом "вставка". Вроде сравнения он считает правильно, но вот перестановки почему то всегда отображаются в виде нуля. Я закомментил часть, где считается вставкой. Если вы мне поможете найти ошибку, я буду очень благодарен. Заранее спасибо.
| Код |
/*////////////////////////
Lab: Sortings ////
Name: output console ////
/*////////////////////////
#include "stdafx.h"
#include "stdlib.h"
#include <string>
#include <iostream>
#include <time.h>
using namespace std;
int Quicksort(int *arr5, int left, int right, int& shift, int& ask)
{
register int i, q, j = 0;
int xx, tmp;
i = left; q = right;
xx = arr5[(left + right) / 2];
do {
while (arr5[i]<xx && i<right)i++;
while (xx<arr5[q] && q>left) q--;
if (i <= q)
{
ask++;
tmp = arr5[i];
arr5[i] = arr5[q];
arr5[q] = tmp;
if (arr5[i] < arr5[q])
{
shift++;
//ask--;
}
i++;
q--;
}
} while (i <= q);
if (left<q) Quicksort(arr5, left, q, shift, ask);
if (i<right) Quicksort(arr5, i, right, shift, ask);
return *arr5, shift, ask;
}
int _tmain(int argc, _TCHAR* argv[])
{
setlocale(LC_CTYPE, "Russian");
int line, column;
cout << "Введите количество строк от 1 до 15: \n";
lines:
cin >> line;
if (line >= 1 && line <= 15)
{
cout << endl;
}
else
{
cout << "Недопустимое значение, введите ещё раз" << endl;
goto lines;
}
cout << "Введите количество столбцов от 1 до 15: \n";
columns:
cin >> column;
if (column >= 1 && column <= 15)
{
cout << endl;
}
else
{
cout << "Недопустимое значение, введите ещё раз" << endl;
goto columns;
}
int arr[15][15];
int arr2[15][15];
int arr12[15][15];
srand(time(NULL));
int *arr5 = new int[column];
cout << "Исходный массив" << endl << endl;
for (int i = 0; i<line; i++)
{
for (int j = 0; j<column; j++)
{
arr12[i][j] = arr2[i][j] = arr[i][j] = rand() % 100;
printf("%4i", arr[i][j]);
}
cout << endl;
}
cout << endl;
int shift_1 = 0; //сравнения для пузырька
int comparison_1 = 0; //перестановки для пузырька
printf("Пузырь");
for (int i = 0; i < line; i++)
for (int j = 0; j < column - 1; j++)
for (int k = j + 1; k < column; k++)
{
if (abs(arr[i][j]) > abs(arr[i][k]))
{
int t;
t = arr[i][j];
arr[i][j] = arr[i][k];
arr[i][k] = t;
shift_1++;
}
comparison_1++;
}
cout << endl << endl;
for (int i = 0; i<line; i++)
{
for (int j = 0; j<column; j++)
{
printf("%4i", arr[i][j]);
}
cout << endl;
}
cout << "\n";
printf("-------------------------------------------------------------\n");
printf("| Метод сортировки | Кол-во перестановок | Кол-во сравнений |\n");
printf("-------------------------------------------------------------\n");
printf("| Bubble | %19i | %16i |\n", shift_1, comparison_1);
printf("____________________________________________________________|");
int k = 0, i, j;
cout << endl << endl << endl;
cout << "Отбор" << endl << endl;
bool z = 0;
int shift_2 = 0;
int comparison_2 = 0;
for (j = 0; j < line; j++)
{
k = 0;
int H = 0;
while (k <= column - 1)
{
for (i = k + 1; i < column; i++)
{
if (abs(arr2[j][i]) < abs(arr2[j][k]))
{
int temp = arr2[j][k];
arr2[j][k] = arr2[j][i];
arr2[j][i] = temp;
H = i;
z = 1;
shift_2++; //перестановки
}
comparison_2++; //сравнения
}
k++;
}
}
for (int i = 0; i<line; i++)
{
for (int j = 0; j<column; j++)
{
printf("%4i", arr2[i][j]);
}
cout << endl;
}
cout << endl << endl << endl;
printf("-------------------------------------------------------------\n");
printf("| Метод сортировки | Кол-во перестановок | Кол-во сравнений |\n");
printf("-------------------------------------------------------------\n");
printf("| Select | %19i | %16i |\n", shift_2, comparison_2);
printf("____________________________________________________________|");
cout << endl << endl << endl;
///////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////
/*ВСТАВКА
///////////////////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////////////////*/
cout << "Вставка";
cout << endl << endl;
int temp;
int shift_10 = 0;
comparison_1 = 0;
j = 0;
int *arr3 = new int[column];
do
{
for (int i = 0; i < column; i++)
{
arr3[i] = arr[j][i];
}
int tmp = 0;
for (int i = 1; i<column; i++)
{
temp = arr3[i];
int W;
for (W = i - 1; W >= 0 && temp < arr3[W]; W--)
{
arr3[W + 1] = arr3[W];
shift_10++;
}
arr3[W + 1] = temp;
comparison_1++;
}
for (int i = 0; i < column; i++)
{
printf("%4i", arr3[i]);
}
cout << endl;
j++;
} while (j < line);
cout << endl << endl << endl;
printf("-------------------------------------------------------------\n");
printf("| Метод сортировки | Кол-во перестановок | Кол-во сравнений |\n");
printf("-------------------------------------------------------------\n");
printf("| Insert | %19i | %16i |\n", shift_10, comparison_1);
printf("____________________________________________________________|");
cout << endl << endl;
//////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////
//harder, darker, faster
//nothing but hardcore!
j = 0;
cout << "Quicksort" << endl << endl;
int shift = 0, ask = 0;
do
{
for (int i = 0; i < column; i++)
{
arr5[i] = arr12[j][i];
}
Quicksort(arr5, 0, column - 1, shift, ask);
for (int i = 0; i < column; i++)
{
printf("%4i", arr5[i]);
}
cout << endl;
j++;
} while (j < line);
cout << endl << endl;
printf("-------------------------------------------------------------\n");
printf("| Метод сортировки | Кол-во перестановок | Кол-во сравнений |\n");
printf("-------------------------------------------------------------\n");
printf("| Quick | %19i | %16i |\n", shift, ask);
printf("____________________________________________________________|");
cout << endl << endl << endl;
cout << "Shell" << endl << endl;
j = 0;
shift = 0;
ask = 0;
int *arr4 = new int[column];
do
{
for (int i = 0; i < column; i++)
{
arr4[i] = arr12[j][i];
}
int gap, k;
int w;
int temp;
char a[5] = { 9, 5, 3, 2, 10 };
for (k = 0; k<5; k++)
{
int temp, q = 0;
int gap = a[k];
for (i = gap; i<column; i++)
{
temp = arr4[i];
for (q = i - gap; temp < arr4[q] - 1 && q >= 0; q = q - gap)
{
arr4[q + gap] = arr4[q];
shift++;
}
arr4[q + gap] = temp;
ask++;
}
}
Quicksort(arr4, 0, column - 1, shift_2, comparison_1);
for (int i = 0; i < column; i++)
{
printf("%4i", arr4[i]);
}
cout << endl;
j++;
} while (j<line);
cout << endl << endl;
printf("-------------------------------------------------------------\n");
printf("| Метод сортировки | Кол-во перестановок | Кол-во сравнений |\n");
printf("-------------------------------------------------------------\n");
printf("| Shell | %19i | %16i |\n", shift, ask);
printf("____________________________________________________________|");
cout << endl << endl;
system("pause");
return 0;
}
|
|