# Is there a well-known algorithm for arranging inputs according to their category?

Background:

(I’m a complete beginner in computer science in general, so I do apologise if my question is not formulated in a sensible way. E.g. I have avoided technicalities in formulating my problem, but perhaps this causes issues. I'm willing to edit accordingly if so).

I’m trying to get to grips with the way that algorithms are/can be used in economics. I think I understand the (very) basics of how sorting algorithms and clustering algorithms could apply to some problems, but there is a (seemingly) elementary problem which I can’t find a well-known algorithm for.

The problem:

Suppose my entire input consists of a set of different quantities of two types of good. For example, apples and oranges:

Input: { 1 apple, 1 orange, 10 apples, 10 oranges }

Is there a well-known algorithm which can arrange these inputs by type of good, such that the output is the following two sets?:

Set 1 (apples): { 1 apple, 10 apples }

Set 2 (oranges): { 1 orange, 10 oranges }

Clustering and sorting algorithms do not seem to be appropriate:

From my (very, very basic) knowledge of clustering algorithms, they would not be appropriate here, as clusters are meant to represent closeness of data points in space. But, if I were to plot these goods as data points, I would have a representation of their values, whereas I'm trying to group them via their categories.

I also don’t think that a comparison based sorting algorithm would work, as these algorithms produce an ordering (total preorder) of the values input. Whereas, again, I'm trying to group them via their categories.

Is my definition of algorithm the issue?

Perhaps I'm misunderstanding the type of thing that can be input into an algorithm? Cormen et al. (Introduction to Algorithms, 2009, §1.1) informally define an algorithm as

...any well-defined computational procedure that takes some value, or set of values, as input and produces some value, or set of values, as output.

So perhaps an algorithm can only take numerical values as an input and not numerical values attached to a category label (like 'apple', or 'orange')?

I’d be very grateful for any help :)

• If you care about listing the output for apples in increasing order (like $\{1,10\}$ rather than $\{10,1\}$) then sorting can be used; assign "apples: 1" and "oranges: 2" then represent your data as ordered pairs where the fruit's code is the first coordinate and the quantity is the second: (1,1), (2,1), (1,10), (2,10). Then after you sort you can bunch things together – Matthew C Dec 1 '19 at 23:29
• If you don't care about the ordering within a fruit, then you could still do the above, but a faster algorithm is as follows (just replace color by fruit) medium.com/@interviewprep/… which has running time linear in the input with constant equal to the number of different fruits – Matthew C Dec 1 '19 at 23:31
• The last algorithm (dutch national flag sort) I should point out is well-known; it puts things of the same category together and also preserves the order that they were originally – Matthew C Dec 1 '19 at 23:33

An algorithm can be seen as the steps needed to go from a well defined type of input to some well defined output. The input can therefore be everything that one can represent within a computer.

In the algorithm you are asking for it seems like the input has already been classified as specific good as in apples are already classified as apples, had it not been defined one could use clustering to find out what separates the types of goods from each other depending on the data of each entry of a good in the database. That means that clustering is a way of data mining.

One way of solving your problem could use sorting like this:

1: def separate_goods(List S):
2:    sort S on the type of good
3:    A := a list
4:    B := a list
5:    current_type := S.type
7:    i := 1
8:    while(i < length(S)){
9:       if(current_type == S[i].type):
11:          i := i + 1
12:      else:
14:          B := a new list
16:          current_type := S[i].type
17:          i := i + 1
18:   }