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

@Feytan · Регистрация: 09.12.2010

Author24 — интернет-сервис помощи студентам

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

C++

#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];// резервируем память под массив на 1 элемент больше
 
 
        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;
}

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

@iama · 22.05.2011, 00:58

В <algorithm> есть функция sort (рекурсивная сортировка), аргументы - начала и конец вектора для сортировки:

C++

vector <int> a;
 
...
 
sort(a.begin(), a.end());

@asics · 22.05.2011, 01:01

Сообщение от Feytan

C++

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

qsort() - это стандартная фнукия из cstdlib, зачем вы ее заново определяете ?

Добавлено через 59 секунд
Пример использования см. тут.

@easybudda · 22.05.2011, 01:06

C

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
    
int cmp(const void * a, const void * b){
    return *(int*)a - *(int*)b;
}
 
void dump(const int * arr, size_t size){
    while ( size-- )
        printf("%02d ", *arr++);
    printf("\n");
}
 
#define SIZE 10
    
int main(void){
    int arr[SIZE], i;
    
    srand(time(NULL));
    for ( i = 0; i < SIZE; ++i )
        arr[i] = rand() % 100;
    
    printf("Before: ");
    dump(arr, SIZE);
    
    qsort(arr, SIZE, sizeof(int), cmp);
    
    printf("After:  ");
    dump(arr, SIZE);
    
    return 0;
}

@Feytan · 22.05.2011, 01:41 **[ТС]**

asics,

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

C++

#include <iostream>
#include <stdlib.h>
#include<time.h>
using namespace std;
 
 
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;
}

@Feytan · 23.05.2011, 10:48 **[ТС]**

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

Вот код:

C++

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

@Nameless One · 23.05.2011, 11:09

Feytan, а чем решение выше не нравится?

@lemegeton · 23.05.2011, 11:09

C++

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;

Скобочку забыли закрыть фигурную.
Поскольку функция сравнения должна возвращать любое положительное или отрицательное число, её можно написать проще.

C++

1
2
3

int compare(const void* a, const void *b) {
  return (*(int*)a - *(int*)b);
}

@Feytan · 23.05.2011, 13:40 **[ТС]**

lemegeton,
Спасибо, дейтвительно скобку забыл поставить.

Я вот попытался с добавлением еще одного случайного элемента, но что-то идет не так как надо

Вот код:

C++

#include <iostream>
#include <cstdlib>
#include<time.h>
 
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+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 (int i = 0; i < N; i++)
                cout << a[i] << "  ";
                cout << endl;
                
        cout<<"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<<"\n Chislo elementov ne mozhet byt <=0";
 
    system("pause");
    
        return 0;
}

@Feytan · 24.05.2011, 13:42 **[ТС]**

Я немного код изменил и добавил в нем условие увеличение на 1 число.
Вот код:

C++

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

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

@Nameless One · 24.05.2011, 13:46

Feytan, в функции compare_ints изменять глобальный счетчик

@lemegeton · 24.05.2011, 15:45

C

...
 
int compare_count = 0;
int compare(const void* a, const void *b) {
  return (*(int*)a - *(int*)b);
  ++compare_count;
}
 
int main(int argc, char **argv) {
...
  sqort(a, size, sizeof(int), compare);
  printf("%d", compare_count);
...
}

@lasbat · 24.05.2011, 15:46

Сообщение от Feytan

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

можно использовать свою сортировку, а не из STL

C++

void quickSort(int arr[], int left, int right) {
      int i = left, j = right;
      int tmp;
      int pivot = arr[(left + right) / 2];
 
      /* partition */
      while (i <= j) {
            while (arr[i] < pivot)
                  i++;
            while (arr[j] > pivot)
                  j--;
            if (i <= j) {
                  tmp = arr[i];
                  arr[i] = arr[j];
                  arr[j] = tmp;
                  i++;
                  j--;
                  //куда-нибудь сюда можно запилить счетчик и передавать его через абсолютную   
                  //адресацию, типа quickSort(int arr[], int left, int right,int &count) 
            }
      };
 
      /* recursion */
      if (left < j)
            quickSort(arr, left, j);
      if (i < right)
            quickSort(arr, i, right);
}

например такую

@ForEveR · 24.05.2011, 16:02

lasbat, qsort такой STL...

@lemegeton · 24.05.2011, 16:03

Опечатался. Должно быть

C

...
 
int compare_count = 0;
int compare(const void* a, const void *b) {
  ++compare_count;
  return (*(int*)a - *(int*)b);
}
 
int main(int argc, char **argv) {
...
  sqort(a, size, sizeof(int), compare);
  printf("%d", compare_count);
...
}

@lasbat · 24.05.2011, 16:13

Сообщение от ForEveR

lasbat, qsort такой STL...

я имел в виду встроенную=)

@ForEveR В астрале 8049 / 4806 / 655 Регистрация: 24.06.2010 Сообщений: 10,562
	24.05.2011, 16:02	14
	lasbat, qsort такой STL... 0

@Nameless One 5828 / 3479 / 358 Регистрация: 08.02.2010 Сообщений: 7,448
	23.05.2011, 11:09	7
	Feytan, а чем решение выше не нравится? 0

@Nameless One 5828 / 3479 / 358 Регистрация: 08.02.2010 Сообщений: 7,448
	24.05.2011, 13:46	11
	Feytan, в функции compare_ints изменять глобальный счетчик 0

@lasbat 3 / 3 / 4 Регистрация: 06.05.2010 Сообщений: 18
	24.05.2011, 16:13	16
	Сообщение от ForEveR lasbat, qsort такой STL... я имел в виду встроенную=) 0