[c++] Wyniki i pozycja w rankingu

[m12345]

Hej, mam problem ze swoim programem, ma on złożoność kwadratową, a chciałabym uzyskać \(\displaystyle{ O(n)}\) czy \(\displaystyle{ O(n \log n)}\). Starałam się przekształcić kod, lecz nie wiem jak pozbyć się pętli w pętli(41-50). Jakieś podpowiedzi?
Wklejam kod:

Kod: Zaznacz cały

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
//sortowanie
void sort(int wyniki[], int n)
{
	for (int i = 0; i < n; i++)
	{
		vector<int> indeks(n, 0);

		for (int i = 0; i < n; i++)
		{
			indeks[i] = i + 1;
		}
		sort(indeks.begin(), indeks.end(),
			[&](const int& a, const int& b)
		{
			return (wyniki[a] > wyniki[b]);
		}
		);
	}
}

int main(int argc, char* argv[])
{
	int n = 0;
	cin >> n;//iczba uczestników

	int* wyniki = new int[n];
	int* rank = new int[n];

	for (int i = 0; i < n; i++)
	{
		cin >> wyniki[i];//wyniki zawodników
	}

	sort(wyniki, n);

	//rank
	for (int i = 0; i < n; i++)
	{
		int rnk = 1;
		for (int j = 0; j < n; j++)
		{
			if (wyniki[j] > wyniki[i])//sprawdzam które wartości są mniejsze od danej wartosci
				rnk++;
		}
		rank[i] = rnk;
	}

	//ranking
	for (int i = 0; i < n; i++)
	{
		cout << rank[i] << " ";
	}

	delete[] wyniki;
	delete[] rank;

	return 0;
}

[qwertghjio]

Możesz zastosować sortowanie przez zliczanie lub quicksort.

[Afish]

Skoro wyniki masz posortowane, to możesz wyszukiwać binarnie ostatni element o tej samej wartości. Możesz też przeiterować raz i gdy wartość elementu ulega zmianie, to zmienia się też ranking.

Jeżeli ten program miał wypisać pozycję każdego zawodnika, to nie zadziała, bo sortujesz wyniki.