Форум программистов, компьютерный форум CyberForum.ru

Застопорился с qsort - C++

Восстановить пароль Регистрация
 
Feytan
1 / 1 / 0
Регистрация: 09.12.2010
Сообщений: 93
22.05.2011, 00:52     Застопорился с qsort #1
Суть задачи в следующем:
Дан одномерный массив длиной N. Массив заполняется датчиком случайных чисел (лучше использовать любое распределение, кроме нормального). Необходимо отсортировать массив со случайными числами используя qsort.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#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;
}
Если возможно поясните что не так делаю
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
22.05.2011, 00:52     Застопорился с qsort
Посмотрите здесь:

C++ qsort
qsort C++ C++
C++ Qsort
C++ qsort
C++ не работает qsort
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
iama
 Аватар для iama
1249 / 974 / 48
Регистрация: 30.07.2010
Сообщений: 5,297
22.05.2011, 00:58     Застопорился с qsort #2
В <algorithm> есть функция sort (рекурсивная сортировка), аргументы - начала и конец вектора для сортировки:
C++
1
2
3
4
5
vector <int> a;
 
...
 
sort(a.begin(), a.end());
asics
Freelance
Эксперт C++
 Аватар для asics
2838 / 1775 / 144
Регистрация: 09.09.2010
Сообщений: 3,842
22.05.2011, 01:01     Застопорился с qsort #3
Цитата Сообщение от Feytan Посмотреть сообщение
C++
1
void qsort(int* a, long int left, long int right);
qsort() - это стандартная фнукия из cstdlib, зачем вы ее заново определяете ?

Добавлено через 59 секунд
Пример использования см. тут.
easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9371 / 5421 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
22.05.2011, 01:06     Застопорился с qsort #4
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#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
1 / 1 / 0
Регистрация: 09.12.2010
Сообщений: 93
22.05.2011, 01:41  [ТС]     Застопорился с qsort #5
asics,

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

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#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
1 / 1 / 0
Регистрация: 09.12.2010
Сообщений: 93
23.05.2011, 10:48  [ТС]     Застопорился с qsort #6
Я пот переделал слегка, но неидет. Может я что-то нетак сделалал или забыл, подскажите

Вот код:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#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
Эксперт С++
 Аватар для Nameless One
5753 / 3402 / 255
Регистрация: 08.02.2010
Сообщений: 7,390
23.05.2011, 11:09     Застопорился с qsort #7
Feytan, а чем решение выше не нравится?
lemegeton
 Аватар для lemegeton
2909 / 1338 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
23.05.2011, 11:09     Застопорился с qsort #8
C++
1
2
3
4
5
6
7
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
1 / 1 / 0
Регистрация: 09.12.2010
Сообщений: 93
23.05.2011, 13:40  [ТС]     Застопорился с qsort #9
lemegeton,
Спасибо, дейтвительно скобку забыл поставить.

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

Вот код:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#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
1 / 1 / 0
Регистрация: 09.12.2010
Сообщений: 93
24.05.2011, 13:42  [ТС]     Застопорился с qsort #10
Я немного код изменил и добавил в нем условие увеличение на 1 число.
Вот код:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#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
Эксперт С++
 Аватар для Nameless One
5753 / 3402 / 255
Регистрация: 08.02.2010
Сообщений: 7,390
24.05.2011, 13:46     Застопорился с qsort #11
Feytan, в функции compare_ints изменять глобальный счетчик
lemegeton
 Аватар для lemegeton
2909 / 1338 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
24.05.2011, 15:45     Застопорился с qsort #12
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
...
 
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
2 / 2 / 0
Регистрация: 06.05.2010
Сообщений: 18
24.05.2011, 15:46     Застопорился с qsort #13
Цитата Сообщение от Feytan Посмотреть сообщение
Подскажите, а как в данном случае сделать чтобы узнать сколько сравнений элементов сделано программой?
можно использовать свою сортировку, а не из STL
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
24.05.2011, 16:02     Застопорился с qsort #14
lasbat, qsort такой STL...
lemegeton
 Аватар для lemegeton
2909 / 1338 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
24.05.2011, 16:03     Застопорился с qsort #15
Опечатался. Должно быть
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
...
 
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);
...
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
24.05.2011, 16:13     Застопорился с qsort
Еще ссылки по теме:

qsort vs sort C++
qsort C++
C++ qsort

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
lasbat
2 / 2 / 0
Регистрация: 06.05.2010
Сообщений: 18
24.05.2011, 16:13     Застопорился с qsort #16
Цитата Сообщение от ForEveR Посмотреть сообщение
lasbat, qsort такой STL...
я имел в виду встроенную=)
Yandex
Объявления
24.05.2011, 16:13     Застопорился с qsort
Ответ Создать тему
Опции темы

Текущее время: 23:47. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru