What kind of sort is this?

I wrote this for an assignment a while back to sort an array of stucts I made, by weight and then alphabetically by name, was wondering what kind of sort this is?

void sortPR(stuct m *arr, int n_nodes) {
    for (int i = 0; i < n_nodes; i  ) {

        // Sort in descending order for weight
        for (int k = i   1; k < n_nodes; k  ) {

            // If weight equal, sort alphabetically
            if (arr[i].weight == arr[k].weight) {

                // Sort alphabetically
                if (strcmp(arr[i].name, arr[k].name) > 0) {
                    swap(&arr[i], &arr[k]);
                }
            } else if (arr[i].weight < arr[k].weight) {
                swap(&arr[i], &arr[k]);
            }
        }
    }
}

CodePudding user response：

It looks like the selection sort with redundant swappings of elements.

Usually for the selection sort only one swapping of elements is done after the inner for loop while the inner for loop only determines the index of the element with which the element with the index i will be swapped if it is required.

CodePudding user response：

sortPR performs a variation of Selection Sort with extra swapping to sort the array by decreasing weight with a secondary key on name, sorted in lexicographical order for identical weight.

The performance is quite bad, with a time complexity is O(N²) in all cases (unlike insertion sort), but for small arrays, this does not matter much and the implementation is straightforward, easy to get right. Quicksort on the contrary is complicated and easy to get wrong.

Furthermore, unlike bubble sort and insertion sort, selection sort does not guarantee stability, relative order of elements that compare identical is not preserved: B₁, B₂, A would sort as A, B₂, B₁. Your implementation behaves differently but has this defect too.

The lexicographical order is not exactly the same as alphabetic order: case will matter and the relative order of letters, digits and punctuation depends on the character set used in the system.

Here is a modified version, closer to the typical insertion sort, with fewer swaps:

void sortPR(stuct m *arr, int n_nodes) {
    for (int i = 0; i < n_nodes; i  ) {
        int i1 = k;

        // Sort in descending order for weight
        for (int k = i   1; k < n_nodes; k  ) {

            // If weight equal, sort alphabetically
            if (arr[i].weight == arr[k].weight) {

                // Sort alphabetically
                if (strcmp(arr[i].name, arr[k].name) > 0) {
                    i1 = k;
                }
            } else if (arr[i].weight < arr[k].weight) {
                i1 = k;
            }
        }
        if (i != i1) {
            swap(&arr[i], &arr[i1]);
        }
    }
}