Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.75/8: Рейтинг темы: голосов - 8, средняя оценка - 4.75
56 / 28 / 18
Регистрация: 09.03.2012
Сообщений: 726
Записей в блоге: 1
1

stdlib.h - quicksort

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

Идея такова: отсортировать массив A[max - 100 000] очень быстрым методом Хоара. Пробовал в stdlib.h делать QuickSort - ничего не получилось. Все значения элементов - до 263-1. Т.е. влазят в тип long. Помогите отсортировать!
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
26.07.2012, 13:33
Ответы с готовыми решениями:

прoблемка с stdlib.h
Моя знакомая удалила случайно файл stdlib.h Когда она подключает файл и вызывает оттуда функцию...

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

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

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

10
187 / 180 / 25
Регистрация: 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
1992 / 1592 / 488
Регистрация: 31.05.2009
Сообщений: 2,980
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
Модератор
Эксперт Python
26647 / 13895 / 2642
Регистрация: 12.02.2012
Сообщений: 22,780
Записей в блоге: 1
26.07.2012, 13:55 4
Цитата Сообщение от SeryZone Посмотреть сообщение
ничего не получилось.
- вообще не сортирует?
0
56 / 28 / 18
Регистрация: 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
187 / 180 / 25
Регистрация: 27.01.2012
Сообщений: 1,335
26.07.2012, 18:39 6
SeryZone, моя сортирует, но я, видимо, не существую.
настойчивое чувство, что меня специально игнорят ; (
0
Каратель
Эксперт С++
6593 / 4014 / 401
Регистрация: 26.03.2010
Сообщений: 9,273
Записей в блоге: 1
26.07.2012, 18:54 7
Цитата Сообщение от SeryZone Посмотреть сообщение
сортирует, но не полностью
чем докажешь?

Добавлено через 1 минуту
Цитата Сообщение от SeryZone Посмотреть сообщение
Проверьте с большим количеством элементов.
проверей, УМВР
1
Модератор
Эксперт PythonЭксперт JavaЭксперт CЭксперт С++
10837 / 6647 / 1614
Регистрация: 25.07.2009
Сообщений: 12,426
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
27.07.2012, 10:22 9
Цитата Сообщение от easybudda Посмотреть сообщение
Вот как бы ещё функции qsort намекнуть, что индексация в массиве не с 0, как обычно, а с 1 начинается...
a это указатель на int, напиши qsort(a+1, n, sizeof(long), less_cmp);
Эксперт С++
5811 / 3462 / 356
Регистрация: 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
27.07.2012, 14:34
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
27.07.2012, 14:34
Привет! Вот еще темы с ответами:

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

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

QuickSort
Начал разбираться с сортировками и вот QuickSort меня озадачил. Дело в том что в интернете есть...

QuickSort на C++11
Написал быструю сортировку, добился работоспособности и сразу захотелось улучшить сам код. ...


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

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

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