Быстрая сортировка

@Дед Мороз · Регистрация: 26.12.2010

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

Есть три файла:
Функция:

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

Не могу понять в чем ошибка. нужно чтобы сортировал. Подозреваю что со входом данных при рекурсии.

@Montanaa · 13.11.2011, 20:17

Подсвети код. Так тебе никто помогать не будет

@Дед Мороз · 13.11.2011, 20:48 **[ТС]**

Есть три файла:
Функция:

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

Не могу понять в чем ошибка. нужно чтобы сортировал. Подозреваю что со входом данных при рекурсии.

Комментарий модератора

Код выделяем тегами!!!

Новые блоги и статьи Все статьи Все блоги /
модель ЗдравоСохранения 8. Подготовка к разному выполнению заданий anaschu 08.04.2026 https:/ / github. com/ shumilovas/ med2. git main ветка * содержимое блока дэлэй из старой модели теперь внутри зайца новой модели 8ATzM_2aurI	Блокировка документа от изменений, если он открыт у другого пользователя Maks 08.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа, разработанного в конфигурации КА2. Задача: запретить редактирование документа, если он открыт у другого пользователя. / / . . .	Система безопасности+живучести для сервера-слоя интернета (сети). Двойная привязка. Hrethgir 08.04.2026 Далее были размышления о системе безопасности. Сообщения с наклонным текстом - мои. А как нам будет можно проверить, что ссылка наша, а не подделана хулиганами, которая выбросит на другую ветку и. . .	Модель ЗдрввоСохранения 7: больше работников, больше ресурсов. anaschu 08.04.2026 работников и заданий может быть сколько угодно, но настроено всё так, что используется пока что только 20% kYBz3eJf3jQ
Дальние перспективы сервера - слоя сети с космологическим дизайном интефейса карты и логики. Hrethgir 07.04.2026 Дальнейшее ближайшее планирование вывело к размышлениям над дальними перспективами. И вот тут может быть даже будут нужны оценки специалистов, так как в дальних перспективах всё может очень сильно. . .	Горе от ума kumehtar 07.04.2026 Эта мне ментальная установка, что вот прямо сейчас, мол, мне для полного счастья не хватает (нужное вписать), и когда я этого достигну - тогда и полный кайф. Одна из самых сильных ловушек на пути. . . .	Использование значений реквизитов справочника в документе, с определенными условиями и правами Maks 07.04.2026 1. Контроль срока действия договора Алгоритм из решения ниже реализован на примере нетипового документа "ЗаявкаНаРаботу", разработанного в конфигурации КА2. Задача: уведомлять пользователя, если. . .	Доступность команды формы по условию Maks 07.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: сделать доступной кнопку (команда формы "ЗавершитьСписание") при. . .

@Montanaa 5 / 5 / 2 Регистрация: 21.03.2011 Сообщений: 79
	13.11.2011, 20:17
	Подсвети код. Так тебе никто помогать не будет 0