Модераторы: Daevaorn
  

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Как отсортировать массив в обратном порядке? 
:(
    Опции темы
sergejzr
Дата 12.7.2005, 13:11 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Un salsero
Group Icon


Профиль
Группа: Админ
Сообщений: 13285
Регистрация: 10.2.2004
Где: Германия г .Ганновер

Репутация: 19
Всего: 360
Необходимо наилучшим(быстрейшим) способом отсортировать поле от большего значения к меньшему.
Плиз дайте пример на ANSI Cи.

quicksort "развернуть" что то не получилось..


--------------------
Me.
FB.
LinkedIn.
ORCID.
YT.
PM WWW IM ICQ Skype GTalk Jabber AOL YIM MSN   Вверх
Mayk
Дата 12.7.2005, 13:23 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


^аВаТаР^ сообщение>>
****


Профиль
Группа: Участник
Сообщений: 2616
Регистрация: 22.5.2005
Где: за границей разум а

Репутация: 45
Всего: 134
qsort пойдёт?
Код

#include <stdlib.h>
#include <stdio.h>
int intcmp(const void*a, const void* b)
{
        return *(int*)b-*(int*)a;
}
int main()
{
        int a[10] = {1,4,2,6,5,7,9,0,2,13};
        int i;
        qsort(a,10,sizeof(int),intcmp);
        for(i=0; i != 10;++i){
                printf("%d ",a[i]);
        }

}



--------------------
 Здесь был кролик. Но его убили.
Человеки < кроликов, йа считаю.
PM MAIL WWW ICQ   Вверх
vadims
Дата 12.7.2005, 13:49 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 305
Регистрация: 8.6.2005

Репутация: 2
Всего: 17
sergej.z
Уточни, что значит отсортировать поле ???

Если все же отсортировать по полю, то подход от Mayk, с уточнением - наверное все же речь идет о сортировке массива структур по значению поля, тогда

Код

#include <stdlib.h>
#include <stdio.h>

struct TMyRec
{
   int key;  // мб любой тип
   ....
};

int intcmp(const void*a, const void* b)
{ // фукция должна принять решение какая из записей a или b больше
   // и вернуть 0 - равны, >0 - a больше b, <0 - b больше a
        return( (TMyRec*)b->key - (TMyRec*)a->key );
}
int main()
{
  TMyRec Mas[] = 
  {
    { 1, ... },
    { 4, ... },
    { 2, ... },
    { 6, ... },
    { 5, ... },
    { 7, ... },
    { 9, ... },
      . . .
   };

   qsort( Mas, sizeof(Mas)/sizeof(Mas[0]), sizeof(TMyRec), intcmp );

}





--------------------
Cpu not found ! Press any key for software emulation.
PM MAIL   Вверх
sergejzr
Дата 12.7.2005, 14:18 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Un salsero
Group Icon


Профиль
Группа: Админ
Сообщений: 13285
Регистрация: 10.2.2004
Где: Германия г .Ганновер

Репутация: 19
Всего: 360
vadims
feld это поле с немецкого дословно. А по смыслу - массив. С терминами иногда путаюсь smile
Спасибо smile


Mayk, спасибо! То, что надо.


--------------------
Me.
FB.
LinkedIn.
ORCID.
YT.
PM WWW IM ICQ Skype GTalk Jabber AOL YIM MSN   Вверх
Dr.Wisdom
Дата 16.7.2005, 08:59 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 145
Регистрация: 6.1.2005

Репутация: нет
Всего: 0
Сортировок много но эта самая простая (вроде)
Ходять слухи что qsort медленная

Код

//Пусть массив
int A[Max];
//.......................
for(int i=0;i<Max;i++)
{
for(int j=i;j<Max;j++)
{
if(A[i]<A[j])
{
int k = A[j];
A[j] = A[i];
A[i] = k;
}
}
}

Писал прямо тут, но идея та.
Кажется это называется прямая сортировка. Для больших Max.
Для меньших есть Пузырьковая (она дурацкая, но для малых множестьв работает быстрее), концепцию помню, пишу находу:
Код

char st = 0;
while(!st)
{
st = 1;
for(int i = 1;i<Max;i++)
{
if(A[i-i]<A[i])
{
int k = A[i-1];
A[i-1] = A[i];
A[i] = k;
st = 0;
}
}
}

Есть еще третья классическая но я даже концепцию не помню.

Это сообщение отредактировал(а) Dr.Wisdom - 16.7.2005, 10:30
--------------------
VIVA LA RESISTANCE
PM MAIL   Вверх
Void
Дата 16.7.2005, 09:34 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


λcat.lolcat
****


Профиль
Группа: Участник Клуба
Сообщений: 2206
Регистрация: 16.11.2004
Где: Zürich

Репутация: 40
Всего: 173
Цитата(Dr @ 16.7.2005, 10:59)
Ходять слухи что qsort медленная

QuickSort - быстрейший алгоритм обменной сортировки. N * log(N) с лучшей известной асимптотикой в общем случае. "Слухи", надо полагать - это то, что qsort из стандартной библиотеки C будет тормозить по сравнению с std::sort - из-за расходов на косвенный вызов предиката, когда в std::sort он, как правило, inline-подставляется.


--------------------
“Coming back to where you started is not the same as never leaving.” — Terry Pratchett
PM MAIL WWW GTalk   Вверх
comcon1
Дата 16.7.2005, 09:38 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 838
Регистрация: 11.6.2005
Где: Москва ДАС-МГУ

Репутация: 12
Всего: 17
Посмотрел исходник. При n<8 сортируется по тупому (как твой первый алгоритм).

Если нет -- рекурсивно с хитрым алгоритмом. Со стеком. Стек правда лимитирован 30 элементами. Но трудно сказать для каких массивов требуется больше. Рекурсивные алгоритмы сортировки на порядок быстрее обычных, т.к. идут за логарифм. время.

вот ссылка: qsort.c



Это сообщение отредактировал(а) comcon1 - 16.7.2005, 09:40


--------------------
user posted image
comcon1 on twitter
PM MAIL   Вверх
Void
Дата 16.7.2005, 10:32 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


λcat.lolcat
****


Профиль
Группа: Участник Клуба
Сообщений: 2206
Регистрация: 16.11.2004
Где: Zürich

Репутация: 40
Всего: 173
Цитата(comcon1 @ 16.7.2005, 11:38)
Стек правда лимитирован 30 элементами. Но трудно сказать для каких массивов требуется больше.

Глубина рекурсии не превысит log2(N) + 1. Значит, этого стека достаточно для сортировки массива из примерно 512 миллионов элементов.
Цитата(comcon1 @ 16.7.2005, 11:38)
Рекурсивные алгоритмы сортировки на порядок быстрее обычных, т.к. идут за логарифм. время.

С рекурсией это никак не связано. Например, HeapSort тоже имеет скорость O(N * log N), однако рекурсией там не пахнет.

В общем, 3-й том Кнута рулит smile


--------------------
“Coming back to where you started is not the same as never leaving.” — Terry Pratchett
PM MAIL WWW GTalk   Вверх
Dr.Wisdom
Дата 16.7.2005, 11:35 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 145
Регистрация: 6.1.2005

Репутация: нет
Всего: 0
Где можно найти описание работы qsort для разных размеров массивов.
Вообще где есть порталы связанные с подобными направлениями.
С математическими отступлениями. smile
--------------------
VIVA LA RESISTANCE
PM MAIL   Вверх
comcon1
Дата 16.7.2005, 11:50 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 838
Регистрация: 11.6.2005
Где: Москва ДАС-МГУ

Репутация: 12
Всего: 17
Сначала на Algolist.ru. Там много алгоритмов сортировки. А если задашь вопрос на форуме - получишь еще больше.
А ссылку на qsort я дал smile.


--------------------
user posted image
comcon1 on twitter
PM MAIL   Вверх
  
 Ответ в темуСоздание новой темы Создание опроса
Правила форума "С++:Общие вопросы"
Earnest Daevaorn

Добро пожаловать!

  • Черновик стандарта C++ (за октябрь 2005) можно скачать с этого сайта. Прямая ссылка на файл черновика(4.4мб).
  • Черновик стандарта C (за сентябрь 2005) можно скачать с этого сайта. Прямая ссылка на файл черновика (3.4мб).
  • Прежде чем задать вопрос, прочтите это и/или это!
  • Здесь хранится весь мировой запас ссылок на документы, связанные с C++ :)
  • Не брезгуйте пользоваться тегами [code=cpp][/code].
  • Пожалуйста, не просите написать за вас программы в этом разделе - для этого существует "Центр Помощи".
  • C++ FAQ

Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, Earnest Daevaorn
 
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | C/C++: Общие вопросы | Следующая тема »

Подписаться на тему | Подписка на этот форум | Скачать/Распечатать тему


 




[ Время генерации скрипта: 0.3746 ]   [ Использовано запросов: 22 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
 По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.