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

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

Восстановить пароль Регистрация
 
TyLinka
32 / 32 / 11
Регистрация: 02.02.2012
Сообщений: 177
09.07.2013, 18:49     Быстрая сортировка #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
#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;
}
Заранее спасибо!
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
09.07.2013, 18:49     Быстрая сортировка
Посмотрите здесь:

Быстрая сортировка C++
Быстрая сортировка C++
Быстрая сортировка C++
C++ Быстрая сортировка
Быстрая сортировка C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
1richard
15 / 5 / 2
Регистрация: 22.06.2013
Сообщений: 25
09.07.2013, 19:32     Быстрая сортировка #2
Не знаю даже, может ты что-то не так вводишь, потому что у меня код работает(Borland C++ 5.02).
Быстрая сортировка
TyLinka
32 / 32 / 11
Регистрация: 02.02.2012
Сообщений: 177
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.
Формат выходных данных
Необходимо вывести пары фамилия-имя по одной на строке, разделяя фамилию и имя одним пробелом. Выводить оценки не нужно. Если несколько учащихся имеют одинаковые средние баллы, то их нужно выводить в порядке, заданном во входных данных.
1richard
15 / 5 / 2
Регистрация: 22.06.2013
Сообщений: 25
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;
//....................
TyLinka
32 / 32 / 11
Регистрация: 02.02.2012
Сообщений: 177
10.07.2013, 08:26  [ТС]     Быстрая сортировка #5
У меня студия, которая при запуске выдаёт ошибку, а отладка показывает на 28 строку.
Миниатюры
Быстрая сортировка  
Croessmah
Модератор
Эксперт С++
 Аватар для Croessmah
11800 / 6779 / 765
Регистрация: 27.09.2012
Сообщений: 16,829
Записей в блоге: 2
Завершенные тесты: 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);
}
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
10.07.2013, 08:43     Быстрая сортировка #7
вызывайте так, чтобы выход за границы массива не получить
C++
1
quickSortR(a, n-1);
это первое, что в глаза бросается

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

Не по теме:

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

TyLinka
32 / 32 / 11
Регистрация: 02.02.2012
Сообщений: 177
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
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
10.07.2013, 21:28     Быстрая сортировка #9
так попробуйте
C++
1
p .sr = a[ N >> 1 ].sr;
1richard
15 / 5 / 2
Регистрация: 22.06.2013
Сообщений: 25
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--;
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.07.2013, 08:44     Быстрая сортировка
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
TyLinka
32 / 32 / 11
Регистрация: 02.02.2012
Сообщений: 177
11.07.2013, 08:44  [ТС]     Быстрая сортировка #11
Самое смешное, что с этой сортировкой проходит 11 тестов из 99. Весь этот сыр бор был начат, потому что с сортировкой пузырьком не проходил 99 тест из-за превышения времени работы программы. Теперь он проходит, в отличие от 88 остальных
Yandex
Объявления
11.07.2013, 08:44     Быстрая сортировка
Ответ Создать тему

Метки
Быстрая сортировка, быстрая сортировка c++, сортировка, сортировка c++
Опции темы

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