C Советы по сортировке массивов

Question

       a=[1,3,6,7,1,2]

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

 void BubbleSort(int a[], int array_size)
 {
 int i, j, temp;
 for (i = 0; i < (array_size - 1); ++i)
 {
      for (j = 0; j < array_size - 1 - i; ++j )
      {
           if (a[j] > a[j+1])
           {
                temp = a[j+1];
                a[j+1] = a[j];
                a[j] = temp;
           }
      }
 }
 }   

Answer 1

В C вы можете использовать встроенную команду qsort:

int compare( const void* a, const void* b)
{
     int int_a = * ( (int*) a );
     int int_b = * ( (int*) b );

     if ( int_a == int_b ) return 0;
     else if ( int_a < int_b ) return -1;
     else return 1;
}

qsort( a, 6, sizeof(int), compare )

см .: http://www.cplusplus.com/reference/clibrary/cstdlib/qsort/

---

Чтобы ответить на вторую часть вашего вопроса: оптимальный (основанный на сравнении) алгоритм сортировки - это алгоритм, который выполняется с O (n log (n)) сравнениями. Некоторые из них имеют это свойство (включая быструю сортировку, сортировку слиянием, сортировку кучи и т. Д.), Но какой из них использовать, зависит от вашего варианта использования.

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

Answer 2

В вашем конкретном случае самая быстрая сортировка, вероятно, описана в этом ответе . Он точно оптимизирован для массива 6 дюймов и использует сортировочные сети. Это 20 раз (измерено на x86) быстрее, чем библиотека qsort. Сети сортировки оптимальны для сортировки массивов фиксированной длины. Поскольку они представляют собой фиксированную последовательность инструкций, они даже могут быть легко реализованы аппаратно.

Вообще говоря, существует множество алгоритмов сортировки, оптимизированных для некоторых специализированных случаев. Алгоритмы общего назначения, такие как сортировка кучи или быстрая сортировка, оптимизированы для сортировки на месте массива элементов. Они дают сложность O (n.log (n)), где n - количество элементов для сортировки.

Библиотечная функция qsort () очень хорошо закодирована и эффективна с точки зрения сложности, но использует вызов некоторой функции сравнения, предоставленной пользователем, и этот вызов имеет довольно высокую стоимость.

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

Answer 3

Зависит

Это зависит от разных вещей. Но в целом алгоритмы, использующие Divide-and-Conquer / дихотомический подход, будут хорошо работать для сортировки проблем, поскольку они представляют интересные сложности среднего случая.

Основы

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

Например, эффективным алгоритмом обычно является быстрая сортировка. Однако, если вы дадите быстрой сортировке полностью инвертированный список, он будет работать плохо (простая сортировка выбора будет работать лучше в этом случае!). Shell-sort также обычно будет хорошим дополнением к быстрой сортировке, если вы выполните предварительный анализ списка.

Посмотрите на следующее, для «расширенных поисков» с использованием подходов «разделяй и властвуй»:

• * 1027 быстрая сортировка *
• ShellSort
• * 1035 слияние *

И эти более простые алгоритмы для менее сложных:

• BubbleSort
• выбор сортировки
• вставить сортировку

Далее

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

Как указал Р. в комментариях и Крисс в своем ответе, вы можете взглянуть на HeapSort , который обеспечивает теоретически лучшую сложность сортировки, чем быстрая сортировка (но выиграет ' В практических условиях часто бывает лучше). Существуют также варианты и гибридные алгоритмы (например, TimSort ).

Answer 4

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

Answer 5

Я хотел бы внести некоторые изменения: В C вы можете использовать встроенную команду qsort :

int compare( const void* a, const void* b)
{
   int int_a = * ( (int*) a );
   int int_b = * ( (int*) b );

   // an easy expression for comparing
   return (int_a > int_b) - (int_a < int_b);
}

qsort( a, 6, sizeof(int), compare )