CODEWITHSUNDEEP
algorithmsortingdata-structures
johnlacrosse
johnlacrosse

Reputation: 37

Deciding between a Priority Queue and Sorting Algorithm

I'm relatively new to data structures and algorithms (learning off YouTube as a highschool student), and I've come to a crossroads in thinking, for a project I am working on.

My project is to create software to make a test. I'm thinking of weighting the individual questions by difficulty, so when taking the test, the least difficult questions display first, and the most difficult last (through a min-heap). This in of itself would work, and would be efficient doing it. However, in my test program, a user might not want the next question. They may want to go back a question. Currently, this is solved by having an array of my Question class (java).

Question[] quizQuestions = {question1, question2, question3, ...}

To go to a question, the program gets the index of the question, and displays it. However, with a priority queue, I lose this functionality. I can think of several ways to avoid this, such as creating a array that stores the questions after the priority queue hands them to the user.

But to me, that begs the question. Would it be more effective to use a sorting algorithm instead, based on the Questions difficulty integer, to just have a single array? Knowing that the time complexity of the priority queue is faster than that of any sorting algorithm, I am leaning towards the queue. But being very new to this, I'd like some outside input.Thanks in advance.

Upvotes: 1

Views: 181

Answers (2)

David Eisenstat
David Eisenstat

Reputation: 65506

Matt has answered from a software engineering perspective. Algorithmically, the priority queue is O(n) time to set up, then O(log n) each time you pop the min element. If you pop all of the elements, you get an O(n log n)-time sorting algorithm called heapsort, which is asymptotically efficient but tends to be slower in practice than whatever sort method your programming environment provides. Honestly even quadratic time would be fine on any reasonably sized test, so I would just sort.

Upvotes: 0

Matt Timmermans
Matt Timmermans

Reputation: 59358

This would be a good time to learn about the "separation of concerns".

You absolutely want to sort the questions first, provide them to the quiz interface as a sorted list, and then have the quiz UI ask the questions in the order that they are provided.

This separates the concerns about question ordering from the concerns about the features of the quiz user interface, and lets you maintain and modify each of those independently. If you want to change the quiz ordering to something else, you can do that without worrying about all the quiz UI code, and if you want to change the quiz UI, you can do that without worrying about how the questions are ordered.

Upvotes: 1

Related Questions