C int array sort

Question

If I have an int[3] array like such:

score_list[3] = [ 1, 2, 0]

Where each location in the array corresponds to a specific Document Number:

score_list[0] = D1
score_list[1] = D2
score_list[2] = D3

What would be the easiest way to sort the array in Descending order, keeping track of the place of each moved int

Where (after sort):

score_list[3] = [ 2, 1, 0]

And

score_list[0] = D2
score_list[1] = D1
score_list[2] = D3 

I only need to print in descending order, not actually rearrange the int array, so:

for (int i=0; i<3; i++)
{
    if (score_list[0] > score_list[1] && score_list[2])
        printf("D%d-%d",i, score_list[0]);
    if (score_list[1] > score_list[0] && score_list[2])
        printf("D%d-%d", i, score_list[1]);
    if (score_list[2] > score_list[0] && score_list[1])
        printf("D%d-%d", i, score_list[2]);
}

Would print the highest number first, then I would compare the last 2, I just feel like this takes too long and there must be a more efficient way

Answer 1

You can solve this using marker (interface) design pattern.
By keeping a record of the visited index in your array each time you get the max, let me define the solution structure first then I will walk through it:

1. Make a new array of the same size of the score_list, let's call that array marker
2. In the for loop, you will make another loop to check for max score and in the same time check to see if the location of the max score in the marker array is 0.

Sample run:
On i=0
Loop on the score_list, and find the max score with marker == 0, print it and then put marker for that score = 1.
On i=1
You will do the same but now there is one location excluded from the list

Here you are a sample code how to do it:
Note that: this code is not a runnable one (and it is not optimized too O(n^2)), I wrote it for explanation purposes only.

int max = -1;
int doc = -1; 
int marker[3] = {0, 0, 0};
for (i=0; i<3; i++)
{
    max = -1;
    for (j=0; j<3; j++)
    {
        // skip this location if it is already printed
        if (marker[j] == 1)
            continue;

        if (score_list[j] > max)
        {
            doc = j;
            max = score_list[j];
        }   
    }

    // this doc will not appear again in the inner for loop (j-loop)
    marker[doc] = 1;

    // print the document with the score
    printf("D%d-%d",doc, max);
}