2
\$\begingroup\$

I am a beginner programmer and have written a program that sorts a number of integers of your choosing using bogo sort.

Are there any improvements that could be made to make this code more efficient (ironic, but you get the idea)? Are there any ways to make this code easier to read for someone else?

#include <iostream>
#include <time.h>

using namespace std;

int findModulus(int quotient, int divisor);

int main()
{
    cout << "Hello, welcome to the Bogo Sort Algorithm!" << endl;

    srand(time(NULL));

    //First sections establishes the dimensions of the matrices

    int entryNum ;

    cout << "Number of values: ";
    cin >> entryNum;

    int seq[entryNum];
    int plchlderSeq[entryNum];
    bool seqIsSorted;
    int chosenOrder[entryNum];
    int chosenOrderPreOp[entryNum];
    int numbers[entryNum];
    int i,j,k;

    cout << "Input the values: ";
    for(i=1; i<=entryNum; i++){
        cin >> seq[i-1];
    }

    do{
        seqIsSorted = true;

        for(i=1; i<=entryNum; i++){
            numbers[i-1] = i ;
        }
        
        //this section is for randomising the order of (1, ... , entryNum), remove comments to see it in action
        for(i=1; i<=entryNum; i++){
            chosenOrderPreOp[i-1] = findModulus(rand(),entryNum-i+1);
            //cout << chosenOrderPreOp[i-1] << "\n";
            chosenOrder[i-1] = numbers[chosenOrderPreOp[i-1]];
            //cout << chosenOrder[i-1] << "\n";
            for(j = chosenOrderPreOp[i-1]+1 ; j <= entryNum-i ; j++){
                numbers[j-1] = numbers[j]; // copy next element left
                for(k=1; k<=entryNum; k++){
                    //cout << numbers[k-1] << " ";
                }
                //cout << " \n";
            }
            /*
            for(j=1; j<=entryNum-i; j++){
                cout << numbers[j-1] << " ";
            }*/
            //cout << " \n";
        }
        for(i=1; i<=entryNum; i++){
            //cout << chosenOrder[i-1] << " ";
        }
        //cout << "\n";

        for(i=1; i<=entryNum; i++){
            plchlderSeq[i-1] = seq[chosenOrder[i-1]-1];
        }
        for(i=1; i<=entryNum; i++){
            seq[i-1] = plchlderSeq[i-1];
        }

        for(i=1; i<=entryNum-1; i++){
            if(seq[i-1] > seq[i]){
                seqIsSorted = false;
            }
        }
        for(i=1; i<=entryNum; i++){
            //cout << seq[i-1] << " ";
        }
        if(seqIsSorted){
            cout << "\nSequence is sorted \n";
            for(i=1; i<=entryNum; i++){
                cout << seq[i-1] << " ";
            }
        } else{
            //cout << "\nSequence is not sorted \n";
        }
    }while(!seqIsSorted);

    return 0;
}

int findModulus(int quotient, int divisor){
    int result;
    do{
        result = quotient;
        quotient = quotient-divisor;
    }while(quotient >= 0);
    return result;
}
\$\endgroup\$
5
  • 2
    \$\begingroup\$ Please add a language tag to the question. You can do this by clicking the edit link at the bottom. It appears to be C++, but it would be better if you would tag it. \$\endgroup\$
    – pacmaninbw
    Jun 17 at 22:02
  • \$\begingroup\$ int seq[entryNum]; with non constexpr entryNum is not valid c++ (that use VLA extension). use std::vector instead. \$\endgroup\$
    – Jarod42
    Jun 17 at 23:47
  • 2
    \$\begingroup\$ bogosort can simply use std::shuffle and std::is_sorted. \$\endgroup\$
    – Jarod42
    Jun 17 at 23:53
  • 1
    \$\begingroup\$ Instead of commenting debugging code (I include resulting empty loop), you might remove it completely. \$\endgroup\$
    – Jarod42
    Jun 17 at 23:57
  • \$\begingroup\$ (@Jarod42: Imagine a language specifying a comment format for comments to optionally not be shown in "code viewers". And suggesting an analogous option for asserts.) \$\endgroup\$
    – greybeard
    Jun 19 at 4:03

2 Answers 2

1
\$\begingroup\$

Advice 1

int seq[entryNum];

That did not compile on Visual Studio 2022 to begin with. Use:

#include <cstdlib>
#include <vector>
...
std::size_t seqLength;
std::cin >> seqLength;
std::vector<int> seq(seqLength);

Advice 2

using namespace std;

Please don't do it. Not just you import a lot of stuff to your program, but also abuse the compiler.

Advice 3

cout << "Input the values: ";
for (i = 1; i <= entryNum; i++) {
    cin >> seq[i - 1];
}

Can be rewriten as:

std::cout << "Input the values:\n";

for (std::size_t i = 0; i < seqLength; i++) {
    std::cin >> seq[i];
}

Advice 4

I would not specifically randomize the input sequence, since you always can input whatever you want to seq.

Advice 5

As noted in comments, you can use std::shuffle and std::is_sorted for your bogosort.

Alternative implementation (C++20)


#include <algorithm>
#include <chrono>
#include <functional>
#include <iostream>
#include <iterator>
#include <random>
#include <vector>

template<class RandomIt, class Cmp = std::less<>>
void bogosort(RandomIt first, RandomIt last, Cmp cmp = Cmp()) {
    unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
    auto prng = std::default_random_engine(seed);

    while (!std::is_sorted(first, last, cmp)) {
        std::shuffle(first, last, prng);
    }
}

int main()
{
    size_t seqLength;

    std::cout << "Number of values: ";
    std::cin >> seqLength;

    std::vector<int> seq(seqLength);

    std::cout << "Input the values:\n";

    for (std::size_t i = 0; i < seqLength; i++) {
        std::cin >> seq[i];
    }

    bogosort(seq.begin(), seq.end());

    std::copy(seq.begin(), 
              seq.end(), 
              std::ostream_iterator<int>(std::cout, " "));

    return 0;
}
\$\endgroup\$
1
\$\begingroup\$

any ways to make this code easier to read for someone else?
One important question to ask, especially where someone else includes a later self (maintenance).

  • Naming
    It isn't hard to guess from looking the names and the code what findModulus(int quotient, int divisor) returns. One needs to guess because there is nothing explicitly documenting what findModulus() is there for.
    There is a bit of doubt due to the first parameter being called quotient instead or numerator.
    result is non-telling - call it remainder or modulus. (It isn't quite as bad in a named function - "Algol family" languages use the procedure name here. Then, there are anonymous functions…)
  • What does the code section
          for(i=1; i<=entryNum; i++){
              plchlderSeq[i-1] = seq[chosenOrder[i-1]-1];
          }
          for(i=1; i<=entryNum; i++){
              seq[i-1] = plchlderSeq[i-1];
          }
    
    achieve? (One problem here: plchlderSeq doesn't ring any bell with me.)
    → Put all your business logic in named procedures.
  • define/declare "things" where you need them. Where handling seqIsSorted, I have forgotten that it is set at the top of the loop.
    (But follow coderodde's advice 5 about is_sorted(), anyway.)
  • The statements controlled by if(seqIsSorted) could just follow the loop.
  • There are two to three open coded loops to insert "all values" in cout:
    Don't repeat yourself, define a function.
  • for- and while-loops read easier than do … while for "disclosing" the (main) termination condition upfront.

Watch out for long procedures (and specifications):
Where a procedure's code is too long to remember the start when reaching the end (doesn't fit the screen/one sheet of paper), parts should be split out.
Where the summary of what a procedure is to achieve can't be stated in a simple sentence, chances are it is doing more than one thing:
A design improvement may be due

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.