найти ошибку в задаче.

[Koshak]

Требуется отсортировать один и тот же массив тремя видами сортировки.Обменом,выбором и вставками.

мой код

#include
#include
using namespace std;
int main ()
{
setlocale(LC_ALL,"Russian");
const int n=10;
int x[n],i,j,q=0,z=0,k,t,m,h,temp;
cout << "Задайте массив из " << n << " элементов для сортировки обменом" << endl;
srand (time(NULL));
for (i=0;i cin >> x[i];
cout << endl;
for (i=0;i for (j=1;j if (x[j-1]>x[j])
{
m=x[j-1];
x[j-1]=x[j];
x[j]=m;
z++;
}
for (i=0;i cout << x[i] << " ";
cout << endl;
z=z*3;
cout << "количество сравнений = " << q << "\n";
cout << "количество присваиваний = " << z << "\n";
cout << endl;
cout << "Введите тот же массив для сортировки методом выбора";
cout << endl;
for (i=0;i cin >> x[i];
cout << endl;
q=0;z=0;
for (i=0;i for (j=i+1;j if (x[j] {
swap(x[j],x[i]);
z++;
}
for (i=0;i cout << x[i] << " ";
cout << endl;
cout << "количество сравнений = " << q << "\n";
z=z*3;
cout << "количество присваиваний = " << z << "\n";
cout << endl;
cout << "Введите тот же массив для сортировки методом вставки" << endl;
cout << endl;
for(i=0;i cin >> x[i];
q=0,z=0;
for (i=1;i for(j=1;j while((j>0) && (x[j-1]>x[j]))
{
swap(x[j-1],x[j]);
z++;
}
for (i=0;i cout << x[i] << " ";
cout << endl;
cout << "Количество сравнений = " << q << endl;
z=z*3;
cout << "Количество присваиваний = " << z << endl;
system("pause >> void");
return 0;
}

#include 

программа выдает неверные результатыпомогите найти ошибку.

[Vsadnik665]

Не поможем. Ничего тебя не учит. Учись сам.

ps.Ты каждую задачку выкладываешь сюда?

[Rowdy]

по моему, этот код из просторов интернета

[L0K1]

Rowdy

infa 105, кто у нас цепляет локали в лабораторке

[Koshak]

Rowdy

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

[nonlux]

Вообще то Koshak прав.

Говнокод тяжело искать в просторах интернета.

Koshak

То что ты пишешь называется спагети-код.

Это не самый лучший метод написаниния программы.

Напиши тоже но например в виде функций хотя бы, чтобы чувствовалась логики приложения.

А потом дальше будем разбирать ошибки

[Koshak]

хорошо,я попробую

я нашел место,где есть ошибка,но не могу исправить ее.

когда идет сортировка методом обмена

srand (time(NULL));
for (i=0;i cin >> x[i];
cout << endl;
for (i=0;i for (j=1;j if (x[j-1]>x[j])
{
m=x[j-1];
x[j-1]=x[j];
x[j]=m;
z++;
}
for (i=0;i cout << x[i] << " ";
cout << endl;
cout << "количество сравнений = " << q << "\n";
cout << "количество присваиваний = " << z << "\n";

 cout << "Задайте массив из " << n << " элементов для сортировки обменом" << endl;

для массива 5 19 4 7 15 12 1 6 10 8 он выводит 90 сравнений, хотя я посчитал на бумаге и их там 45.значит он в каком, то месте дважды проходит по массиву

[martinges]

for (i=0;i

for (j=1;j

//n=10, внутренний цикл n-1 итераций, внешний n итераций----> n*(n-1)=n^2-n=90

//переменная q у тебя вертится именно 90 раз)

[Koshak]

спасибо

вроде все хорошо, только он для любого вида сортировки выдает одинаковое количество присваиваний

[martinges]

тааакс стоп.... сам алгоритм я как то хреново просмотрел)) это же не метод обмена(пузырька) у тебя во внутреннем цикле кавардак))

по идее итерация и ты опустил в конец(начало) самый лёгкий или самый тяжелый элемент и на следующий итерации его не учитываешь) а в твоем цикле ты "на всякий случай" его все равно проверишь в итоге избыточное количество итераций

for (i=0;i

for (j=i+1;j ну или

for (i=n;i>0;i--)

for (j=0;j

[Koshak]

сделал так

for (i=n;i>0;i--)

for (j=0;j

но теперь выводятся неверные результаты

Добавлено спустя 2 минуты 9 секунд:

кстати,препод сказал, что

это

cout << "Введите тот же массив для сортировки методом выбора";
cout << endl;
for (i=0;i cin >> x[i];
cout << endl;
q=0;z=0;
for (i=0;i for (j=i+1;j if (x[j] {
swap(x[j],x[i]);
z++;
}
for (i=0;i cout << x[i] << " ";
cout << endl;
cout << "количество сравнений = " << q << "\n";
z=z*3;
cout << "количество присваиваний = " << z << "\n";
cout << endl;

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

cout << "Введите тот же массив для сортировки методом вставки" << endl;
cout << endl;
for(i=0;i cin >> x[i];
q=0,z=0;
for (i=1;i for(j=1;j while((j>0) && (x[j-1]>x[j]))
{
swap(x[j-1],x[j]);
z++;
}
for (i=0;i cout << x[i] << " ";
cout << endl;
cout << "Количество сравнений = " << q << endl;
z=z*3;
cout << "Количество присваиваний = " << z << endl;
system("pause >> void");
return 0;
}

нихрена не мотед вставок.

[martinges]

гг точно)) вспомнил)

соседи - пузырек

обмен - фиксация одного и обмен по второму циклу

вставка - побегушки сначала с малого массива потом расширяешь

P.S. Koshak ну вот видишь как плохо нихрена не проверять код на работоспособность

[Koshak]

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

и кстати,переделал сортировку обменом

cout << endl;
for (i=0;i cin >> x[i];
cout << endl;
int imin;
q=0;z=0;
for (i=0;i {
k=i,imin=x[i];
for(j=i+1;j {
if(x[j] k=j,imin=x[j];
}
x[k]=x[i];
x[i]=imin;
z++;
}
for (i=0;i cout << x[i] << " ";
cout << endl;
cout << "количество сравнений = " << q << "\n";
z=z*3;
cout << "количество присваиваний = " << z << "\n";
cout << endl;

cout << "Введите тот же массив для сортировки методом выбора";

теперь он всегда выводит количество сравнений 45,а присваиваний 30:(

Добавлено спустя 2 минуты 18 секунд:

и переделал сортировку вставками

cout << endl;
int w;
for(i=0;i cin >> x[i];
q=0,z=0;
for (i=1;i {
w=x[i];
j=i-1;
while(j>=0 && x[j]>w)
{
x[j+1]=x[j];
j--;
z++;
}
x[j+1]=w;
}
for (i=0;i cout << x[i] << " ";
cout << endl;
cout << "Количество сравнений = " << q << endl;
z=z*3;
cout << "Количество присваиваний = " << z << endl;

cout << "Введите тот же массив для сортировки методом вставки" << endl;

вроде нормально, но незнаю в какое место ставить счетчик

[Koshak]

ребят,посмотрите пожалуйста.

вот конечный вариант программы,там что-то не так с методом выбора.он ВСЕГДА выводит числа 45 и 30 для любого массива.а с методом вставок он ВСЕГДА выводит количество присваиваний 30.

#include
#include
using namespace std;
int main ()
{
setlocale(LC_ALL,"Russian");
const int n=10;
int x[n],i,j,q=0,z=0,k,t,m,h,temp;
cout << "Задайте массив из " << n << " элементов для сортировки обменом" << endl;
srand (time(NULL));
for (i=0;i cin >> x[i];
cout << endl;
for (i=0;i for (j=n-1;j>i;j--,q++)
{
if (x[j-1]>x[j])
{
m=x[j-1];
x[j-1]=x[j];
x[j]=m;
z++;
}
}
for (i=0;i cout << x[i] << " ";
cout << endl;
cout << "количество сравнений = " << q << "\n";
z=z*3;
cout << "количество присваиваний = " << z << "\n";
cout << endl;
cout << "Введите тот же массив для сортировки методом выбора";
cout << endl;
for (i=0;i cin >> x[i];
cout << endl;
int imin;
q=0;z=0;
for (i=0;i {
k=i,imin=x[i];
for(j=i+1;j if(x[j] {
k=j,imin=x[j];
}
x[j]=x[i];
x[i]=imin;
z++;
}
for (i=0;i cout << x[i] << " ";
cout << endl;
cout << "количество сравнений = " << q << "\n";
z=z*3;
cout << "количество присваиваний = " << z << "\n";
cout << endl;
cout << "Введите тот же массив для сортировки методом вставки" << endl;
cout << endl;
int w;
for(i=0;i cin >> x[i];
q=0,z=0;
for (i=0;i {
w=x[i];
for (j=i-1;j>=0 && x[j] > w;j--,q++)
x[j+1]=x[j];
x[j+1]=w;
z++;
}
for (i=0;i cout << x[i] << " ";
cout << endl;
cout << "Количество сравнений = " << q << endl;
z=z*3;
cout << "Количество присваиваний = " << z << endl;
system("pause >> void");
return 0;
}

#include 

[nonlux]

Koshak

Бл.......$#$?++$+#?$#

если до завтра терпит, то покажу как должна выглядеть нормальная программа.

но попробуй после этого писать такой код)

[Koshak]

попробую

[nonlux]

maip.cpp

#include "SortAlgorithmInfo.cpp"

int main(int argc, char** argv) {
int arrLen = 20;
int arr[] = {32, 4, 21, 5, 23, 66, 3, 56, 556, 67, 69, 67, 34, 23, 12, 89, 43, 12, 56, 99};
new SortAlgorithmInfo(arr, arrLen, BUBLE);
new SortAlgorithmInfo(arr, arrLen, INSERT);
new SortAlgorithmInfo(arr, arrLen, SELECTION);
}

SortAlgorithmInfo.cpp

#include "AbsrtactSortAlgorithm.cpp"
#include "BubbleSortAlgorithm.cpp"
#include "InsertSortAlgorithm.cpp"
#include "SelectionSortAlgorithm.cpp"

const int BUBLE =0;
const int INSERT=1;
const int SELECTION=2;
class SortAlgorithmInfo {
private:

void printArray(int *arr, int len, char *text) {
printf("%s:", text);
for (int i = 0; i < len; i++) {
printf("%i ", arr[i]);
}
printf("\r\n");
}
void printAlgorithmInfo(AbstractSortAlgorithm *alg, char *text){
printf("%s\r\nShift:%i\r\nCondition:%i\r\n",text,alg->getShiftCount(),alg->getConditionCount());
}
AbstractSortAlgorithm* algorithmFactory(int type){
switch(type){
case BUBLE:
return new BubleSortAlgorithm();
case INSERT:
return new InsertSortAlgorithm();
case SELECTION:
return new SelectionSortAlgorithm();
}
}
char * getAlgorithmName(int type){
switch(type){
case BUBLE:
return (char *)"BubleSortAlgorithm";
case INSERT:
return (char *) "InsertSortAlgorithm";
case SELECTION:
return (char *) "SelectionSortAlgorithm";
}
}
public:

SortAlgorithmInfo(int *unsortArray, int len, int algType) {
AbstractSortAlgorithm *alg = algorithmFactory(algType);
int *sortArray = alg->execute(unsortArray, len);
printf("********************************************************\r\n");
printAlgorithmInfo(alg, getAlgorithmName(algType));
printArray(unsortArray, len, (char *) "unsort");
printArray(sortArray, len, (char *) " sort");
printf("********************************************************\r\n");

}
};

#include 

AbsrtactSortAlgorithm.cpp

#ifndef _MY_ASA_
#define _MY_ASA_

class AbstractSortAlgorithm {
protected:
int _shiftCounter;
int _conditionCounter;

void addShift() {
_shiftCounter++;
}

void addCondition() {
_conditionCounter++;
}
public:

AbstractSortAlgorithm(void) {
_shiftCounter = 0;
_conditionCounter = 0;
}

~AbstractSortAlgorithm(void) {
};

int getShiftCount() {
return _shiftCounter;
}

int getConditionCount() {
return _conditionCounter;
}
virtual int* execute(int* unsortArray, int len) = 0;
};
#endif

BubbleSortAlgorithm.cpp

#include "AbsrtactSortAlgorithm.cpp"
#include
#include
class BubleSortAlgorithm : public AbstractSortAlgorithm{
public:

int* execute(int* unsortArray, int len){
int *sortArray=new int[len];
memcpy(sortArray,unsortArray,sizeof(int)*len);
for(int i=len-1;i>=0;i--){
bool shifted=false;
for(int j=0;j addCondition();
if (sortArray[j]>sortArray[j+1]){
addShift();
int temp=sortArray[j];
sortArray[j]=sortArray[j+1];
sortArray[j+1]=temp;
shifted=true;
}
}
if (!shifted)
break;
}
return sortArray;
};
};

InsertSortAlgorithm.cpp

#include "AbsrtactSortAlgorithm.cpp"
#include
#include

class InsertSortAlgorithm : public AbstractSortAlgorithm {
public:

int* execute(int* unsortArray, int len) {
int *sortArray = new int[len];
memcpy(sortArray, unsortArray, sizeof (int) *len);
for (int i = 0; i < len; i++) {
int insertItem = sortArray[i];
for (int j = i - 1; j >= 0 && sortArray[j] > insertItem; j--) {
addCondition();
addShift(); //!!!!Condition==Shift+1
sortArray[j + 1] = sortArray[j];
sortArray[j] = insertItem;
}
if (i)
addCondition();
}
return sortArray;
};
};

SelectionSortAlgorithm.cpp

#include
#include

class SelectionSortAlgorithm : public AbstractSortAlgorithm {
public:

int* execute(int* unsortArray, int len) {
int *sortArray = new int[len];
memcpy(sortArray, unsortArray, sizeof (int) *len);
for (int i = 0; i < len; i++) {
int shiftPos = i;
int min = sortArray[i];
for (int j = i + 1; j < len; j++) {
addCondition();
if (sortArray[j] < min) {
min = sortArray[j];
shiftPos = j;
}
}
if (shiftPos != i) {
addShift();
sortArray[shiftPos] = sortArray[i];
sortArray[i] = min;
}
}
return sortArray;
};
};

#include "AbsrtactSortAlgorithm.cpp"

Добавлено спустя 1 минуту 20 секунд:

Вот как то так *124

[Koshak]

спасибо, только не понятны некоторые строчки.

                addShift(); //!!!!Condition==Shift+1
            }
            if (i)
                addCondition();
        }

вот эти

[nonlux]

алгоритм вставок

пример на 4 проходе

1342....

сравнение 2 и 4 престановка 2 и 4

сравнение 2 и 3 престановка 2 и 3

сравнение 2 и 1 престановок нет

то есть сравнений на любом шаге будет на одно больше.

но на первом шаге когда i равно 0 сколько будет сравнений?

цикл не будет проходить так как -1 элемента в массиве нет

поэтому я и добавил +1 перестановку

а условие if(i) тоже самое что и if(i>0)

Р.S.

если ты хочушь стать нормальным программером

сравни свой код и мой

какой легче читать и искать в нем ошибки, модифицировать, твой или мой?

не пиши говнокод в котором ты сам не можешь отследить что и куда утекает,

продумывай структу программы, вникни в конструкции языка,что такое ооп например,

почитай что такое рефакторинг, и что такое паттерны проектирования.

это в вузе преподаватели поощряют говнокод, в реальной жизни приложение умрет.

а главное делай это красиво, так и желание и мотивация и самооцека растут,

[superman]

Если не возражаете, несколько общих заметок по коду выше: за памятью нужно следить (подразумевается не просто добавление delete[], а осмысленное выделение), С++ дает много плюшек, в данном случае стоит использовать как минимум enum, const, убрать C-style касты.

[nonlux]

superman

Спасибо, полностью согласен. Этого нет в примере, потому что:

1. Я не C/C++ программист, а web), и последнее програ на С++ была написана более трех лет назад.

2. В примере хотелось показать не тонкости работы с коткрентым языком, а общий подход к написанию приложения,используюя слабую связность, и паттерны программирования( проектирования). Потому как видя код топик стартера пришел в свящетое Неистовство))), ибо так учат писать в ВУЗе, а точнее не совсем не учат.

Например тут я попытался изобразить праттерн Стратегия.

Это классы AbstractSortAlgorithm и наследники. Используя подобную технику можно свободно выбирать необходимую реализацию того или иного действия.

То есть если представить, что в нашей проге очень важно быстро сортировать массивы.

Допустим

BubbleSort оптимален на массивах до 100 элементов

InsertSort оптимален на массивах от 100 до 500

а SelectSort оптемален на остальных

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

А для получения нужного алгоритма можно использовать еще один паттерн фабричный метод

пример SortAlgorithmInfo::algorithmFactory

Добавлено спустя 51 секунду:

убрать C-style касты

Кстати это что ? и почему убрать?

[Koshak]

к сожалению, я не умею писать таким образомменя учили именно такно я пока только 2 курс

вставки не сортируетможет что-то не так сделал?

cout << "Введите тот же массив для сортировки методом вставки" << endl;
	cout << endl;
	int w;
	for(i=0;i		cin >> x[i];
	q=0,z=0;
	for (i=1;i	{
		w=x[i];
		for (j=i-1;j>=0 && (x[j] > w);j--)
			q++;
		z++;z=z+1;
			x[j+1]=x[j];
		x[j+1]=w;
	}
	if(i>0)
	{
		z++;
	}

[nonlux]

вот и начни писать так,

напиши все алгоритмы в отдельных функциях

отдельно сделай функцию ввода

отдельно вывода

а так и посмотрим)

Добавлено спустя 3 минуты 26 секунд:

хотя я вижу где ошибка)))...

если тебе нах не нужно писать проги и это тебе не интересно скажи, и узнаешь где ошибка

если интересно напишим красивую прогу)

[superman]

nonlux

ну да, в общем то идея понятна. Заметки касаются только мелких деталей реализации.

Кстати это что ? и почему убрать?

Это приведение типов, например

(char*)"sort"

Чтобы приводить указатели как правило можно использовать одно или комбинацию из: static_cast, dynamic_cast, reinterpret_cast, const_cast. В данном случае (char*)"sort" эквивалентно const_cast.

Почему убрать - потому что касты в стиле C обычно либо вообще не нужны, либо правильнее явно заменяются одним из вышеперечисленных. В данном случае каст не нужен и не правилен. Нужно использовать тип "const char*" в параметрах функции, а не насильно снимать константность с статической строки (такие строки в большинстве случаев размещаются в Read-Only памяти, случайная запись туда приведет к сбою).

[Koshak]

nonlux , у меня есть еще одна программа.подобие такой, только там нужное реализовать сортировку вставками, сортировку бинарными вставками и сортировку Шелла.вот ее и попробую по твоему методу писать,а эту уж так допишу

ошибка где-то тут?)

  q++;
     z++;z=z+1;
       x[j+1]=x[j];
     x[j+1]=w;
   }
   if(i>0)
   {
     z++;
}

P.s. а зачем писать функции для ввода и вывода,если можно сделать

cin >> x[i]-ввод,cout << x[i]-вывод

?