Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
TyLinka
33 / 33 / 21
Регистрация: 02.02.2012
Сообщений: 179
#1

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

09.07.2013, 18:49. Просмотров 853. Ответов 10

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

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
#include <string>
#include <iostream>
#include <fstream>
 
using namespace std;
 
struct pupils
{
       string name1;
       string name2;
       long inf;
       long fiz;
       long mat;
       long sr;
};
void quickSortR(pupils* a, long N) {
 
  long i = 0, j = N;
  pupils temp, p;
 
  p .sr = a[ N>>1 ].sr;
 
  do {
      while ( a[i].sr < p.sr ) i++;
      while ( a[j].sr > p.sr ) j--;
 
    if (i <= j) {
      temp = a[i]; a[i] = a[j]; a[j] = temp;
      i++; j--;
    }
  } while ( i<=j );
 
  if ( j > 0 ) quickSortR(a, j);
  if ( N > i ) quickSortR(a+i, N-i);
}
int main()
{
    ifstream in;
    ofstream out;
    in.open("input.txt");
    out.open("output.txt");
 
    long n;
    in >> n;
    pupils *a = new pupils [n];
    
    for (long i = 0; i < n; i++)
    {
        in >> a[i].name1 >> a[i].name2 >> a[i].mat >> a[i].fiz >> a[i].inf;
        a[i].sr = a[i].mat + a[i].fiz + a[i].inf;
    }
 
    quickSortR(a, n);
 
    for (long i = 0; i < n; i++)
        out << a[i].name1 << " " << a[i].name2 << endl;            
 
    delete [] a;
 
    in.close();
    out.close();
 
    return 0;
}
Заранее спасибо!
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
09.07.2013, 18:49
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Быстрая сортировка (C++):

Быстрая сортировка (сортировка Хоара) для связных списков
есть у кого готовый алгоритм? или подскажите как реализовать

Быстрая сортировка(сортировка Хоара). Отсортировать фрагмент массива
Мне нужно отсортировать фрагмент массива, расположенный между первым и...

Быстрая сортировка (сортировка методом Хоара)
Ввести массив x1,x2,...,x20 в диапазоне . Требуется расположить отрицательные...

C/C++ FAQ :: Быстрая сортировка (сортировка Хоара)
Вопрос, скорее академический, по мотивам реализации. Вот в faq приведена...

Сортировка расчёской и быстрая сортировка
В файле in.txt записана последовательность целых чисел. Заданными методами...

Сортировка Хоара / Быстрая сортировка
Доброго времени суток. Написал реализацию алгоритма быстрой сортировки. void...

10
1richard
15 / 5 / 5
Регистрация: 22.06.2013
Сообщений: 31
09.07.2013, 19:32 #2
Не знаю даже, может ты что-то не так вводишь, потому что у меня код работает(Borland C++ 5.02).
Быстрая сортировка
0
TyLinka
33 / 33 / 21
Регистрация: 02.02.2012
Сообщений: 179
09.07.2013, 19:52  [ТС] #3
Цитата Сообщение от 1richard Посмотреть сообщение
Не знаю даже, может ты что-то не так вводишь, потому что у меня код работает(Borland C++ 5.02).
Вложение 290478
я ввожу вот что
4
Ivanov Vasiliy 5 3 4
Petrov Sergey 4 3 5
Konstantinov Nikolay 5 5 5
Kuznetsov Ivan 5 4 4

вот, что должно вывести
Konstantinov Nikolay
Kuznetsov Ivan
Ivanov Vasiliy
Petrov Sergey

Судя по вашим скринам, код всё равно не правильно работает, потому что прога должна сортировать массив.
Вот задача, которая была:

Выведите фамилии и имена учащихся в порядке убывания их среднего балла.

Формат входных данных
Заданы сначала количество учащихся n, затем n строк, каждая из которых содержит фамилию, имя и три числа (оценки по трем предметам: математике, физике, информатике). Данные в строке разделены одним пробелом. Оценки принимают значение от 1 до 5.
Формат выходных данных
Необходимо вывести пары фамилия-имя по одной на строке, разделяя фамилию и имя одним пробелом. Выводить оценки не нужно. Если несколько учащихся имеют одинаковые средние баллы, то их нужно выводить в порядке, заданном во входных данных.
0
1richard
15 / 5 / 5
Регистрация: 22.06.2013
Сообщений: 31
09.07.2013, 21:34 #4
Вывести в обратном порядке, и будет получен искомый результат:
C++
1
2
3
4
5
6
7
8
//.................
 quickSortR(a, n);
 
    for (long i = n-1; i >= 0; i--)
        out << a[i].name1 << " " << a[i].name2 << endl;            
 
    delete [] a;
//....................
1
TyLinka
33 / 33 / 21
Регистрация: 02.02.2012
Сообщений: 179
10.07.2013, 08:26  [ТС] #5
У меня студия, которая при запуске выдаёт ошибку, а отладка показывает на 28 строку.
0
Миниатюры
Быстрая сортировка  
Croessmah
++Ͻ
14158 / 8083 / 1513
Регистрация: 27.09.2012
Сообщений: 19,921
Записей в блоге: 3
Завершенные тесты: 1
10.07.2013, 08:39 #6
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
   //...
void quickSortR(pupils* a, long N) {
   long i = 0, j = N;
   //...
   while ( a[j].sr > p.sr ) j--;//a[j] это же получается a[N] - выход за пределы диапазона
}
 
 
int main(){
   //...
   pupils *a = new pupils [n];
   //...
   quickSortR(a, n);
}
1
Thinker
Эксперт С++
4232 / 2206 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
10.07.2013, 08:43 #7
вызывайте так, чтобы выход за границы массива не получить
C++
1
quickSortR(a, n-1);
это первое, что в глаза бросается

Добавлено через 1 минуту

Не по теме:

я не первый, кто это заметил

1
TyLinka
33 / 33 / 21
Регистрация: 02.02.2012
Сообщений: 179
10.07.2013, 20:18  [ТС] #8
Спасибо, большое!
А я понять не могла, где у меня за границу вылазит

Добавлено через 11 часов 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
#include <string>
#include <iostream>
#include <fstream>
 
using namespace std;
 
struct pupils
{
       string name1;
       string name2;
       long inf;
       long fiz;
       long mat;
       long sr;
};
void quickSortR(pupils* a, long N) {
 
  long i = 0, j = N;
  pupils temp, p;
 
  p .sr = a[ (N + 1) >> 1 ].sr;
 
  do {
      while ( a[i].sr < p.sr ) i++;
      while ( a[j].sr > p.sr ) j--;
 
    if (i <= j) {
      temp = a[i]; 
      a[i] = a[j]; 
      a[j] = temp;
      i++; 
      j--;
    }
  } while ( i<=j );
 
  if ( j > 0 ) quickSortR(a, j);
  if ( N > i ) quickSortR(a + i, N-i);
}
int main()
{
    ifstream in;
    ofstream out;
    in.open("input.txt");
    out.open("output.txt");
 
    long n;
    in >> n;
    pupils *a = new pupils [n];
    
    for (long i = 0; i < n; i++)
    {
        in >> a[i].name1 >> a[i].name2 >> a[i].mat >> a[i].fiz >> a[i].inf;
        a[i].sr = a[i].mat + a[i].fiz + a[i].inf;
    }
 
    quickSortR(a, n - 1);
 
    for (long i = n - 1; i >= 0; i--)
        out << a[i].name1 << " " << a[i].name2 << endl;            
 
    delete [] a;
 
    in.close();
    out.close();
 
    return 0;
}
Исходные данные:
8
Ivanov Vasiliy 5 3 4
Petrov Sergey 4 3 5
Konstantinov Nikolay 5 5 5
Kuznetsov Ivan 5 4 4
Ivanov Vasiliy 5 3 4
Petrov Sergey 4 3 5
Konstantinov Nikolay 5 5 5
Kuznetsov Ivan 5 4 4

Выводится:
Konstantinov Nikolay
Konstantinov Nikolay
Kuznetsov Ivan
Kuznetsov Ivan
Ivanov Vasiliy
Petrov Sergey
Petrov Sergey
Ivanov Vasiliy

Должно быть:
Konstantinov Nikolay
Konstantinov Nikolay
Kuznetsov Ivan
Kuznetsov Ivan
Ivanov Vasiliy
Ivanov Vasiliy
Petrov Sergey
Petrov Sergey
0
Thinker
Эксперт С++
4232 / 2206 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
10.07.2013, 21:28 #9
так попробуйте
C++
1
p .sr = a[ N >> 1 ].sr;
1
1richard
15 / 5 / 5
Регистрация: 22.06.2013
Сообщений: 31
10.07.2013, 23:19 #10
Смею заметить, что "Petrov Sergey 4 3 5" и "Ivanov Vasiliy 5 3 4" - эквивалентны, тоесть их параметр sr в поле структуры одинаковый, а значит результат, как этот:
" Выводится:
Konstantinov Nikolay
Konstantinov Nikolay
Kuznetsov Ivan
Kuznetsov Ivan
Ivanov Vasiliy
Petrov Sergey
Petrov Sergey
Ivanov Vasiliy"
есть правильный, так же, я бы посоветовал, писать в коде
C++
1
p .sr = a[ N / 2].sr;
что я вляется более наглядным способом определения середины сортируемого массива.
Так же, если внимательно читать условие задачи, а именно "Если несколько учащихся имеют одинаковые средние баллы, то их нужно выводить в порядке, заданном во входных данных." То для ваших входных данных, правильным выводом будет:
"Konstantinov Nikolay
Konstantinov Nikolay
Kuznetsov Ivan
Kuznetsov Ivan
Ivanov Vasiliy
Petrov Sergey
Ivanov Vasiliy
Petrov Sergey"

Добавлено через 16 минут
Добиться правильного результата, можно добавив в структуру еще одно поле, которое бы хранило начальный порядок элементов:
C++
1
2
3
4
5
6
7
8
9
10
struct pupils
{
       string name1;
       string name2;
       long inf;
       long fiz;
       long mat;
       long sr;
       long key;
};
И заполнялось бы при вводе следующим образом:
C++
1
2
3
4
5
6
for (long i = 0; i < n; i++)
    {
        in >> a[i].name1 >> a[i].name2 >> a[i].mat >> a[i].fiz >> a[i].inf;
        a[i].sr = a[i].mat + a[i].fiz + a[i].inf;
        a[i].key = i;
    }
В связи с чем, перестановка элементов сортировкой может выглядеть так:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
if (i <= j) 
{
 if(a[i].sr != a[j].sr)
 {
  temp = a[i]; 
  a[i] = a[j]; 
  a[j] = temp;
 }
 else
  if(a[i].key < a[j].key )
 {
  temp = a[i]; 
  a[i] = a[j]; 
  a[j] = temp;
 }
i++; 
j--;
}
1
TyLinka
33 / 33 / 21
Регистрация: 02.02.2012
Сообщений: 179
11.07.2013, 08:44  [ТС] #11
Самое смешное, что с этой сортировкой проходит 11 тестов из 99. Весь этот сыр бор был начат, потому что с сортировкой пузырьком не проходил 99 тест из-за превышения времени работы программы. Теперь он проходит, в отличие от 88 остальных
0
11.07.2013, 08:44
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.07.2013, 08:44
Привет! Вот еще темы с решениями:

Быстрая сортировка
void quickSortR(int *first,int *last) { // На входе - массив a, a - его...

Быстрая сортировка
Здравствуйте уважаемые форумчане киберфорума. Имеется проблеммка с задачкой,...

Быстрая сортировка
Есть три файла: Функция: #ifndef QUICK #define QUICK #include &lt;vector&gt; ...

Быстрая сортировка
Здравствуйте. Ребята, очень нужна помощь. Есть функция быстрой сортировки, ей...


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

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

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