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

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

Войти
Регистрация
Восстановить пароль
 
Тиша
1 / 1 / 0
Регистрация: 02.11.2009
Сообщений: 75
#1

QSort, не могу устранить ошибку в программе - C++

28.01.2011, 01:24. Просмотров 550. Ответов 8
Метки нет (Все метки)

Делаю одно обширную программу, в которой использую контейнеры. Одна из функций - быстрая сортировка элементов вектора не работает, закинула ее в отдельную программу все пытаюсь с помощью отладки устранить ошибку но не понимаю как. Код ниже

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
#include "stdafx.h"
#include <iostream>
   #include <cstdio>
     #include <time.h>
#include <vector>
using std::vector;
using namespace std;
 
 
void QuickSort(int b[], int N){
        
 
  int i = 0;
  int j = N;           
  int temp, p;
  
 
  p = b[N>>1 ];               
 
 
  do {
    while ( b[i] < p ) i++;
    while ( b[j] > p ) j--;
 
    if (i <= j) {
      temp = b[i]; b[i] = b[j]; b[j] = temp;
      i++; j--;
    }
  } while ( i<=j );
 
 
  if ( j > 0 ) QuickSort(b,j);
  if ( N > i ) QuickSort(b+i,N-i);
 
 
 
}
 
 
void main()
{ vector <int> a;
int tStep = 5;
int t=0;
while(t <= 5) {  
    int size=t;
    srand(time(NULL));
        for(int i=0;i<size;i++)
a.push_back(rand()%100 + 1);
 
        clock_t start;
       start=clock();
       int i;
 int *b=new int[size];
 
      
 for(i=0;i<size;i++) b[i]=a[i];
  
    QuickSort(b,size);
  for(i=0;i<size;i++)
        a[i]=b[i];
  
  delete []b;
  double diff=(clock()-start)/(double)CLOCKS_PER_SEC;
cout<<diff<<" "<<t<<endl;
     
       
 
       t += tStep;
       cout<<endl;
}
    /*for(int i=0;i<a.size();i++)
       cout<<a[i]<<" ";*/
 
}


если запускать просто вектор, то в
C++
1
if ( N > i ) QuickSort(b+i,N-i);
дает ошибку на b+i
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
28.01.2011, 01:24     QSort, не могу устранить ошибку в программе
Посмотрите здесь:

Не могу исправить ошибку в программе на С++ - C++
Написал программу: #include &lt;iostream&gt; #include &lt;conio.h&gt; using namespace std; double sin (unsigned short n); int main() ...

Не могу найти ошибку в программе - C++
Здравствуйте! Не могу понять, как полностью отладить программу. Определенное понимание о характере ошибке есть( ниже прложил ее название),...

Не могу найти ошибку в программе - C++
Добрый вечер, уважаемые программисты. Прошу у вас помощи с программой. Нужно её сдавать, а она не работает. Буду очень благодарен за любую...

Не могу найти ошибку в программе - C++
#include &lt;iostream&gt; #include &lt;fstream&gt; #include &lt;cctype&gt; #define is_delim(c) (std::isspace((c)) || std::ispunct((c))) using...

Не могу найти ошибку в программе - C++
Разложение числа на сумму двух квадратов &quot;for(a=o;a&lt;=floor(sqrt(W));x++); for(b=0;b&lt;=floor(sqrt(w));y++); if(a*a+b*b==W) ...

Не могу найти ошибку в программе - C++
# include &lt;iostream&gt; #include &lt;string&gt; #include &lt;math.h&gt; void main() { string str; char hex={'0', '1', '2', '3', '4',...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Nameless One
Эксперт С++
5769 / 3418 / 255
Регистрация: 08.02.2010
Сообщений: 7,444
28.01.2011, 06:44     QSort, не могу устранить ошибку в программе #2
Главная ошибка - это то, что функция быстрой сортировки спроектирована у тебя так, что она может у тебя работать только с массивом int, но не с вектором элементов int.

А если написать функцию сортировки так, то она будет работать с любым массивом С и любым контейнером (с двунаправленными итераторами):
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
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <string>
#include <ctime>
 
template<class Iterator>
void quickSort(Iterator first, Iterator last)
{
    Iterator x = first;
        
    Iterator i = first;
    Iterator j = last - 1;
    do
    {
    while(*i < *x) ++i;
    while(*x < *j) --j;
    if(i <= j)
        std::swap(*i++, *j--);
    }
    while(i <= j);
    if(first < j) quickSort(first, j + 1);
    if(i < last) quickSort(i, last);
}
 
template<class Iterator>
bool testIfSorted(Iterator first, Iterator last)
{
    Iterator it = first + 1;
    while(it != last)
    if(*first++ > *it++)
        return false;
    return true;
}
 
template<class Iterator>
void test(Iterator first, Iterator last, const std::string& msg)
{
    std::cout << "Testing " << msg << std::endl;
    std::cout << "Before sorting:" << std::endl;
    std::copy(first, last, std::ostream_iterator<int>(std::cout, " "));
    std::cout << std::endl;
    quickSort(first, last);
    std::cout << "After sorting:" << std::endl;
    std::copy(first, last, std::ostream_iterator<int>(std::cout, " "));
    std::cout << std::endl;
    std::cout << "Result: "
          << (testIfSorted(first, last) ? "success" : "failure")
          << std::endl << std::endl;
}
 
int main()
{
    srand(static_cast<size_t>(time(NULL)));
    const size_t size = 15;
    std::vector<int> ivec(size);
    for(std::vector<int>::iterator it = ivec.begin(); it != ivec.end(); ++it)
    *it = rand() % 100 + 1;
    /* Тестируем работу с контейнерным классом */
    test(ivec.begin(), ivec.end(), "std::vector<int> container");
 
    int iarray[size];
    for(int* ip = iarray; ip != iarray + size; ++ip)
    *ip = rand() % 100 + 1;
    /* Тестируем работу с обычным массивом */
    test(iarray, iarray + size, "plain array of int");
    
    return 0;
}

Не по теме:

И да, если пишешь "using namespace std;", то писать "using std::vector" уже не надо.

Тиша
1 / 1 / 0
Регистрация: 02.11.2009
Сообщений: 75
28.01.2011, 18:39  [ТС]     QSort, не могу устранить ошибку в программе #3
Nameless One, спасибо, сейчас попробую ^^ я не супер как разбираюсь во всем этом, в основном все по книжкам и по книжкам)

Добавлено через 1 час 7 минут
Nameless One, только как Interator запихнуть в класс? у меня есть класс Sort, в нем содержиться vector <int> a и все функции. Функция QuickSort одна из функций этого класса. Когда в аргументы пишу QuickSort(Interator first, Interator last) выдает ошибку, убираю функцию из класса - не работает. Добавляю template <class Interator> над описанием класса Sort, выдает ошибки на вс другие функции.
Nameless One
Эксперт С++
5769 / 3418 / 255
Регистрация: 08.02.2010
Сообщений: 7,444
28.01.2011, 18:42     QSort, не могу устранить ошибку в программе #4
Тиша, покажи сам класс.
Тиша
1 / 1 / 0
Регистрация: 02.11.2009
Сообщений: 75
28.01.2011, 18:43  [ТС]     QSort, не могу устранить ошибку в программе #5
Nameless One,
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
class Sort {
 
     vector <int> a;
        public:
    int size;
        
    //void read(ifstream &in);//
    void SelectSort(); //выбор
    void BubbleSort(); //пузырь
    void InsertSort(); //вставка
    //void QuickSort(Interator first, Interator last); //быстрая
    void HeapSort(); //пиромида
    void ShellSort(); //Шелл
    void RadixSort(); //поразрядная
    void MergeSort(long lb, long ub); //слияние
    void Merge(long lb, long split, long ub);
    void SiftDown(int a[], long k, long n);
    void write();
    void Rand(int size);
    void DrawDiagram(HWND hwnd, HDC hdc);
    //void Quick();//
    //void Sum();//
    
     
        };
Nameless One
Эксперт С++
5769 / 3418 / 255
Регистрация: 08.02.2010
Сообщений: 7,444
28.01.2011, 18:47     QSort, не могу устранить ошибку в программе #6
Тиша, можно сделать либо чтобы сам класс был шаблонным, либо чтобы функция сортировки могла работать только с итераторами std::vector<int>. Второй вариант - проще.
Тиша
1 / 1 / 0
Регистрация: 02.11.2009
Сообщений: 75
28.01.2011, 18:50  [ТС]     QSort, не могу устранить ошибку в программе #7
Nameless One, так, а как сделать второе?
Nameless One
Эксперт С++
5769 / 3418 / 255
Регистрация: 08.02.2010
Сообщений: 7,444
28.01.2011, 18:53     QSort, не могу устранить ошибку в программе #8
Тиша, убери везде template<class ...>, a Iterator замени на std::vector<int>::iterator
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.01.2011, 18:58     QSort, не могу устранить ошибку в программе
Еще ссылки по теме:

не могу найти ошибку в программе - C++
задача Дана символьная строка. Подсчитать количество букв k в последнем ее слове считает только буквы К в первом слове и выдаёт...

Не могу найти ошибку в программе - C++
Прога рабочая, но если вводишь х = 0 и у= 0 то она зацикливается на &quot;Ошибка! Начните заново.&quot; и не работает правильно. Хотя должна....

Не могу найти ошибку в программе - C++
Даны действительные числа х1, у1, х2, у2, …,х10, у10. Найти периметр десятиугольника, вершины которого имеют соответственно координаты (х1,...

Не могу найти ошибку в программе - C++
Не могу найти ошибку в программе #include &quot;stdafx.h&quot; #include &lt;iostream.h&gt; #include &lt;math.h&gt; #include &lt;fstream.h&gt; #include...


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

Или воспользуйтесь поиском по форуму:
Тиша
1 / 1 / 0
Регистрация: 02.11.2009
Сообщений: 75
28.01.2011, 18:58  [ТС]     QSort, не могу устранить ошибку в программе #9
Nameless One, Дааа! Здорово, все работает! Спасибо)))
Yandex
Объявления
28.01.2011, 18:58     QSort, не могу устранить ошибку в программе
Ответ Создать тему
Опции темы

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