Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

Войти
Регистрация
Восстановить пароль
 
TyLinka
32 / 32 / 11
Регистрация: 02.02.2012
Сообщений: 177
#1

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

09.07.2013, 18:49. Просмотров 795. Ответов 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++):

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

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

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

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

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

Сортировка Хоара / Быстрая сортировка - C++
Доброго времени суток. Написал реализацию алгоритма быстрой сортировки. void SortHhoar(int *arr,int f,int l)//Хоара { int mid = (f...

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

Добавлено через 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
0
Thinker
Эксперт С++
4228 / 2202 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
10.07.2013, 21:28 #9
так попробуйте
C++
1
p .sr = a[ N >> 1 ].sr;
1
1richard
15 / 5 / 2
Регистрация: 22.06.2013
Сообщений: 28
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
32 / 32 / 11
Регистрация: 02.02.2012
Сообщений: 177
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
Привет! Вот еще темы с ответами:

Быстрая сортировка - C++
Не работают обе версии сортировки.Не понимаю почему.И еще почему-то портится значение второго элемента. Быстрая сортировка 1.0 ...

Быстрая сортировка - C++
void quickSortR(int *first,int *last) { // На входе - массив a, a - его последний элемент. int *i = first, *j = last; ...

Быстрая сортировка - C++
Воспользовался готовым решением для сортировки: Алгоритмы сортировок в итоге если беру массив: int A = {2,1,4,5,8,7,1,5,2,9} ...

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


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

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

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