Сортировка элементов массива - сравнение двух способов

В статье показывается сортировка массива двумя способами. Каждый способ оценивается на количество затраченного сортировкой времени.

#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <conio.h>
#include <math.h>

inline void Change(int a[], int first, int second)
// меняем местами элементы буфера first на second
// a[] - наш массив
// first и second - номера элементов массива a, которые надо поменять местами!
{
    if (first == second) // Если одинаковые номера элементов, то не нужно менять их местами
        return;
    int i;

    i = a[second];
    a[second] = a[first];
    a[first] = i;

/*
// Можно еще так вот, но так медленнее:
    a[first] += a[second]; // Здесь,
    a[second] = a[first] - a[second]; // здесь,
    a[first] = a[first] - a[second]; // и здесь мы меняем местами два числа в буфере
*/
}

int FindMax(int a[], int max)
// Поиск максимального числа в массиве от a[0] до a[max]
// a[] - наш массив
// max - размер массива a
{
    int imax = 0;

    for (int i = 0; i <= max; i++)
    {
        if (a[imax] < a[i])
            imax = i;
    }

    return imax;
}

void Sort(int b[], int max)
// Сортировка номер один!
// b[] - наш массив
// max - размер массива b
{
    int i1;
    for (int i = max - 1; i > 0; i--)
    {
        i1 = FindMax(b, i); // Находим самое максимальное число в промежутке от a[0] до a[i]

        Change(b, i, i1); // ставим максимальное число в конец (а именно на место эллемента под номером i)
    }
}

void Sort1(int c[], int max)
// Сортировка номер два!
// c[] - наш массив
// max - размер массива c
{
    for (int i1 = 0; i1 < max; i1++)
    {
        for (int i = max-2; i >= i1; i--)
        {            
            if (c[i+1] > c[i]) continue;

            Change(c, i, i+1); // Двигаем минимальное число вверх, тем самым сортируя числа
        }
    }
}

void main()
{
#define MAX 100
    int a[MAX], b[MAX], c[MAX]; // Объявляем пару буферов

/*
// Можно две строки выше записать еще и так, тогда у юзера будет запрашиваться размер буфера
    int MAX;

    printf("Enter the size of array with the numbers: ");
    scanf("%i", &MAX);

    int *a = new int[MAX]; // Объявляем буфер
    int *b = new int[MAX]; // Объявляем буфер
    int *c = new int[MAX]; // Объявляем буфер
*/

    srand((unsigned)time(0));
    for (int i = 0; i < MAX; i++)
    {
        a[i] = rand(); // заполняем случайными числами
        b[i] = a[i]; // делаем копию
        c[i] = a[i]; // делаем копию
    }

    clock_t begin, end;
    begin = clock();
    Sort(b, MAX); // 
    end = clock();

    float f = (float)(end-begin); // Измеряем время, занятое сортировкой

    printf ("Sorting %i elements with the sort number 1 takes     %.0f msec.\r\n\r\n", MAX, f);

    begin = clock();
    Sort1(c, MAX); // 
    end = clock();
    float f1 = (float)(end-begin); // Измеряем время, занятое сортировкой


    printf ("Sorting %i elements with the sort number 2 takes     %.0f msec.\r\n", MAX, f1);

    // Вы хотите просмотреть отсортированные данные?
    printf("\r\n\r\n\r\nDo you really want to view the sorting result? (y/n)"); 
    short Key = 0;

    while (Key = _getch()) // Ожидание нажатия на кнопку
    {
        if (Key == 'n' || Key == 'N' || Key == 27) // если нажата кнопк N или Esc, то
            return; // выход
        else if (Key == 'y' || Key == 'Y') // если y, то
            break; // то продолжаем
    }

    printf("\r\n\r\n\r\n");
    printf(" N.    unsorted     N.    1-st sort     N.    2-nd sort\r\n");
    printf("\r\n");
    for (i = 0; i < MAX; i++)
        printf("%3i.    %5i        %3i.    %5i        %3i.    %5i\r\n", 
		i+1, a[i], i+1, b[i], i+1, c[i]); // Печать содержимого массивов
    printf("\r\nPress any key to continue\r\n");

    Key = 0;

    while (!Key) Key = _getch(); // Ожидание нажатия на кнопку
}

Первый способ будет быстрее. Были получены следующие результаты на сортировке 50000 элементов:

• Сортировка первым способом заняла 11786 мс.
• Сортировка вторым способом заняла 22953 мс.

Второй способ медленнее в ~1.9 раза! Так что делайте выводы, господа ;)