Algorithm for sorting within windows

Question

I am writing an app which displays speeches on various topics, with each speech having a number of attributes. I want to give the user the choice to sort a list of speeches by an attribute, even within a previously sorted list of speeches.

Consider for example: Suppose the previous list had been sorted by the attribute: "speaker's name", and there were three different speakers (so the list was split into three windows with each window consisting of the same speaker). Now, the user wants to sort the speeches based on the attribute: "length of the speech" such that the new list would now be sorted by speaker's name, and within each window of the speaker's name, the speeches would be sorted by the length (creating a new window within this window for each length of speech in the speaker's window).

I would like to give the user the ability to do this with an arbitrary number of attributes. How can I go about doing such sorting, preferably in the most efficient way?

P.S: I am just a teenage programmer who has been programming for a few years and can understand algorithms in concrete steps - I have not taken college classes in CS, so please keep that in mind when explaining the algorithms.

Answer 1

What you require is the lexicographic ordering. Let me describe this.

Suppose the speeches have two attributes. The first one is "speaker's name" and the second one is the "length". For simplification, let me define the speaker's name by the integer value instead of a character string. Now, suppose the speeches are represented using the following tuples: $(0,0)$, $(1,2)$, $(0,3)$, $(1,4)$, $(2,3)$, $(2,4)$, and $(1,1)$. Here, the second speech has the speaker's name: $1$, and length $= 2$.

Requirement 1: You simply want to sort the speeches by the "speaker's name".

Just consider the first attribute for comparing any two speeches and apply any sorting algorithm. You will get the following ordering: $(0,0)$, $(0,3)$, $(1,2)$, $(1,4)$, $(1,1)$, $(2,3)$, and $(2,4)$.

Requirement 2: You want to sort first by the "speaker's name" and then by the "length". This is the requirement that you have mentioned in your question.

Now, define a new comparison operation between two tuples as follows: $(a,b) < (c,d)$ if and only if $(a<c)$ or $(a = c$ and $b<d)$ Here, we are comparing by giving the "first attribute" more priority. And if the first attribute value is the same, we compare based on the "second attribute".

Smilarly, you can define $(a,b) > (c,d)$ if and only if ($a>c$) or ($a = c$ and $b>d$).

Now, you can simply use any sorting algorithm by replacing the standard comparison operation with the above-defined comparison operation.

You will get the following ordering: $(0,0)$, $(0,3)$, $(1,1)$, $(1,2)$, $(1,4)$, $(2,3)$, and $(2,4)$.

Requirement 3: Suppose, you want to sort by the length and then by the speaker's name

Simply, define the comparison operation between two tuples as: $(a,b) < (c,d)$ if and only if $(b<d)$ or $(b = d$ and $a<c)$. Now, again you can use any standard sorting algorithm by replacing the standard comparison operation with this comparison operation.

You will get the following ordering: $(0,0)$, $(1,1)$, $(1,2)$, $(0,3)$, $(2,3)$, $(1,4)$, and $(2,4)$.

---

Similarly, you can define a new comparison operation for the multiple attributes based on your requirements.