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 журнал (п)), если вы знаете что-нибудь о ваших данных - в статье Википедии о Radix Sort

Answer 2

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

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

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

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

Answer 3

Зависит от

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

Основы

Чтобы понять, какие алгоритмы работают лучше всего, вы будете нуждаться в базовых знаниях algorithms complexity и big-O notation, так что вы можете понять, как они оценивают с точкой зрения average case, best case and worst case scenarios. При необходимости вам также необходимо обратить внимание на sorting algorithm's stability.

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

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

• quicksort
• shellsort
• mergesort

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

• bubblesort
• selection sort
• insert sort

Далее

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

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

Answer 4

Я хотел бы внести некоторые изменения: В 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) 

Answer 5

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