Uporządkuj tablicę wielu powtarzających się elementów, tak aby zgromadzić te same elementy zachowując kolejność ich pierwszego wystąpienia

Potrzebuję pomocy, bo nie wiem jak się za to zabrać, wiem już, że sortowanie odpada.
Przykład
Wejście: [ 5, 4, 5, 5, 3, 1, 2, 2, 4 ]
Wyjście: [ 5, 5, 5, 4, 4, 3, 1, 2, 2 ]

Jak najbardziej należy posortować. Jak inaczej chcesz to osiągnąć, skoro efektem jest posortowana tablica? Z definicji, algorytm, którego efektem jest posortowany ciąg jest algorytmem sortowania.

Przykład sprzed kilku dni:

• zapamiętaj pierwsze wystąpienia
• posortuj wg nich

// dla tablicy typu T nazwanej array
std::map<T, size_t> first_seen;
size_t idx{};
for(auto const& element : array) {
    first_seen.insert({element, idx++});
}

std::sort(std::begin(array), std::end(array), [&](auto const& l, auto const& r) {
    return first_seen[l] < first_seen[r];
});

@kq: Mam funckję na sortowanie tabeli rosnąco, jak mógłbym to zamienić i czy w ogóle z quicksortu czy z jakiejś innej musiałbym korzystać?
void quicksort(int *tablica, int lewy, int prawy)
{
fstream plik_wyniki;
int v=tablica[(lewy+prawy)/2];
int i,j,x;
i=lewy;
j=prawy;
do
{
while (tablica[i]<v) i++;
while (tablica[j]>v) j--;
if (i<=j)
{
x=tablica[i];
tablica[i]=tablica[j];
tablica[j]=x;
i++;
j--;
}
}
while (i<=j);
if (j>lewy) quicksort(tablica,lewy, j);
if (i<prawy) quicksort(tablica, i, prawy);

Było już kilka dni temu:

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

int main()
{
	vector<int> src{5,3,2,5,5,2,1,4,6};
	unordered_map<int,size_t> positions;
	unordered_map<size_t,int> values;
	unordered_map<size_t,unsigned> counts;
	unordered_map<size_t,size_t> orders;
	for(size_t i=0,k=0;i<src.size();++i)
	{
		int value=src[i];
		positions.insert(make_pair(value,i));
		size_t position=positions[value];
		++counts[position];
		if(i==position)
		{
			values[i]=value;
			orders[k++]=i;
		}
	}
	for(size_t k=0;k<orders.size();++k)
	{
		size_t position=orders[k];
		int value=values[position];
		unsigned count=counts[position]; 
		while(count--) cout<<value<<' ';
	}
	return 0;
}

W czasie O(n)

Przepraszam, ale te rozwiązania są dla mnie zbyt zaawansowane, czy mógłby mi ktoś wytłumaczyć jak z tej mojej funkcji sortowania zrobić tę, której potrzebuję? Ewentualnie jak napisać od nowa taką funkcje, która będzie działać tak jak w przykładzie. Program musi pobierać dane do tablicy z pliku txt i wyniki również zapisywać w txt.

Dla każdej występującej na liście liczby oblicz miejsce pierwszego wystąpienia.
Sortuj wg miejsca pierwszego wystąpienia.

Temat już był poruszany z tydzień temu (może dwa). Tyle, ze specyfikacja problemu zajęła więcej czasu :)

@MarekR22: jak nazywał się ten temat na forum?

Tusty Hamburger napisał(a):

@MarekR22: jak nazywał się ten temat na forum?

Troszkę zajęło mi znalezienie:
Sortowanie elementów w tablicy, tak aby zgromadzić te same elementy, z kolejnością ich pierwszego wstąpienia + wczytywanie z pliku.

Pewnie kolega z roku.

> echo 5 4 5 5 3 1 2 2 4 | python3 -c 'import collections; print(*collections.Counter(input().split()).elements())'
5 5 5 4 4 3 1 2 2
>