Застопорился с qsort

[feytan]

Суть задачи в следующем:
Дан одномерный массив длиной N. Массив заполняется датчиком случайных чисел (лучше использовать любое распределение, кроме нормального). Необходимо отсортировать массив со случайными числами используя qsort.
Я вроде разобрался с возможностями qsort, но серавно незнаю куда подстаавить и что нужно доделать.

Если возможно поясните что не так делаю или что-то забыл

Вот код:

#include <iostream>
#include<time.h>
using namespace std;

void qsort(int* a, long int left, long int right);

int main ()
{
srand (time(NULL));
int i, N, j, k;

//Задаем количество элементов

cout<<endl<<"Dlina massiva - N: "; //N - длина одномерного массива

cin>>N;

cout<<"\n";

if(N > 0)
{
//Резервируем место на диске под количество элементов
int *a = new int[N];


cout << "Vremennii massiv: " << endl;
for(i=0; i<N; i++)
{
a[i]=rand()%20;

cout<<a[i]<<" ";
}
cout<<"\n";

qsort(a, 0, N);

cout << "\n Konechnii massiv: " << endl;
for (int i = 0; i < N; i++)
cout << a[i] << " ";

delete [] a;
}

else cout<<"\n Chislo elementov ne mozhet byt <=0";

system("pause");

return 0;
}

[lxa85]

Согласно данного (http://www.cppreference.com/wiki/algorithm/qsort) описания, алгоритм не полный.
Как я понял qsort надо подсказать, как сравнивать элементы массива между собой.
Остальной ввод/вывод с виду верен, там сложно ошибиться, въедливо не проверял.

[feytan]

Я пот переделал слегка, но неидет. Может я что-то нетак сделалал или забыл, подскажите

Вот код:

#include <iostream>
#include <cstdlib>

using namespace std;

int compare_ints(const void* a, const void* b)
{
int* arg1 = (int*) a;
int* arg2 = (int*) b;
if( *arg1 < *arg2 ) return -1;
else if( *arg1 == *arg2 ) return 0;
else return 1;

int main ()
{
srand (time(NULL));
int i, N, j, k;

//Задаем количество элементов

cout<<endl<<"Dlina massiva - N: "; //N - длина одномерного массива

cin>>N;

cout<<"\n";

if(N > 0)
{
//Резервируем место на диске под количество элементов
int *a = new int[N];

int size = N;

qsort(a, size, sizeof(int), compare_ints);

cout << "Vremennii massiv: " << endl;
for(i=0; i<N; i++)
{
a[i]=rand()%20;

cout<<a[i]<<" ";
}
cout<<"\n";

qsort(a, size, sizeof(int), compare_ints);

cout << "\n Konechnii massiv: " << endl;
for (int i = 0; i < N; i++)
cout << a[i] << " ";

delete [] a;
}

else cout<<"\n Chislo elementov ne mozhet byt <=0";

system("pause");

return 0;
}
}

[lxa85]

feytan, в фигурных скобочках напутал.
\\ head code ...
int compare_ints(const void* a, const void* b)
{
\\ compare_ints code ...
}
int main ()
{
\\ main code ...
return 0;
}
} не нужна, перенести наверх
Пример работы :
Dlina massiva - N: 25

Vremennii massiv:
17 11 12 10 17 17 8 12 4 18 1 11 9 2 18 14 15 2 17 12 11 19 0 12 15

Konechnii massiv:
0 1 2 2 4 8 9 10 11 11 11 12 12 12 12 14 15 15 17 17 17 17 18 18 19
RUN SUCCESSFUL (общее время: 5с)
из них 4,5 я читал и вводил длину массива.

Функция main не должна быть составной функцией чего либо еще. Это основная функция, получающая управление после запуска приложения.

[El Scorpio]

int compare_ints(const void* a, const void* b)
{ int* arg1 = (int*) a;
int* arg2 = (int*) b;
if( *arg1 < *arg2 )
return -1;
else if( *arg1 == *arg2 )
return 0;
else return 1;
»
Во-первых, поскольку параметры передаются через const void*, то и указатели должны быть const.
Во-вторых, можно и проще код написать


int compare_ints (const void* a, const void* b)
{
int res = *(const int*) b - *(const int*) a;
return (res > 0) ? 1 : (res < 0) ? -1 : 0;
}

Зачем три раза сравнивать два числа, если всё каждый раз всё сводится к вычислению их разности? Куда проще один раз эту разность определить, а потом уже с нулём сравнивать. Ведь сравнение числа с нулём выполняется гораздо быстрее сравнения двух чисел.
И стоит обратить внимание на оператор "?" . Он действует так: (Условие) ? Результат_Если_Истина : Иной_Результат
Здесь мы в одной строке проверяем сразу три возможных варианта и полученный результат передаём на return

[feytan]

El Scorpio,
Спасибо за совет, у меня вот теперь другой вопрос.

Я пытаюсь добавить еще один элемент массива, притом, чтобы массив оставлся отсортированным, но что-то идет не так, или я про что-то не так делаю

Вот код:

#include <iostream>
#include <cstdlib>

using namespace std;

int compare_ints (const void* a, const void* b)
{
int res = *(const int*) a - *(const int*) b;
return (res < 0) ? -1 : (res > 0) ? 1 : 0;
}

int main ()
{
srand (time(NULL));
int i, N, j, k;

//Задаем количество элементов

cout<<endl<<"Dlina massiva - N: "; //N - длина одномерного массива

cin>>N;

cout<<"\n";

if(N > 0)
{
//Резервируем место на диске под количество элементов
int *a = new int[N+1];// резервируем память под массив на 1 элемент больше

int size = N;


cout << "Vremennii massiv: " << endl;
for(i=0; i<N; i++)
{
a[i]=rand()%100;

cout<<a[i]<<" ";
}
cout<<"\n";

qsort(a, size, sizeof(int), compare_ints);

cout << "\nKonechnii massiv1: " << endl;
for (int i = 0; i < N; i++)
cout << a[i] << " ";
cout << "\n";

cout<<endl<<"k: "; //k - случайное число
cin>>k;
cout<<endl;

i=0;
while ((a[i]<k) && (i<N)) //ищем место, куда поставить случайное число
i++;
for (j=N; j>i; j--) //сдвигаем все элементы массива на 1 в конец, чтобы вставить случайный элемент
a[j]=a[j-1];

a[i]=k; //вставляем на найденное место случайный элемент

cout << "Konechnii massiv: " << endl;
for (int i = 0; i < N+1; i++)
cout << a[i] << " ";
cout << endl;

delete [] a;
}

else cout<<"\nChislo elementov ne mozhet byt <=0" << endl;


system("pause");

return 0;
}

[feytan]

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

[feytan]

Нашел решение:

Вот код:

#include <iostream>
#include <cstdlib>

using namespace std;

int compare_ints (const void* a, const void* b)
{
int res = *(const int*) a - *(const int*) b;
return (res < 0) ? -1 : (res > 0) ? 1 : 0;
}

int main ()
{
srand (time(NULL));
int i, N, j, k;

//Задаем количество элементов

cout<<endl<<"Dlina massiva - N: "; //N - длина одномерного массива

cin>>N;

cout<<"\n";

if(N > 0)
{
//Резервируем место на диске под количество элементов
int *a = new int[N+1];// резервируем память под массив на 1 элемент больше

int size = N;


cout << "Vremennii massiv: " << endl;
for(i=0; i<N; i++)
{
a[i]=rand()%100;

cout<<a[i]<<" ";
}
cout<<"\n";

qsort(a, size, sizeof(int), compare_ints);

cout << "\nOtsortirovannii massiv: " << endl;
for (i = 0; i < N; i++)
cout << a[i] << " ";
cout << "\n";

cout<<endl<<"k: "; //k - случайное число
cin>>k;
cout<<endl;

i=0;
while ((a[i]<k) && (i<N)) //ищем место, куда поставить случайное число
i++;
for (j=N; j>i; j--) //сдвигаем все элементы массива на 1 в конец, чтобы вставить случайный элемент
a[j]=a[j-1];

a[i]=k; //вставляем на найденное место случайный элемент

cout << "Konechnii massiv: " << endl;
for (i = 0; i < N+1; i++)
cout << a[i] << " ";
cout << endl;

delete [] a;
}

else cout<<"\nChislo elementov ne mozhet byt <=0" << endl;


system("pause");

return 0;
}

Подскажите, а что нужно добавить, чтобы проводился подсчет количества перестановок в массиве? Если я не ошибаюсь, то нужно просто добавить какие-то условия в compare_ints? Но вот какие?

[lxa85]

ну из методов "костылей" - добавь работу с глобальной переменной типа счетчик.
Увеличивай его в случае "больше" или в случае "меньше". "Поиграйся" в общем.

[feytan]

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

Задание: Дан одномерный массив длиной N. Массив заполняется датчиком случайных чисел (лучше использовать любое распределение, кроме нормального).
Требуется:
1) отсортировать массив со случайными числами;
2) в отсортированный массив, вставить случайное число, чтобы он оставался отсортированным;
3) также на экране после выполнения программы должно появляться сообщение, о том, сколько сравнений элементов сделано программой;
4) также программа должна выдавать сколько времени потребовалось ПК на выполнение программы

Вот мои три разных способа решения задачи:

Первый:

#include <iostream>
#include <cstdlib>
#include<windows.h>

using namespace std;

int compare_count = 0;
int compare(const void* a, const void *b)
{
++compare_count;
return (*(int*)a - *(int*)b);
}

int main ()
{

DWORD t1, t2, d_time;

srand (time(NULL));
int i, N, j, k;
t1 = GetTickCount();
//Задаем количество элементов

N=rand()%100;
cout<<endl<<"Dlina massiva - N: " <<N <<endl; //N - длина одномерного массива

cout<<"\n";

//Резервируем место на диске под количество элементов
int *a = new int[N+1];// резервируем память под массив на 1 элемент больше

int size = N;


cout << "Vremennii massiv: " << endl;
for(i=0; i<N; i++)
{
a[i]=rand()%100;

cout<<a[i]<<" ";
}
cout<<"\n";

t1 = GetTickCount();

qsort(a, size, sizeof(int), compare);

cout << "\nOtsortirovannii massiv: " << endl;
for (i = 0; i < N; i++)
cout << a[i] << " ";
cout << "\n";

cout << "\nKolichestvo sravnenii: " << compare_count <<endl;

k=rand()%100;
cout<< endl << "Sluchainoe chislo - k: " << k <<endl; //k - случайное число
cout<< endl;
i=0;
while ((a[i]<k) && (i<N)) //ищем место, куда поставить случайное число
i++;
for (j=N; j>i; j--) //сдвигаем все элементы массива на 1 в конец, чтобы вставить случайный элемент
a[j]=a[j-1];

a[i]=k; //вставляем на найденное место случайный элемент

cout << "Konechnii massiv: " << endl;
for (i = 0; i < N+1; i++)
cout << a[i] << " ";
cout << endl;

t2 = GetTickCount();
d_time = t2 - t1;

cout<<"\nVremia raboti: "<<d_time<<" milisek\n";

delete [] a;

system("pause");

return 0;
}

Второй:

#include <iostream>
#include <cstdlib>
#include<windows.h>

using namespace std;

int compare_count = 0;
int compare(const void* a, const void *b)
{
++compare_count;
return (*(int*)a - *(int*)b);
}

int main ()
{

DWORD t1, t2, d_time;

srand (time(NULL));
int i, N, j, k;

//Задаем количество элементов

cout<<endl<<"Dlina massiva - N: "; //N - длина одномерного массива

cin>>N;

cout<<"\n";

if(N > 0)
{
//Резервируем место на диске под количество элементов
int *a = new int[N+1];// резервируем память под массив на 1 элемент больше

int size = N;


cout << "Vremennii massiv: " << endl;
for(i=0; i<N; i++)
{
a[i]=rand()%100;

cout<<a[i]<<" ";
}
cout<<"\n";

t1 = GetTickCount();

qsort(a, size, sizeof(int), compare);

cout << "\nOtsortirovannii massiv: " << endl;
for (i = 0; i < N; i++)
cout << a[i] << " ";
cout << "\n";

cout << "\nKolichestvo sravnenii: " << compare_count <<endl;

k=rand()%100;
cout<< endl << "Sluchainoe chislo - k: " << k <<endl; //k - случайное число
cout<< endl;
i=0;
while ((a[i]<k) && (i<N)) //ищем место, куда поставить случайное число
i++;
for (j=N; j>i; j--) //сдвигаем все элементы массива на 1 в конец, чтобы вставить случайный элемент
a[j]=a[j-1];

a[i]=k; //вставляем на найденное место случайный элемент

cout << "Konechnii massiv: " << endl;
for (i = 0; i < N+1; i++)
cout << a[i] << " ";
cout << endl;

t2 = GetTickCount();
d_time = t2 - t1;

cout<<"\nVremia raboti: "<<d_time<<" milisek\n";

delete [] a;
}

else cout<<"Chislo elementov ne mozhet byt <=0" << endl;

system("pause");

return 0;
}

Третий:

#include <iostream>
#include<time.h>
#include<windows.h>

using namespace std;

int main ()
{
DWORD t1, t2, d_time;

srand (time(NULL));

int i, N, j, k;

//Задаем количество элементов

cout<<endl<<"Dlina massiva - N: "; //N - длина одномерного массива

cin>>N;

cout<<"\n";

if(N > 0)
{

//Резервируем место на диске под количество элементов

int *a = new int[N+1];// резервируем память под массив на 1 элемент больше

cout << "Vremennii massiv: " << endl;
for(i=0; i<N; i++)
{
a[i]=rand()%100;
cout<<a[i]<<" ";
}
cout<<"\n";
cout<< endl;

t1 = GetTickCount();

int count=0;
for (i = 0; i < N - 1; i++)
{
for(j = N-1; j>i; j--)
if (a[j-1] > a[j])
{
swap(a[j], a[j-1]); count++;
}
}
cout << "Otsortirovannii massiv: " << endl;
for (i = 0; i < N; i++)
cout << a[i] << " ";
cout<< endl;

cout<<"\nKolichestvo perestanovok: "<<count;
cout<< endl;

k=rand()%100;
cout<< endl << "Sluchainoe chislo - k: " << k <<endl; //k - случайное число
cout<< endl;

i=0;
while ((a[i]<k) && (i<N)) //ищем место, куда поставить случайное число
i++;
for (j=N; j>i; j--) //сдвигаем все элементы массива на 1 в конец, чтобы вставить случайный элемент
a[j]=a[j-1];

a[i]=k; //вставляем на найденное место случайный элемент

cout << "Konechnii massiv: " << endl;
for (i = 0; i < N+1; i++)
cout << a[i] << " ";
cout <<"\n";

t2 = GetTickCount();
d_time = t2 - t1;

cout<<"\nVremia raboti: "<<d_time<<" milisek\n";

delete [] a;
}

else cout<<"Chislo elementov ne mozhet byt <=0" << endl;

system("pause");

return 0;
}

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

P.S. Если у кого есть еще какие варианты решения данной задачи пишите.

Всем спасибо за помощь в решении задачи.