Bubble Sort In C ++

Question

Saya mempelajari C ++ modern dan juga algoritme, dan sedang berlatih dengan membuat kode beberapa algoritme sederhana. Juga mencoba menggunakan template bila memungkinkan karena saya cukup asing dengan pemrograman generik.

Butuh bantuan dalam meninjau kode dalam hal desain, efisiensi, keringkasan, dan gaya. Tolong jangan menahan dan merobek kode saya. Ini cara terbaik bagi saya untuk belajar :) terima kasih! Saya menggunakan MSVC, C ++ 17.

// version for contaners with random access
// move minima to correct position (sweep from right to left)
template<typename T>
void bubbleRandCppStl(T& container) {
    for (auto i{ container.rend() - 1 }; i != container.rbegin(); --i) {
        bool swapped {}; // flag to store if swap occured in sweep
        for (auto j{ container.rbegin() }; j != i; ++j) {
            if (*j < *(j + 1)) {
                std::iter_swap(j, j + 1);
                swapped = true;
            }
        }
        if (!swapped) { // end early if no swap occurred in sweep
            break;
        }
    }
}

// version for lists (std::list and std::forward_list)
// move maxima to correct position (sweep from left to right, because forward iterator is unidirectional)
template<typename T>
void bubbleListCppStl(T& container) {
    // container.size() takes O(n) time, so we just do a full sweep
    // and get the size at the same time
    typename T::size_type sz{};
    bool swapped{}; // flag to store if swap occured in sweep
    for (auto i{ container.begin() }, after_i{ ++container.begin() };
        after_i != container.end(); ++i, ++after_i) {
        ++sz;
        if (*i > * after_i) {
            std::iter_swap(i, after_i);
            swapped = true;
        }
    }
    if (!swapped) { // end early if no swap occurred in sweep
        return;
    }

    // decrement size as we now need to sort only sz - 1 elements
    --sz;

    // sort the remaining elements
    for (; sz > 1; --sz) {
        auto i{ container.begin() };
        for (auto elem_left{ sz }; elem_left > 1; --elem_left, ++i) {
            if (*i > * (std::next(i))) {
                std::iter_swap(i, std::next(i));
                swapped = true;
            }
        }
        if (!swapped) { // end early if no swap occurred in sweep
            break;
        }
    }
}

```

Answer 1

Selamat datang di Review Kode. Berikut beberapa saran:

• Alih-alih menggunakan wadah sebagai argumen, gunakan sepasang iterator untuk fleksibilitas.

• Sediakan satu fungsi yang digunakan iterator_categoryuntuk menemukan versi yang benar.

• Izinkan pengguna untuk menentukan pembanding khusus.

• Secara pribadi, menurut saya itu bool swapped{false};lebih jelas dari bool swapped{}.

• Pertukaran terus-menerus tampaknya kurang efisien daripada bergerak.

• Apakah Anda yakin perlu iterator terbalik di sini? Menelusuri dari kiri ke kanan saja sudah cukup.

• Menghitung std::next(i)dua kali tidak terasa efisien.