Сортировка пузырьком, быстрая сортировка, сортировка вставками, сортировка выбором - реализация и сравнение на C.

September 9, 2018 13:30

В данной статье мы подготовили для Вас реализацию и сравнение различных сортировок на языке программирования C по различным критериям: числу сравнений, числу перестановок и времени выполнения.

Одной из простейших сортировок является "сортировка пузырьком". Принцип ее работы заключается в том, что алгоритм идет по массиву снизу вверх и по пути проверяет пары рядом стоящих элементов (соседних). Если получается так, что в паре элементы находятся в неверном порядке - они меняются между собой местами.

Быстрая сортировка - достаточно старый метод и сейчас используется в основном с доработками. Смысл ее работы в том, что выбирается основной элемент (a[i]) и по нему массив разбивается на две части, после чего все ключи, которые меньше или равны a[i] перемещаются влево от этого элемента, а остальные - вправо. Таким образом получается два подмассива. В каждом из них производится та же самая операция, пока элементов не станет меньше двух. В конце концов получится отсортированный массив.

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

Идея сортировки выбором заключается в том, чтобы создать отсортированную последовательность путем добавки к ней элементов по очереди (один за другим) в правильном порядке.

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

/* 
    Реализация и сравнение основных алгоритмов сортировки
*/

typedef struct {
    size_t transpositions, comparations;
} Counter;

typedef struct {
    const char *title;
    Counter counter;
    double duration;
    size_t arrayLength;
} TestResult;

typedef void (*SortFunction)(int*, size_t);
typedef Counter (*GetCounterSortFunction)(int*, size_t);
typedef int* (*ArrayCreatorFunction) (size_t);

/*  
    Функция возвращает отсортированный массив целых чисел   
*/
int *GetSortedIntArray(size_t size) {
    int *array = (int*) malloc(sizeof(int) * size);
    
    for (int i = 0; i < size; ++i) {
        array[i] = i;
    }

    return array;
}

/*  
    Функция возвращает обратно отсортированный массив целых чисел   
*/
int *GetBackSortedIntArray(size_t size) {
    int *array = (int*) malloc(sizeof(int) * size);
    
    for (int i = 0; i < size; ++i) {
        array[i] = size - i - 1;
    }

    return array;
}

/*  
    Функция возвращает частично отсортированный массив целых чисел   
*/
int *GetPartiallySortedIntArray(size_t size) {
    int *array = (int*) malloc(sizeof(int) * size);
    
    for (int i = 0; i < size; ++i) {
        array[i] = (i > size / 2) ? rand() % size : i;
    }

    return array;
}

/*  
    Функция сортировки вставками 
    Параметры: array - указатель на первый элемент массива, size - размер массива     
*/
void InsertSort(int *array, size_t size) {
    int temp, i, j;
    
    for (i = 0; i < size; ++i) {
        temp = array[i];
        
        for (j = i - 1; j >= 0; --j) {
            if (temp > array[j]) { break; }
            array[j + 1] = array[j];
        }
        array[j + 1] = temp;
    }
}

/*
    Функция сортировки вставками с подчётом количества перестановок и сравнений
    Параметры: array - указатель на первый элемент массива, size - размер массива
    Возвращаемое значение: структура Counter с заполнеными полями
*/
Counter GetInsertSortCounter(int *array, size_t size) {
    int temp, i, j;
    Counter counter = { 0, 0 };
    
    for (i = 0; i < size; ++i) {
        temp = array[i];
        for (j = i - 1; j >= 0; --j) {
            counter.comparations++;

            if (temp > array[j]) { break; }
            array[j + 1] = array[j]; 
        }
        counter.transpositions++;
        array[j + 1] = temp; 
    }
    return counter;
}

/*  
    Функция сортировки выбором 
    Параметры: array - указатель на первый элемент массива, size - размер массива     
*/
void SelectionSort(int *array, size_t size) {
    int minId = 0;
    
    for (int i = 0; i < size; ++i) {
        minId = i;
        for (int j = i + 1; j < size; ++j) {
            if (array[j] < array[minId]) {
                minId = j;
            }
        }
        
        if (minId != i) {
            int temp = array[i];
            array[i] = array[minId];
            array[minId] = temp;
        }
    }
}

/*
    Функция сортировки выбором с подчётом количества перестановок и сравнений
    Параметры: array - указатель на первый элемент массива, size - размер массива
    Возвращаемое значение: структура Counter с заполнеными полями
*/
Counter GetSelectionSortCounter(int *array, size_t size) {
    
    int minId = 0;
    Counter counter = { 0, 0 };

    for (int i = 0; i < size; ++i) {
        minId = i;
        for (int j = i+1; j < size; ++j) {
            counter.comparations++;
            if (array[j] < array[minId]) {
                minId = j;
            }
        }
        
        if (minId != i) {
            int temp = array[i];
            array[i] = array[minId];
            array[minId] = temp;
            counter.transpositions++;
        }
    }
    return counter;
}

/*  
    Функция сортировки пузырьком 
    Параметры: array - указатель на первый элемент массива, size - размер массива     
*/
void BubbleSort(int* array,  size_t count) {
    int temp,i,j;
    
    for (i = 1; i < count; i++)
        for (j = count - 1; j >= i; j--)    {
            if (array[j - 1] > array[j]) {
                temp = array[j - 1];
                array[j - 1] = array[j];
                array[j] = temp;
            }
        }
}

/*
    Функция сортировки пузырьком с подчётом количества перестановок и сравнений
    Параметры: array - указатель на первый элемент массива, size - размер массива
    Возвращаемое значение: структура Counter с заполнеными полями
*/
Counter GetBubbleSortCounter(int* array,  size_t size) {
    int temp,i,j;
    Counter counter = { 0, 0 };  
    
    for (i = 1; i < size; i++)
        for (j = size - 1; j >= i; j--)    {
            counter.comparations++;
            if (array[j - 1] > array[j]) {
                temp = array[j - 1];
                array[j - 1] = array[j];
                array[j] = temp;
                counter.transpositions++;    
            }
        }
    return counter;    
}


/*  
    Функция быстрой сортировки
    Параметры: array - указатель на первый элемент массива, size - размер массива
*/
void QuickSort(int *array, size_t length) {

    void quickSort(int *array, int left,int right) {
        int i,j,p,temp;
        i = left;
        j = right;
        p = array[(left + right) / 2];
        
        do {
            while ((array[i] < p) && (i < right))  i++; // поиск элемента больше или равного p
            while ((array[j] > p) && (j > left)) j--; // поиск элемента меньше или равного p
            
            if (i <= j)    {
                temp = array[i];
                array[i] = array[j];
                array[j] = temp;
                i++; 
                j--;
            }
            
        } while (i <= j);
        
        if (j > left) quickSort(array, left, j);
        if (i < right) quickSort(array,i, right); 
    }

    quickSort(array, 0, length);
}

/*
    Функция быстрой сортировки с подчётом количества перестановок и сравнений
    Параметры: array - указатель на первый элемент массива, left, right - границы сортировки
    Возвращаемое значение: структура Counter с заполнеными полями
*/
Counter GetQuickSortCounter(int *array, size_t length) {

    Counter getQuickSortCounter(int *array, int left,int right) {
        int i, j, p, temp; 
        Counter counter = { 0, 0 }; 
            
        i = left;
        j = right;
        p = array[(left + right) / 2];
        
        do {
            // ищу элемент больше или равный p
            while ((array[i] < p) && (i < right)) {    
            i++;
            counter.comparations += 2; 
            } 
            // ищу элемент меньше или равный p
            while ((array[j] > p) && (j > left)) {   
                j--;
                counter.comparations += 2;
            } 

            if (i <= j)    {
                temp = array[i];
                array[i] = array[j];
                array[j] = temp;
                i++;
                j--;
            }
            counter.comparations++; 
            counter.transpositions++;    
            
        } while (i <= j);
        
        if (j > left) {
            Counter temp = getQuickSortCounter(array, left, j);
            counter.transpositions += temp.transpositions;
        }

        if (i < right) {
            Counter temp = getQuickSortCounter(array,i, right);
            counter.comparations += temp.comparations; 
        }  
        return counter;
    }

    return getQuickSortCounter(array, 0, length);
}


/*  
    Функция пирамидальной сортировки
    Параметры: array - указатель на первый элемент массива, size - размер массива
*/
void PyramidalSort(int *array, size_t size) {
    
    void shiftDown(int *array, int i, size_t size) {
        int nmax = i;
        int value = array[nmax];

        while (1) {
            int childN = i * 2 + 1;

            if ((childN < size) && (array[childN] > value)) 
                nmax = childN;

            ++childN;

            if ((childN < size) && (array[childN] > array[nmax]))
                nmax = childN;

            if (nmax == i) 
                break;

            array[i] = array[nmax];
            array[nmax] = value;

            i = nmax;
        }
    }

    for (int i = (size / 2 - 1); i >= 0; --i) {
        shiftDown(array, i, size);
    }

    while(size > 1) {
        size--;
        int first_elem = array[0];
    
        array[0] = array[size];
        array[size] = first_elem;

        shiftDown(array, 0, size);
    }
}

Counter GetPyramidalSortCounter(int *array, size_t size) {
    Counter counter = { 0, 0 };

    void shiftDown(int *array, int i, size_t size) {
        int nmax = i;
        int value = array[nmax];

        while (1) {
            int childN = i * 2 + 1;

            if ((childN < size) && (array[childN] > value)) 
                nmax = childN;

            ++childN;

            if ((childN < size) && (array[childN] > array[nmax]))
                nmax = childN;

            if (nmax == i) 
                break;

            array[i] = array[nmax];
            array[nmax] = value;

            i = nmax;

            counter.comparations += 5;
            counter.transpositions++;
        }
    }

    for (int i = (size / 2 - 1); i >= 0; --i) {
        shiftDown(array, i, size);
    }

    while(size > 1) {
        size--;
        int first_elem = array[0];
    
        array[0] = array[size];
        array[size] = first_elem;
        counter.transpositions++;

        shiftDown(array, 0, size);
    }

    return counter;
}

/*
    Функция измеряет время сортировки массива 
    Параметры: sortFunction - функция сортировки, array - указатель на первый элемент массива,
    count - размер массива,
    Возвращаемое значение: время в секундах 
*/
double GetSortFunctionDuration(SortFunction sortFunction, int *array, size_t length) {
    clock_t time = clock();
    sortFunction(array, length);

    time = clock() - time;
    return (double) time / CLOCKS_PER_SEC;
}

TestResult GetSortFunctionTestResult(
    const char *title,
    size_t length,

    SortFunction sortFunction, 
    GetCounterSortFunction getCounterSortFunction,
    ArrayCreatorFunction arrayCreatorFunction) {
    
    int *array = arrayCreatorFunction(length);

    TestResult testResult = {
        title,
        getCounterSortFunction(array, length),
        GetSortFunctionDuration(sortFunction, array, length),
        length
    };

    free(array);
    return testResult;
}

void PrintSortFunctionTestResult(TestResult testResult) {
    printf("%-20s%15d%15d%15d%15f\n", 
    testResult.title,
    testResult.arrayLength,
    testResult.counter.comparations,
    testResult.counter.transpositions,
    testResult.duration);
}

int main(int argc, char const *argv[])
{
    const int length = 10000;

    printf("%-20s%15s%15s%15s%15s\n\n", 
        "Algorithm",
        "Array length",
        "Comparations",
        "Transpositions",
        "Duration");

    PrintSortFunctionTestResult(
        GetSortFunctionTestResult("Bubble sort", 
            length, 
            BubbleSort, 
            GetBubbleSortCounter,
            GetBackSortedIntArray));

    PrintSortFunctionTestResult(
        GetSortFunctionTestResult("Quick sort", 
            length, 
            QuickSort, 
            GetQuickSortCounter, 
            GetBackSortedIntArray));

    PrintSortFunctionTestResult(
        GetSortFunctionTestResult("Insert sort", 
            length, 
            InsertSort, 
            GetInsertSortCounter, 
            GetBackSortedIntArray));

    PrintSortFunctionTestResult(
        GetSortFunctionTestResult("Selection sort", 
            length,
            SelectionSort,
            GetSelectionSortCounter,
            GetBackSortedIntArray));

    PrintSortFunctionTestResult(
        GetSortFunctionTestResult("Pyramidal sort",
        length,
        PyramidalSort,
        GetSelectionSortCounter,
        GetBackSortedIntArray));

    return 0;
}