Как добавить количество обменов в сортировке пузырьком?

Question

У меня есть реализованный алгоритм сортировки пузырьком. Как можно добавить количество обменов одного элемента на каждой итерации? Поясню, например: Массив: 9 2 3 4 0 2 6 Начинаем сортировку:

2 3 4 0 2 6 | 9 Вот, в данном случае девятка прошла 6 позиций
2 3 0 2 4 | 6 9 Теперь четвёрка прошла 2 позиции

Код:

#include <iostream>
using namespace std;


void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
        cout << "Step " << i + 1 << " ";
        for (int k = 0; k < n; k++) {
            cout << arr[k] << " ";
        }
        cout << endl;
    }
}

int main() {
    int sizeOfArray;
    cout << "Enter a count of array's elements: ";
    cin >> sizeOfArray;
    int* arr = new int[sizeOfArray];
    cout << "Enter elements of array: ";
    for (int i = 0; i < sizeOfArray; i++) {
        cin >> arr[i];
    }
    bubbleSort(arr, sizeOfArray);
    cout << "Sorted array: ";
    for (int i = 0; i < sizeOfArray; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    delete[] arr; // clean memory
    return 0;
}

Answer 1

// -------------- //
// - typing.hpp - //
// -------------- //

#ifndef __TYPING_HPP__
#define __TYPING_HPP__

#include <map>
#include <vector>
#include <utility>

using CountPairVec = std::vector<std::pair<int, std::size_t>>;

using MapOtpType = std::map<int, int>;
using VecOtpType = std::vector<CountPairVec>;

#endif

// ------------------ //
// - BubbleSort.hpp - //
// ------------------ //

#ifndef __BUBBLE_SORT_HPP__
#define __BUBBLE_SORT_HPP__

#include "typing.hpp"

void bubbleSort(int*, int*);
void bubbleSort(int*, int*, VecOtpType&);
void bubbleSort(int*, int*, MapOtpType&);

#endif

// ------------------ //
// - BubbleSort.cpp - //
// ------------------ //

#include "BubbleSort.hpp"

void bubbleSort(int* beg, int* end) {
    int temp;
    for (int* stop = end - 1; stop > beg; --stop)
        for (int* it = beg; it < stop; ++it) 
            if (*it > *(it + 1)) {
                temp = *it;
                *it = *(it + 1);
                *(it + 1) = temp;
            }
}

void bubbleSort(int* beg, int* end, VecOtpType& shift) {
    int temp;
    shift.clear();

    bool key = 0;
    std::size_t count = 0;
    auto pushPair = [&shift, &count, &key](int val) -> void {
        shift.back().push_back(std::make_pair(val, count));
        count = 0;
        key = false;
    };

    for (int *it, *stop = end - 1; stop > beg; --stop) {
        shift.push_back(CountPairVec());
        for (it = beg; it < stop; ++it) 
            if (*it > *(it + 1)) {
                ++count;
                key = true;

                temp = *it;
                *it = *(it + 1);
                *(it + 1) = temp;
            } else if(key) { (void) pushPair(*it); }
        if(key) { (void) pushPair(*it); }
        if(shift.back().empty()) { shift.pop_back(); }
    }
}

void bubbleSort(int* beg, int* end, MapOtpType& shift) {
    int temp;
    std::map<int, std::pair<std::size_t, int>> res; 
    for(int* it = beg; it < end; ++it) { ++res[*it].first; }

    for (int* stop = end - 1; stop > beg; --stop)
        for (int* it = beg; it < stop; ++it) 
            if (*it > *(it + 1)) {
                ++res[*it].second;
                --res[*(it + 1)].second;

                temp = *it;
                *it = *(it + 1);
                *(it + 1) = temp;
            }
    
    for(const auto& it: res) {
        shift[it.first] = it.second.second / it.second.first;
    }
}

// ---------- //
// - IO.hpp - //
// ---------- //

#ifndef __IO_HPP__
#define __IO_HPP__

#include <iostream>
#include "typing.hpp"

int* scan(size_t&);

template<typename T> char print(const T&);
template<typename T> char print(const std::vector<T>&);
template<typename T1, typename T2> char print(const std::map<T1, T2>&);
template<typename T1, typename T2> char print(const std::pair<T1, T2>&);
template<typename IterableObject> char print(IterableObject, IterableObject);

template<typename T>
char print(const T& val) {
    std::cout << val;
    return '\0';
}

template<typename T>
char print(const std::vector<T>& vec) {
    return print(vec.begin(), vec.end());
}

template<typename T1, typename T2>
char print(const std::map<T1, T2>& mp) {
    return print(mp.begin(), mp.end());
}

template<typename T1, typename T2>
char print(const std::pair<T1, T2>& pair_) {
    std::cout << '{';
    std::cout << "val: " << pair_.first;
    std::cout << ", ";
    std::cout << "shift: " << pair_.second;
    std::cout << '}';
    return '\0';
}

template<typename IterableObject>
char print(IterableObject beg, IterableObject end) {
    std::cout << '[';
    if(beg != end) {
        (void) print(*beg);
        for(auto it = ++beg; it != end; ++it)
            std::cout << ", " << print(*it);
    }
    std::cout << ']';
    return '\0';
}

#endif

// ---------- //
// - IO.cpp - //
// ---------- //

#include "IO.hpp"

int* scan(std::size_t& len) {
    int n;
    int* arr;

    std::cout << "Enter the number of elements in the array: ";
    if(!(std::cin >> n) || n <= 0) { throw std::invalid_argument("len must be a positive integer!"); }

    len = n;
    arr = new int[len];

    std::cout << "Enter the array: ";
    for(std::size_t i = 0; i < len; ++i)
        if(!(std::cin >> arr[i])) { throw std::invalid_argument("every array element must be integer!"); }
    return arr;
}

// ------------ //
// - main.cpp - //
// ------------ //

#include "IO.hpp"
#include "BubbleSort.hpp"

int* copy(const int* arr, std::size_t len) {
    int* new_arr = new int[len];
    for(std::size_t i = 0; i < len; ++i) { new_arr[i] = arr[i]; }
    return new_arr;
}

void ver1(int* arr, std::size_t len) {
    (void) bubbleSort(arr, arr + len);

    std::cout << "version 1:\n";
    std::cout << "---> Sorted array: " << print(arr, arr + len) << '\n';
    delete[] arr;
}

void ver2(int* arr, std::size_t len) {
    MapOtpType shift;

    (void) bubbleSort(arr, arr + len, shift);

    std::cout << "version 2:\n";
    std::cout << "---> Sorted array: " << print(arr, arr + len) << '\n';
    std::cout << "---> Shift: " << print(shift) << '\n';
    delete[] arr;
}

void ver3(int* arr, std::size_t len) {
    VecOtpType shift;

    (void) bubbleSort(arr, arr + len, shift);

    std::cout << "version 3:\n";
    std::cout << "---> Sorted array: " << print(arr, arr + len) << '\n';
    std::cout << "---> Shift: " << print(shift);
    delete[] arr;
}

int main() {
    int* arr;
    std::size_t len;

    arr = scan(len);
    std::cout << "Initial array: " << print(arr, arr + len) << "\n\n";

    (void) ver1(copy(arr, len), len);
    std::cout << '\n';

    (void) ver2(copy(arr, len), len);
    std::cout << '\n';

    (void) ver3(copy(arr, len), len);

    delete[] arr;
    return 0;
}

Вывод 1:

Enter the number of elements in the array: 7
Enter the array: 9 2 3 4 0 2 6
Initial array: [9, 2, 3, 4, 0, 2, 6]

version 1:
---> Sorted array: [0, 2, 2, 3, 4, 6, 9]

version 2:
---> Sorted array: [0, 2, 2, 3, 4, 6, 9]
---> Shift: [{val: 0, shift: -4}, {val: 2, shift: -2}, {val: 3, shift: 1}, {val: 4, shift: 1}, {val: 6, shift: -1}, {val: 9, shift: 6}]

version 3:
---> Sorted array: [0, 2, 2, 3, 4, 6, 9]
---> Shift: [[{val: 9, shift: 6}], [{val: 4, shift: 2}], [{val: 3, shift: 2}], [{val: 2, shift: 1}]]

Вывод 2:

Enter the number of elements in the array: 8
Enter the array: 5 2 2 2 10 1 9 9
Initial array: [5, 2, 2, 2, 10, 1, 9, 9]

version 1:
---> Sorted array: [1, 2, 2, 2, 5, 9, 9, 10]

version 2:
---> Sorted array: [1, 2, 2, 2, 5, 9, 9, 10]
---> Shift: [{val: 1, shift: -5}, {val: 2, shift: 0}, {val: 5, shift: 4}, {val: 9, shift: -1}, {val: 10, shift: 3}]

version 3:
---> Sorted array: [1, 2, 2, 2, 5, 9, 9, 10]
---> Shift: [[{val: 5, shift: 3}, {val: 10, shift: 3}], [{val: 5, shift: 1}], [{val: 2, shift: 1}], [{val: 2, shift: 1}], [{val: 2, shift: 1}]]

Вывод 3:

Enter the number of elements in the array: 6
Enter the array: 56 7 -8 0 -10 -100
Initial array: [56, 7, -8, 0, -10, -100]

version 1:
---> Sorted array: [-100, -10, -8, 0, 7, 56]

version 2:
---> Sorted array: [-100, -10, -8, 0, 7, 56]
---> Shift: [{val: -100, shift: -5}, {val: -10, shift: -3}, {val: -8, shift: 0}, {val: 0, shift: 0}, {val: 7, shift: 3}, {val: 56, shift: 5}]

version 3:
---> Sorted array: [-100, -10, -8, 0, 7, 56]
---> Shift: [[{val: 56, shift: 5}], [{val: 7, shift: 4}], [{val: 0, shift: 2}], [{val: -8, shift: 2}], [{val: -10, shift: 1}]]

Вывод 4:

Enter the number of elements in the array: 6
Enter the array: 56 56 7 -8 -100 -100
Initial array: [56, 56, 7, -8, -100, -100]

version 1:
---> Sorted array: [-100, -100, -8, 7, 56, 56]

version 2:
---> Sorted array: [-100, -100, -8, 7, 56, 56]
---> Shift: [{val: -100, shift: -4}, {val: -8, shift: -1}, {val: 7, shift: 1}, {val: 56, shift: 4}]

version 3:
---> Sorted array: [-100, -100, -8, 7, 56, 56]
---> Shift: [[{val: 56, shift: 4}], [{val: 56, shift: 4}], [{val: 7, shift: 3}], [{val: -8, shift: 2}]]

Вывод 5:

Enter the number of elements in the array: 3
Enter the array: 5 5 5
Initial array: [5, 5, 5]

version 1:
---> Sorted array: [5, 5, 5]

version 2:
---> Sorted array: [5, 5, 5]
---> Shift: [{val: 5, shift: 0}]

version 3:
---> Sorted array: [5, 5, 5]
---> Shift: []

БЛОГ НА HUSL

Как добавить количество обменов в сортировке пузырьком?

Ответы (1 шт):