Какие есть самые лучшие алгоритмы сортировки, самые быстрые?

KlikQ

Подскажите пожалуйста, какие есть самые лучшие алгоритмы сортировки, самые быстрые. Например есть одномерный массив чисел, как его быстро отсортировать? Или например есть одномерный массив символов, как его быстро отсортировать по убыванию или наоборот? Если можете, напишите код на Си, как пример. Заранее спасибо.
10 ответов

KlikQ

Используй встроенную функцию qsort.
#include <stdio.h>
#include <stdlib.h>
 
#define SIZE 100 // размер выделения памяти
 
void init(int[], int);
int compareASC(const void*, const void*);
int compareDESC(const void*, const void*);
void print(int[], int);
 
int main()
{
    int *p = (int*) malloc(SIZE * sizeof(int)); // выделяем память
 
    if(p == NULL) { // если память не может выделиться
        printf("Error! No free memory!");
        system("pause");
        exit(0);
    }
 
    // заполняем массив значениями
    init(p, SIZE);
 
    // сортируем
    qsort(p, SIZE, sizeof(int), compareASC);
    //qsort(p, SIZE, sizeof(int), compareDESC); - сортировка в обратном порядке
 
    // выводим массив
    print(p, SIZE);
 
    // после использования памяти освождаем её
    free(p);
    p = NULL;
 
    system("pause");
    return 0;
}
 
void init(int arr[], int len) {
    int i;
    for(i = 0; i < len; i++) arr[i] = rand(); // заполняем случайными числами
}
 
int compareASC(const void *p1, const void *p2) {
    int n1 = *(int*)p1;
    int n2 = *(int*)p2;
 
    if(n1 < n2) return -1;
    if(n1 == n2) return 0;
    else return 1;
}
 
int compareDESC(const void *p1, const void *p2) {
    return -compareASC(p1, p2);
}
 
void print(int arr[], int len) {
    int i;
    for(i = 0; i < len; i++) {
        printf("%d\n", arr[i]);
    }
}


KlikQ

Простите, забыл написать, нужно использовать только библиотеку stdio.h .


KlikQ

KlikQ, держите - Алгоритмы сортировок Я советую 6 вариант - быструю сортировку.


KlikQ

спасибо


KlikQ

Лично мне больше всего нравится гномья сортировка, она проста, довольно эффективна и легко реализуется на C.


KlikQ

Vtulhu, ваша сортировка похожа на сортировку "Пузырек".


KlikQ

Большинство существующих алгоритмов сортируют за N * log2 (N)


KlikQ

Если известен диапазон значений элементов массива (например, это 8-битные числа), то можно просто посчитать встречаемость каждого такого числа в исходном массиве.


KlikQ

она проста, довольно эффективна
И в чем же её эффективность, позвольте разузнать?
(int*) malloc(SIZE * sizeof(int));
Ох и любят же приплюснутые маллок приводить