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

Быстрая сортировка - C++

Восстановить пароль Регистрация
 
Дед Мороз
0 / 0 / 0
Регистрация: 26.12.2010
Сообщений: 4
13.11.2011, 19:28     Быстрая сортировка #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
#ifndef QUICK
#define QUICK
#include <vector>
 
using namespace std;
 
template<class T> 
void qs(vector<T> &vect, int L, int R) // функция сортировки
{
   L=0;
   R=vect.size();
   int i = L;
   int j = R;       // поставить указатели на исходные места 
   T temp_QuickS;
   int central;
   central = vect.at( vect.size() - 1 );        // центральный элемент
                          // процедура разделениz
      do {
         while ( vect.at(i) < central ) i++;
         while ( vect.at(j) > central ) j--;
            if (i <= j) {
               temp_QuickS = vect.at(i);
               vect.at(i) = vect.at(j); 
               vect.at(j) = temp_QuickS;
               i++; j--;
            }
       } 
       while ( i<=j );
       
      /*  temp_QuickS = vect.at(i); 
    vect.at(i) = vect.at(R); 
    vect.at(R) =  temp_QuickS;*/
  
                  // рекурсивные вызовы, если есть, что сортировать 
      if ( j > L )   qs(vect, L, i-1);
      if ( R > i )   qs(vect, i+1, R );
}
#endif
Структура:
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
#ifndef QUICKSORT
#define QUICKSORT
 
template<class T, class T1> // Структура элемента
struct QuickSort
{
  T x; // Ключ
  T1 y; // Данные
  bool operator<(QuickSort<T, T1>); // Функция сравнения
  bool operator>(QuickSort<T, T1>); // Функция сравнения
};
 
 template<class T, class T1>
bool QuickSort<T, T1>::operator<(QuickSort<T, T1> QuickS) // Функция сравнения
  {
     if(x==QuickS.x)
      if(y<QuickS.y)
        return true;
      else
        return false;
    if(x<QuickS.x)
      return true;
    else
      return false;
  }
template<class T, class T1>
bool QuickSort<T, T1>::operator>(QuickSort<T, T1> QuickS) // Функция сравнения
  {
     if(x==QuickS.x)
      if(y>QuickS.y)
        return true;
      else
        return false;
    if(x>QuickS.x)
      return true;
    else
   
     return false;
     } 
 
#endif
И собственно файл в котором происходит все действие:
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
#include <iostream>
#include <fstream>
#include <vector>
#include <iomanip>
#include "QuickSort.h"
#include "quick.cpp"
 
using std::cout;
using std::ifstream;
using std::setw;
using std::endl;
 
void Input(vector<QuickSort<int, int> > *vect) // Функция ввода
{
  ifstream input_file("file2.txt"); // Файл с данными
  QuickSort<int, int> QuickS; // Вспомогательная структура
  while(!input_file.eof()) // Перемещаем элементы из файла в вектор
  {
    input_file>>QuickS.x;
    input_file>>QuickS.y;
    vect->push_back(QuickS);
  }
  input_file.close();
}
 
void Output(vector<QuickSort<int, int> > &vect) // Функция вывода
{
  cout<<"Key"<<setw(8)<<"Data"<<endl;
  for(int i=0; i<vect.size(); i++) // Выводим результат на экран
    cout<<setw(3)<<vect.at(i).x<<setw(6)<<vect.at(i).y<<endl;
}
 
int main(int argc, char *argv[])
{
 
    vector<QuickSort<int, int> > vect ; // Вектор заданных элементов
    Input(&vect); // Считываем данные
    qs(vect, 0, vect.size()); // Сортируем
    Output(vect); // Вывод на экран
    system("PAUSE");
    return EXIT_SUCCESS;
}
Не могу понять в чем ошибка. нужно чтобы сортировал. Подозреваю что со входом данных при рекурсии.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.11.2011, 19:28     Быстрая сортировка
Посмотрите здесь:

C++ Быстрая сортировка
C/C++ FAQ :: Быстрая сортировка (сортировка Хоара) C++
Быстрая сортировка C++
быстрая сортировка C++
C++ Быстрая сортировка
Быстрая сортировка (сортировка Хоара) для связных списков C++
Быстрая сортировка (сортировка методом Хоара) C++
C++ Сортировка Хоара / Быстрая сортировка

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Montanaa
5 / 5 / 1
Регистрация: 21.03.2011
Сообщений: 79
13.11.2011, 20:17     Быстрая сортировка #2
Подсвети код. Так тебе никто помогать не будет
Дед Мороз
0 / 0 / 0
Регистрация: 26.12.2010
Сообщений: 4
13.11.2011, 20:48  [ТС]     Быстрая сортировка #3
Есть три файла:
Функция:
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
#ifndef QUICK
#define QUICK
#include <vector>
 
using namespace std;
 
template<class T>
void qs(vector<T> &vect, int L, int R)
{
L=0;
R=vect.size();
int i = L;
int j = R; // поставить указатели на исходные места
T temp_QuickS;
int central;
central = vect.at( vect.size() - 1 ); // центральный элемент
// процедура разделениz
do {
while ( vect.at(i) < central ) i++;
while ( vect.at(j) > central ) j--;
if (i <= j) {
temp_QuickS = vect.at(i);
vect.at(i) = vect.at(j);
vect.at(j) = temp_QuickS;
i++; j--;
}
}
while ( i<=j );
 
/* temp_QuickS = vect.at(i);
vect.at(i) = vect.at(R);
vect.at(R) = temp_QuickS;*/
 
// рекурсивные вызовы, если есть, что сортировать
if ( j > L ) qs(vect, L, i-1);
if ( R > i ) qs(vect, i+1, R );
}
#endif
Структура:
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
#ifndef QUICKSORT
#define QUICKSORT
 
template<class T, class T1> // Структура элемента
struct QuickSort
{
T x; // Ключ
T1 y; // Данные
bool operator<(QuickSort<T, T1>); // Функция сравнения
bool operator>(QuickSort<T, T1>); // Функция сравнения
};
 
template<class T, class T1>
bool QuickSort<T, T1>::operator<(QuickSort<T, T1> QuickS) // Функция сравнения
{
if(x==QuickS.x)
if(y<QuickS.y)
return true;
else
return false;
if(x<QuickS.x)
return true;
else
return false;
}
template<class T, class T1>
bool QuickSort<T, T1>::operator>(QuickSort<T, T1> QuickS) // Функция сравнения
{
if(x==QuickS.x)
if(y>QuickS.y)
return true;
else
return false;
if(x>QuickS.x)
return true;
else
 
return false;
}
 
#endif
И собственно файл в котором происходит все действие:
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
#include <iostream>
#include <fstream>
#include <vector>
#include <iomanip>
#include "QuickSort.h"
#include "quick.cpp"
 
using std::cout;
using std::ifstream;
using std::setw;
using std::endl;
 
void Input(vector<QuickSort<int, int> > *vect) // Функция ввода
{
ifstream input_file("file2.txt"); // Файл с данными
QuickSort<int, int> QuickS; // Вспомогательная структура
while(!input_file.eof()) // Перемещаем элементы из файла в вектор
{
input_file>>QuickS.x;
input_file>>QuickS.y;
vect->push_back(QuickS);
}
input_file.close();
}
 
void Output(vector<QuickSort<int, int> > &vect) // Функция вывода
{
cout<<"Key"<<setw(8)<<"Data"<<endl;
for(int i=0; i<vect.size(); i++) // Выводим результат на экран
cout<<setw(3)<<vect.at(i).x<<setw(6)<<vect.at(i).y<<endl;
}
 
int main(int argc, char *argv[])
{
 
vector<QuickSort<int, int> > vect ; // Вектор заданных элементов
Input(&vect); // Считываем данные
[COLOR="DarkRed"]qs(vect, 0, vect.size())[/COLOR]; // Сортируем
Output(vect); // Вывод на экран
system("PAUSE");
return EXIT_SUCCESS;
}
Не могу понять в чем ошибка. нужно чтобы сортировал. Подозреваю что со входом данных при рекурсии.
 Комментарий модератора 
Код выделяем тегами!!!
Yandex
Объявления
13.11.2011, 20:48     Быстрая сортировка
Ответ Создать тему
Опции темы

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