сортировка индексным массивом с++

320

19 ноября 2020, 09:50

Задача была написать тривиальную структуру и отсортировать ее в процентном соотношении по кол-ву поступивших в вуз учеников методом сортировки индексов. Я понимаю, что ошибка кроется в пользовательской функции сортировки по индексам (indexSort, я так полагаю). Но как бы я не пытался, безрезультатно.

#include <stdlib.h>
#include <stdio.h>
#include <iostream>
typedef struct
{
    char name[10];
    int vip;
    int vuz;
    float pr;
} school;
void IndexSort(school arr[], int n, int *B) //алгоритм сортировки через     массив индексов
{
    int i, j, t = 0;
    for (i = 0; i < n; i++)
    {
        B[i] = i;
    }
    for (i = 0; i < n - 1; i++)
    {
        for (j = i + 1; j < n; ++j)
        {
            if (arr[B[i]].pr < arr[B[j]].pr)
            {
                t = B[i];
                B[i] = B[j];
                B[j] = t;
            }
        }
    }
}
int main()
{
    int i, j, t, n;
    school S;
    std::cout << "Input amount of schools: ";
    std::cin >> n;
    std::cout << std::endl;
    school* arr = new school[n];
    int* B = new int[n];
    for (i = 0; i < n; i++)
    {
        std::cout << "Input school name: ";
        std::cin >> arr[i].name;
        std::cout << "Input amount of graduate school:";
        std::cin >> arr[i].vip;
        std::cout << "Input amount of already students:";
        std::cin >> arr[i].vuz;
        if (arr[i].vip < arr[i].vuz)
        {
            std::cout << "You did mistake, try again " << std::endl;
            break;
        }
}
for (i = 0; i < n; i++)
{
    arr[i].pr = ((float)arr[i].vip / 100 * (float)arr[i].vuz);
}
IndexSort(arr, n, B);
for (i = 0; i < n; i++)
{
    std::cout << arr[B[i]].name << "  " << std::endl;
    std::cout << arr[B[i]].pr << "  " << std::endl;
}
return 0;
}

Answer 1

Если считать, что ваша индексная сортировка пузырьком работает, то её результатом должен быть массив индексов B[], отсортированный так, что на нулевом месте в нём стоит индекс записи с наименьшим pr и так далее.

Однако при выводе массив B[] вовсе не используется. Вероятно, вывод должен выглядеть так:

for (i = 0; i < n; i++)  {
    int k = B[i];
    cout << arr[k].name << "  " << arr[k].vip << "  " << arr[k].vuz << "  ";
}
или без введения новой переменной
arr[B[i]].name и т.п.

Здесь используется один и тот же неинициализированный экземпляр S, присваиваемый всем элементам массива:

    for(i = 0; i < n; i++)
    {
        S.pr = ((float)S.vip/(float)S.vuz)*100;
        arr[i] = S;
    }

Привёл код к рабочему состоянию:

#include "pch.h"
#include <iostream>
typedef struct
{
    char name[10];
    int vip;
    int vuz;
    float pr;
} school;
void IndexSort(school arr[], int n, int *B)
{
    int i, j, t = 0;
    for (i = 0; i < n; i++)
    {
        B[i] = i;
    }
    for (i = 0; i < n - 1; i++)
    {
        for (j = i + 1; j < n; ++j)
        {
            if (arr[B[i]].pr < arr[B[j]].pr)
            {
                t = B[i];
                B[i] = B[j];
                B[j] = t;
            }
        }
    }
}
int main()
{
    int i, j, t, n;
    school S;
    std::cout << "Input amount of schools: ";
    std::cin >> n;
    std::cout << std::endl;
    school* arr = new school[n];
    int* B = new int[n];
    for (i = 0; i < n; i++)
    {
        std::cout << "Input school name: ";
        std::cin >> arr[i].name;
        std::cout << "Input amount of graduate school:";
        std::cin >> arr[i].vip;
        std::cout << "Input amount of already students:";
        std::cin >> arr[i].vuz;
        if (arr[i].vip < arr[i].vuz)
        {
            std::cout << "You did mistake, try again " << std::endl;
            break;
        }
    }
    for (i = 0; i < n; i++)
    {
        arr[i].pr = ((float)arr[i].vip / (float)arr[i].vuz) * 100;
    }
    IndexSort(arr, n, B);
    for (i = 0; i < n; i++)
        std::cout << arr[B[i]].name << "  " << arr[B[i]].vip << "  " << arr[B[i]].pr << "  ";
    return 0;
}

Answer 2

Сортировка массива индексов должна осуществлять доступ к исходному массиву именно и только через массив индексов
```
 ...
 if (arr[B[i]].pr < arr[B[j]].pr)
 {
   t=B[i];
   B[i]=B[j];
   B[j]=t;
 }
 ...
```
Непонятно, почему память под основные данные выделена через new [], а память под массив индексов якобы "выделена напрямую": int B[n];. К тому же n в этот момент у вас вообще не инициализировано. Что вы хотели сказать этим int B[n];, если в n содержится "мусор"?

В любом случае, если n не является константой, то либо new [], либо std::vector. Никакого int B[n]; в С++ не допускается.
Как уже правильно заметил @MBo, зачем вы сортировали свой массив индексов, если потом вы его вообще не используете?