Здравствуйте, sprsrpsh, Вы писали:

S>Если верить Вашей оценке, то алгоритм рекурсивной сортировки Хоара тоже работает за
S>O(n*n) операций, там также сканируется весь массив. Но он работает за O(n*log(n)) операций... Странно, или может я не так мыслю. Если мой алгоритм не верен, помогите мне реализовать поиск наименьшего элемента методом дерева за O(log(n)) операций. Метод дерева: весь массив разбиваем на пары, в кажой паре берём наименьший элемент, далее действуем так же, пока не останется один элемент(мой алгоритм делает то же самое, нашёл я его в книжке "Программирование — теоремы и задачи" А. Шеня, там задача — найти минимум за log(n) операций, используя метод дерева).

1. В принципе невозможно найти минимальное значение из N неупорядоченных элементов за время, меньшее чем O(N). Хотя бы по 1 разу нужно каждый элемент посетить. Хоть деревом, хоть тушкой, хоть чучелком.

2. Quicksort (сортировка Хоара) здесь не при чём. Если ты работаешь с упорядоченным массивом (единожды потратившись на его сортировку), то поиск минимума мгновенный; зато каждый раз, совершая вставку в массив, двигаешь в среднем N/2 элементов.

3. Для твоей задачи нужен контейнер "очередь с приоритетами".
Ведь, если отвлечься от способа хранения данных, алгоритм сводится к

priority_queue pq;
// первоначальное заполнение
for(i=0; i<N; ++i) push_pq(pq, data[i]);

// сложение
for(i=0; i<N-1; ++i) // повторять N-1 раз
{
  pair  = pop_minimum_from_pq(pq);
  pair += pop_minimum_from_pq(pq);
  s += pair;
  push_pq(pq, pair);
}
// полная сумма - последний элемент в очереди
total = pop_pq(pq);

Очевидно, очередь можно сделать на
— несортированном массиве: вытаскивание минимума сводится к его линейному поиску (и линейному сдвигу всех остальных), вставка — дописывание в конец
— массиве, сортированном по убыванию: вытаскивание — вытаскивание из конца, вставка — логарифмический поиск позиции и линейный сдвиг
— пирамиде: и вытаскивание, и вставка логарифмические

Кстати, пирамидальная сортировка (запихать всё в пирамиду, а затем всё оттуда повытаскивать) в среднем вдвое медленнее быстрой, но зато — заведомо линейно-логарифмическая (в то время как быстрая в худшем случае — квадратичная).