Bubble sort C/C++

Poměrně jednoduchý a rychlý (pro malé hodnoty) algoritmus, nenáročný na naprogramování. Pro větší hodnoty se nedoporučuje, jeho náročnost je přeci jen Ο(n2). Vzorový kód obsahuje i tělo main() se vzorovými daty.

Bouble sort v C

Jednoduchý bouble sort v C, včetně funkce main.

#include <stdio.h>
#define DATA_SIZE 20

void swap(int *a, int *b)
{
    int tmp;
    tmp = *a;
    *a = *b;
    *b = tmp;
}

void bouble_sort(int data[DATA_SIZE])
{
    int i, j;
    for (i = 0; i < DATA_SIZE; i++)
        for (j = 0; j < DATA_SIZE - 1; j++)
            if (data[j] > data[j + 1])
            {
                swap(data + j, data + j + 1);
            }
}

int main(int argc, const char * argv[])
{

    int data[20] = { 12, 4, 6, 43, 68, 35, 79, 3, 11, 18,
                   26, 21, 2, 88, 34, 13, 90, 57, 77, 19 };
    int i;

    for (i = 0; i < DATA_SIZE; i++)
        printf("%02d | ", data[i]);
    printf("\n");

    bouble_sort(data);

    for (i = 0; i < DATA_SIZE; i++)
        printf("%02d | ", data[i]);
    printf("\n");

    return 0;
}

Bouble sort v C++

Jak je mým zvykem, algoritmy v C++ se snažím psát jako šablony

#include <iostream>
#include <vector>
#include <iomanip>

#define DATATYPE int

using std::vector;
using std::cout;
using std::endl;

template <typename T>
void swap(std::vector<T> *data, int a, int b)
{
    T tmp;
    tmp = data->at(a);
    data->at(a) = data->at(b);
    data->at(b) = tmp;
}

template <typename T>
void quick_sort(std::vector<T> *data, int start, int end)
{
    int pivot, startIndex, endIndex;
    if (start >= end)
        return;

    pivot = start;
    startIndex = start + 1;
    endIndex = end;

    while (startIndex < endIndex)
    {
        if (data->at(pivot) >= data->at(startIndex))
            startIndex++;
        else
            swap(data, startIndex, endIndex--);
    }

    if (pivot + 1 == startIndex)
    {
        if (data->at(pivot) > data->at(startIndex))
        {
            swap(data, pivot, startIndex);
        }
    }
    else
    {
        if (data->at(pivot) < data->at(startIndex))
            startIndex--;
        swap(data, pivot, startIndex);
    }

    pivot = startIndex;

    quick_sort(data, start, pivot - 1);
    quick_sort(data, pivot + 1, end);
}

int main(int argc, const char * argv[])
{
    DATATYPE dataSource[20] = { 12, 4, 6, 43, 68, 35, 79, 3, 11, 18,
        26, 21, 2, 88, 34, 13, 90, 57, 77, 19 };

    vector<DATATYPE> data(dataSource, dataSource + sizeof(dataSource)/sizeof(DATATYPE));

    for (vector<DATATYPE>::iterator idx = data.begin(); idx < data.end(); idx++)
        cout << "" << std::setfill('0') << std::setw(2) << *idx;
    cout << endl;

    quick_sort<DATATYPE>(&data, 0, (int)data.size() - 1);

    for (vector<DATATYPE>::iterator idx = data.begin(); idx < data.end(); idx++)
        cout << "" << std::setfill('0') << std::setw(2) << *idx;

    return 0;
}
Příspěvek byl publikován v rubrice Programování se štítky , , . Můžete si uložit jeho odkaz mezi své oblíbené záložky.