C++ Pancake sort Exercise: Sort a collection of integers using the Pancake sort

Last update on December 20 2024 12:31:44 (UTC/GMT +8 hours)

Write a C++ program to sort a collection of integers using Pancake sort.

Sample Solution:

C++ Code :

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>

// Pancake sort template function that accepts a predicate to determine the order
template <typename BidIt, typename Pred>
void pancake_sort(BidIt first, BidIt last, Pred order) {
    // If the range has less than two elements, no sorting is needed
    if (std::distance(first, last) < 2)
        return;

    // Iterating through the range from beginning to end
    for (; first != last; --last) {
        // Finding the maximum element within the current unsorted range
        BidIt mid = std::max_element(first, last, order);
        // If the maximum element is already at the end, no flips are needed
        if (mid == last - 1) {
            continue;
        }
        // If the maximum element is not at the beginning, flip elements to move it to the front
        if (first != mid) {
            std::reverse(first, mid + 1);
        }
        // Flip elements to move the maximum element to its final sorted position
        std::reverse(first, last);
    }
}

// Pancake sort template function that defaults to ascending order
template <typename BidIt>
void pancake_sort(BidIt first, BidIt last) {
    // Calling the pancake_sort function with default ascending order
    pancake_sort(first, last, std::less<typename std::iterator_traits<BidIt>::value_type>());
}

// Main function
int main() {
    // Initializing a vector with integers for sorting
    std::vector<int> data = {125, 0, 695, 3, -256, -5, 214, 44, 55};

    // Displaying the original numbers in the vector
    std::cout << "Original numbers:\n";
    std::copy(data.begin(), data.end(), std::ostream_iterator<int>(std::cout, " "));
    std::cout << "\n";

    // Sorting the vector using ascending pancake sort
    pancake_sort(data.begin(), data.end());

    // Displaying the sorted numbers after pancake sort
    std::cout << "Sorted numbers:\n";
    std::copy(data.begin(), data.end(), std::ostream_iterator<int>(std::cout, " "));
    std::cout << "\n";

    return 0;
}

Sample Output:

Original numbers:
125 0 695 3 -256 -5 214 44 55 
Sorted numbers:
-256 -5 0 3 44 55 125 214 695

Flowchart:

C++ Code Editor:

Contribute your code and comments through Disqus.

Previous: Write a C++ program to sort a collection of integers using the Merge sort.
Next: Write a C++ program to sort a collection of integers using the Quick sort.