Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Feytan
1 / 1 / 0
Регистрация: 09.12.2010
Сообщений: 93
#1

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

22.05.2011, 00:52. Просмотров 781. Ответов 15
Метки нет (Все метки)

Суть задачи в следующем:
Дан одномерный массив длиной 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;
}
Если возможно поясните что не так делаю
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
22.05.2011, 00:52
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Застопорился с qsort (C++):

qsort - C++
Вот код программы. Посмотрите вопрос в комментарии. #include &lt;iostream&gt; #include &lt;stdlib.h&gt; using namespace std; int main() ...

qsort - C++
читал, что с помощю QSORT можно упорядочить масив, но не пишет как. помогите!!

qsort C++ - C++
Помогите, плиз,разобраться с этой функцией, я прогу написала, но мало чего понимаю в ней, я написала в трех файлах, так и выкладываю. ...

qsort - C++
Вот код: #include &lt;cstdio&gt; #include &lt;algorithm&gt; int compare(const void *s1, const void *s2) { return strcmp((char *)s1, (char...

qsort - C++
Ребят,расскажи подробно и простенько про qsort;Видел тему,но ничего не понял.Я новичек еще можно сказать пока в С++. у меня просто...

qsort vs sort - C++
Собственно вопрос что лутше, в каких ситуациях, и почему , спасибо

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

Добавлено через 59 секунд
Пример использования см. тут.
0
easybudda
Модератор
Эксперт CЭксперт С++
9694 / 5644 / 962
Регистрация: 25.07.2009
Сообщений: 10,848
22.05.2011, 01:06 #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;
}
0
Feytan
1 / 1 / 0
Регистрация: 09.12.2010
Сообщений: 93
22.05.2011, 01:41  [ТС] #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;
}
0
Feytan
1 / 1 / 0
Регистрация: 09.12.2010
Сообщений: 93
23.05.2011, 10:48  [ТС] #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;
}
}
0
Nameless One
Эксперт С++
5775 / 3425 / 255
Регистрация: 08.02.2010
Сообщений: 7,448
23.05.2011, 11:09 #7
Feytan, а чем решение выше не нравится?
0
lemegeton
2925 / 1354 / 135
Регистрация: 29.11.2010
Сообщений: 2,725
23.05.2011, 11:09 #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);
}
0
Feytan
1 / 1 / 0
Регистрация: 09.12.2010
Сообщений: 93
23.05.2011, 13:40  [ТС] #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;
}
0
Feytan
1 / 1 / 0
Регистрация: 09.12.2010
Сообщений: 93
24.05.2011, 13:42  [ТС] #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;
}
Подскажите, а как в данном случае сделать чтобы узнать сколько сравнений элементов сделано программой?
0
Nameless One
Эксперт С++
5775 / 3425 / 255
Регистрация: 08.02.2010
Сообщений: 7,448
24.05.2011, 13:46 #11
Feytan, в функции compare_ints изменять глобальный счетчик
0
lemegeton
2925 / 1354 / 135
Регистрация: 29.11.2010
Сообщений: 2,725
24.05.2011, 15:45 #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);
...
}
0
lasbat
2 / 2 / 0
Регистрация: 06.05.2010
Сообщений: 18
24.05.2011, 15:46 #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);
}
например такую
0
ForEveR
В астрале
Эксперт С++
7983 / 4742 / 321
Регистрация: 24.06.2010
Сообщений: 10,543
Завершенные тесты: 3
24.05.2011, 16:02 #14
lasbat, qsort такой STL...
0
lemegeton
2925 / 1354 / 135
Регистрация: 29.11.2010
Сообщений: 2,725
24.05.2011, 16:03 #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);
...
}
1
24.05.2011, 16:03
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
24.05.2011, 16:03
Привет! Вот еще темы с ответами:

не работает qsort - C++
#include &lt;iostream&gt; #include &lt;math.h&gt; #include &lt;iomanip&gt; #include &lt;string.h&gt; using namespace std; struct MARSH { char...

Vector and qsort - C++
Здравствуйте, есть код: #include &quot;iostream&quot; #include &quot;vector&quot; using namespace std; int compare (const void * a, const void *...

Функция Qsort - C++
Прошу ознакомить меня с функцией Qsort. Если можно, то не мудрено и на примерах. Спасибо.

Сортировка qsort - C++
Доброго времени суток, уже применял qsort для сортировки цифр, но не могу найти его для алфавита. Необходимо распределить предложения в...


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

Или воспользуйтесь поиском по форуму:
15
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru