Застопорился с qsort - Компьютерный форум OSzone.net

Компьютерный форум OSzone.net (http://forum.oszone.net/index.php)

- Программирование и базы данных (http://forum.oszone.net/forumdisplay.php?f=21)

- - Застопорился с qsort (http://forum.oszone.net/showthread.php?t=207331)

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

Суть задачи в следующем:
Дан одномерный массив длиной 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;

 }

Согласно данного описания, алгоритм не полный.
Как я понял qsort надо подсказать, как сравнивать элементы массива между собой.
Остальной ввод/вывод с виду верен, там сложно ошибиться, въедливо не проверял.

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

Вот код:

Код:

#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;

}

}

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 не должна быть составной функцией чего либо еще. Это основная функция, получающая управление после запуска приложения.

Цитата:

Цитата feytan

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

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;

}

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

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

Вот код:

Код:

#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? Но вот какие?

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

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

Задание: Дан одномерный массив длиной 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. Если у кого есть еще какие варианты решения данной задачи пишите.

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