чем на сях можно массив по возрастанию или наоборот отсортировать?

man qsort тебе поможет

спасибо, получилось :)

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
// подключить API ImageMagick
#include <magick/api.h>
                                                                                                                                                       
int cmp(const void *a, const void *b) {
  return *(int*)a - *(int*)b;
}
                                                                                                                                                       
....

  for (i = 0; i <= s-1; i++) {
    sm[i]=(int)pixels[i].blue;
  }
  qsort(sm, s, sizeof(int), cmp );
  for (i = 0; i <= s-1; i++) {
    printf("sorted: %d\t%d\n",i,(int)sm[i]);
  }

ну вообще-то 16 млн чисел каждое из которых может принимать только 65536 значений быстрее сортировать заводя массив из 65536 счетчиков и подсчитывая встречаемость каждой точки.

разве быстрее?? 16млн*65536 итераций для сравнение, т.е. оно не закончит работу в обозримом будущем... :( А есть ли в сях аналог перлового хеша(по функциональности всмысле), чтобы это реализовать...

:) Ты не понял, тебе надо один раз пройтись по 16 млн, потом один раз пройтись по 65536.

гы, я уж вот так извратился :)

  for (i = 0; i <= s-1; i++) {
    y[(int)pixels[i].blue]++;
  }

где порядковое значение массива y есть значение яркости, а число, 
содержащееся в какоммнить элементе массива - число пикселей с данной 
яркостью(порадковым номером массива)...

Но на самом деле надо выделить динамический диапазон яркостей в 
зависимости от экспозиции на фотокамере... вобщем, сортировка то не 
помогла, я пока не знаю куда копать... и это тоже не совсем то, 
походу... думаю пока сижу...

>разве быстрее??

при qsort сложность O(n*log(n)),
при варианте который предложил товарищ O(n),

тебя в школе ничему не учили,
или ты программист от сохи?

от сохи и с ложкой!

>Ты не понял, тебе надо один раз пройтись по 16 млн, потом один раз пройтись по 65536.

Не факт. Возможно нужно записать числа в системе счисления по основанию 256( байты) и пройтись два раза по 256.

>Не факт. Возможно нужно записать числа в системе счисления по основанию 256( >байты) и пройтись два раза по 256.

быстрее 65536, я измерял.

> тебя в школе ничему не учили,
> или ты программист от сохи?

Тут кто-то другой от сохи. Во-первых, quicksort работает за
время O(n^2). Во-вторых, при данных ограничениях анализ алгоритма
методом размахивания O-шками не работает.

А можно узнать почему?

Между тем оптимальный алгоритм, для данного случая, даёт сложность=n (где n-количество сортируемых чисел).

ага, но тока линейность будет "скомпенсирована" дико большим перетаскиванием данный из одного места в др.

> Во-первых, quicksort работает за время O(n^2).

в среднем (матожидание по всем перестановкам) он работает O(n*logn)

симплексный метод в худшем случае тоже за экспоненту работает, однако его используют, потому что на практике работает хорошо..

Нет. Ничего никуда перетаскивать не надо. по памяти сложность будет n+65536 ну и ещё немного на всякую сопроводительную требуху.

Офигеть, ты это всерьёз? :)

За n^2 пузырьковая сортирует (то есть самая медленная).

Не пости сюда больше. По крайней мере так категорично.

> Офигеть, ты это всерьёз? :) За n^2 пузырьковая сортирует (то есть самая медленная).

немножко он прав. Стандартная реализация qsort действительно имеет O(n^2) в худшем случае. O(n*logn) только в среднем.

Это скорее теоретически. Что-то мне подсказывает, что товарищ просто перепутал.

>Офигеть, ты это всерьёз? :)

>За n^2 пузырьковая сортирует (то есть самая медленная).

Не пости сюда больше. По крайней мере так категорично.

Пузырук (ну или сортировка вставками) при некоторых условиях работает за O(n), а merge_sort за O(n*log n). В качестве упражнения можешь подумать почему

Подсказка: когда массив почти отсортирован

Когда говорят "алгоритм работает за ..." или "сложность такая-то" - всегда подразумевается худший случай, если не оговорено противное.
Так вот, quicksort работает за O(n^2) [если кто-то это не помнит/не
знает, ему стоит почитать что-нибудь про элементарные алгоритмы, прежде
чем спорить здесь], что не мешает ему быть в среднем очень эффективным.

>огда говорят "алгоритм работает за ..." или "сложность такая-то" - всегда подразумевается худший случай

Где и кем подразумевается, не могли бы дать адрес.

Какую-нибудь умную книжку почитайте. Кормена, например.

>время O(n^2)

бред, измерять скорость алгоритма по худшему случаю, при условие случайных данных это бред, почитай что-нибудь ламо.

> Пузырук (ну или сортировка вставками) при некоторых условиях работает за O(n),

Это модифицированный пузырёк!