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

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

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

stdlib.h - quicksort - C++

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

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

C++ прoблемка с stdlib.h
ПРИШЛИТЕ МНЕ ПОЖАЛУЙСТA ФАЙЛ stdlib.h ДЛЯ VS2006 C++
C++ Число перестановок QuickSort
C++ Ошибка stdlib.h
C++ QuickSort
QuickSort найдите ошибку C++
C++ Stdlib system
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
nexen
187 / 180 / 3
Регистрация: 27.01.2012
Сообщений: 1,335
26.07.2012, 13:37     stdlib.h - quicksort #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 И что ещё за очень быстрый метод Хоара?
rangerx
1922 / 1531 / 139
Регистрация: 31.05.2009
Сообщений: 2,894
26.07.2012, 13:51     stdlib.h - quicksort #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;
}
Catstail
Модератор
22148 / 10622 / 1729
Регистрация: 12.02.2012
Сообщений: 17,667
26.07.2012, 13:55     stdlib.h - quicksort #4
Цитата Сообщение от SeryZone Посмотреть сообщение
ничего не получилось.
- вообще не сортирует?
SeryZone
56 / 28 / 5
Регистрация: 09.03.2012
Сообщений: 726
Записей в блоге: 1
26.07.2012, 18:20  [ТС]     stdlib.h - quicksort #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]);
}
nexen
187 / 180 / 3
Регистрация: 27.01.2012
Сообщений: 1,335
26.07.2012, 18:39     stdlib.h - quicksort #6
SeryZone, моя сортирует, но я, видимо, не существую.
настойчивое чувство, что меня специально игнорят ; (
Jupiter
Каратель
Эксперт C++
6549 / 3969 / 226
Регистрация: 26.03.2010
Сообщений: 9,273
Записей в блоге: 1
Завершенные тесты: 2
26.07.2012, 18:54     stdlib.h - quicksort #7
Цитата Сообщение от SeryZone Посмотреть сообщение
сортирует, но не полностью
чем докажешь?

Добавлено через 1 минуту
Цитата Сообщение от SeryZone Посмотреть сообщение
Проверьте с большим количеством элементов.
проверей, УМВР
easybudda
Эксперт С++
9412 / 5435 / 917
Регистрация: 25.07.2009
Сообщений: 10,428
26.07.2012, 19:49     stdlib.h - quicksort #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 начинается...
orlov
Сообщений: n/a
27.07.2012, 10:22     stdlib.h - quicksort #9
Цитата Сообщение от easybudda Посмотреть сообщение
Вот как бы ещё функции qsort намекнуть, что индексация в массиве не с 0, как обычно, а с 1 начинается...
a это указатель на int, напиши qsort(a+1, n, sizeof(long), less_cmp);
Nameless One
Эксперт С++
5765 / 3414 / 255
Регистрация: 08.02.2010
Сообщений: 7,430
27.07.2012, 10:41     stdlib.h - quicksort #10
orlov, я думаю, что проще и логичнее будет при вводе-выводе массива пользоваться циклом от нуля до n (не включая n):

C
1
2
for(i = 0; i < n; ++i)
  /* ... */
Мне кажется, easybudda именно это имел в виду
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
27.07.2012, 14:34     stdlib.h - quicksort
Еще ссылки по теме:

C++ Прокомментировать код. QuickSort
C++ Сортировка методом QuickSort
Реализация QuickSort C++
QuickSort на C++11 C++

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

Или воспользуйтесь поиском по форуму:
easybudda
27.07.2012, 14:34     stdlib.h - quicksort
  #11

Не по теме:

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

Yandex
Объявления
27.07.2012, 14:34     stdlib.h - quicksort
Ответ Создать тему
Опции темы

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