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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.78
SeryZone
56 / 28 / 5
Регистрация: 09.03.2012
Сообщений: 726
Записей в блоге: 1
#1

stdlib.h - quicksort - C++

26.07.2012, 13:33. Просмотров 1148. Ответов 10
Метки нет (Все метки)

Идея такова: отсортировать массив A[max - 100 000] очень быстрым методом Хоара. Пробовал в stdlib.h делать QuickSort - ничего не получилось. Все значения элементов - до 263-1. Т.е. влазят в тип long. Помогите отсортировать!
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
26.07.2012, 13:33
Здравствуйте! Я подобрал для вас темы с ответами на вопрос stdlib.h - quicksort (C++):

Ошибка stdlib.h - C++
Имеется файл содержащий что-то подобное: 1. Nomer reisa: 1 ves bagazha: 1.00 (kg) kolichestvo veshei: 11 2. Nomer reisa: 1 ves bagazha:...

прoблемка с stdlib.h - C++
Моя знакомая удалила случайно файл stdlib.h Когда она подключает файл и вызывает оттуда функцию rand(), то выскакивает ошибка,что функция...

Stdlib system - C++
Здравствуйте! Вот какая проблема. функция system("текст") выдает ответ в общий поток ( в Qt в qDebug). А как сделать так что бы была...

Exit() без stdlib и c++11 - C++
Подскажите пожалуйста, почему компилируется этот код со стандартом с++11: #include <iostream> using namespace std; int main() { ...

ПРИШЛИТЕ МНЕ ПОЖАЛУЙСТA ФАЙЛ stdlib.h ДЛЯ VS2006 - C++
ПРИШЛИТЕ МНЕ ПОЖАЛУЙСТA ФАЙЛ stdlib.h ДЛЯ VS2006

Quicksort - C++
Дан массив, необходимо отсортировать его в порядке возрастания. Использую квиксорт, но в одном из тестов не проходит по времени (2с). ...

10
nexen
187 / 180 / 3
Регистрация: 27.01.2012
Сообщений: 1,335
26.07.2012, 13:37 #2
А что насчет функции sort из stl? Она, вроде бы, тоже Хоаром реализована

C++
1
2
3
4
5
6
7
8
9
#include <algorithm>
..
int main()
{
const int MAX = 100*1000;
long long mas[MAX];
....
sort(mas, mas+MAX); // по умолчанию сортировка по неубывающей
}
p.s И что ещё за очень быстрый метод Хоара?
1
rangerx
1937 / 1546 / 141
Регистрация: 31.05.2009
Сообщений: 2,913
26.07.2012, 13:51 #3
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <cstdlib>
#include <iostream>
 
int less_cmp(const void* a, const void* b) {
 
    return *static_cast<const long*>(a) - *static_cast<const long*>(b);
}
 
int main() {
 
    const size_t size = 5;
    long arr[size] = { 5, 2, 4, 1, 3 };
 
    std::qsort(arr, size, sizeof(long), less_cmp);
 
    for(size_t i = 0; i < size; ++i)
        std::cout << arr[i] << " ";
    std::cout << std::endl;
    
    return 0;
}
0
Catstail
Модератор
22909 / 11275 / 1833
Регистрация: 12.02.2012
Сообщений: 18,487
26.07.2012, 13:55 #4
Цитата Сообщение от SeryZone Посмотреть сообщение
ничего не получилось.
- вообще не сортирует?
0
SeryZone
56 / 28 / 5
Регистрация: 09.03.2012
Сообщений: 726
Записей в блоге: 1
26.07.2012, 18:20  [ТС] #5
Цитата Сообщение от Catstail Посмотреть сообщение
- вообще не сортирует?
Вот, получилось, чуть-чуть сортирует, но не полностью. Проверьте с большим количеством элементов.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <stdio.h>
#include <stdlib.h>
long a[100000],i,n;
 
int less_cmp(const void* a, const void* b) {
 
    return *static_cast<const long*>(a) - *static_cast<const long*>(b);
}
 
int main(void)
{
    scanf("%ld",&n);
    for (i=1;i<=n;i++) scanf("%ld",&a[i]);
    qsort(a, n, sizeof(long), less_cmp);
    for (i=1;i<n;i++) printf("%ld ",a[i]);
    printf("%ld\n",a[n]);
}
0
nexen
187 / 180 / 3
Регистрация: 27.01.2012
Сообщений: 1,335
26.07.2012, 18:39 #6
SeryZone, моя сортирует, но я, видимо, не существую.
настойчивое чувство, что меня специально игнорят ; (
0
Jupiter
Каратель
Эксперт С++
6561 / 3982 / 227
Регистрация: 26.03.2010
Сообщений: 9,273
Записей в блоге: 1
Завершенные тесты: 2
26.07.2012, 18:54 #7
Цитата Сообщение от SeryZone Посмотреть сообщение
сортирует, но не полностью
чем докажешь?

Добавлено через 1 минуту
Цитата Сообщение от SeryZone Посмотреть сообщение
Проверьте с большим количеством элементов.
проверей, УМВР
1
easybudda
Модератор
Эксперт CЭксперт С++
9698 / 5648 / 964
Регистрация: 25.07.2009
Сообщений: 10,863
26.07.2012, 19:49 #8
Цитата Сообщение от Jupiter Посмотреть сообщение
чем докажешь?
Цитата Сообщение от SeryZone Посмотреть сообщение
C++
1
2
3
4
//...
    for (i=1;i<=n;i++) scanf("%ld",&a[i]);
    qsort(a, n, sizeof(long), less_cmp);
    //...
Вот как бы ещё функции qsort намекнуть, что индексация в массиве не с 0, как обычно, а с 1 начинается...
1
Orlov
0 / 0 / 0
Регистрация: 10.02.2016
27.07.2012, 10:22 #9
Цитата Сообщение от easybudda Посмотреть сообщение
Вот как бы ещё функции qsort намекнуть, что индексация в массиве не с 0, как обычно, а с 1 начинается...
a это указатель на int, напиши qsort(a+1, n, sizeof(long), less_cmp);
0
Nameless One
Эксперт С++
5777 / 3427 / 255
Регистрация: 08.02.2010
Сообщений: 7,448
27.07.2012, 10:41 #10
orlov, я думаю, что проще и логичнее будет при вводе-выводе массива пользоваться циклом от нуля до n (не включая n):

C
1
2
for(i = 0; i < n; ++i)
  /* ... */
Мне кажется, easybudda именно это имел в виду
0
easybudda
27.07.2012, 14:34     stdlib.h - quicksort
  #11

Не по теме:

Цитата Сообщение от orlov Посмотреть сообщение
напиши qsort(a+1, n, sizeof(long), less_cmp);
Спасибо, Кеп, но так
Цитата Сообщение от Nameless One Посмотреть сообщение
при вводе-выводе массива пользоваться циклом от нуля до n (не включая n)
привычнее...

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
27.07.2012, 14:34
Привет! Вот еще темы с ответами:

QuickSort на C++11 - C++
Написал быструю сортировку, добился работоспособности и сразу захотелось улучшить сам код. #include &lt;iostream&gt; #include...

QuickSort - C++
Помогите с алгоритмом и кодом на C++ быстрой сортировки! Наработок вообще нет!

Реализация QuickSort - C++
Ребят, есть нужда отсортировать массив структур по полю name (по алфавиту) реализовав алгоритм QuickSort. Написал вроде как черновой...

Прокомментировать код. QuickSort - C++
Напишите пожалуйста как можно подробнее комментарии к каждой строке, а то я точно чайник и мало что понимаю #include &lt;iostream&gt; ...


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

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

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