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

feytan · 22 Май 2011

Застопорился с 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=rand()%20;

cout<<a<<" ";
}
cout<<"\n";

qsort(a, 0, N);

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

delete [] a;
}

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

system("pause");

return 0;
}

feytan · 23 Май 2011

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

Вот код:

#include <iostream>
#include <cstdlib>

using namespace std;

int compare_ints(const void* a, const void* b) // comparison function
{
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=rand()%20;

cout<<a<<" ";
}
cout<<"\n";

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

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

delete [] a;
}

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

system("pause");

return 0;
}
}

feytan · 24 Май 2011

Что-то делаю не так, подскажите

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

Вот код:

Код:

#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 · 24 Май 2011

Нашел ответ. Если у кого есть другие варианты буду рад их увидеть

Ответ пришел: Уберал int перед i во всех циклах for
И все заработало нормально.

Вот код:

Код:

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

Если у кого есть другие варианты буду рад их увидеть

feytan · 24 Май 2011

И еще вопрос: если нужно добавить подсчет количества перестановок в массиве, то что нужно добавить в этой программе?

feytan · 25 Май 2011

Одномерный массив

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

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

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

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

feytan

Ученик

feytan

Ученик

feytan

Ученик

Вложения

feytan

Ученик

feytan

Ученик

feytan

Ученик