Sortowanie tablicy z wartościami wraz z zachowaniem indeksów

Question

Witam,

czy wie ktoś może z was jak łatwo posrtować  tablicę wraz zachowaniem indeksów każdej wartości?

np.

indexy:    1 2 3 4 5

wartości: 3 1 4 2 9

po posortowaniu:

indexy :    2 4 1 3 5

wartości : 1 2 3 4 9

Answer 1

tutaj z objasnieniem:

#include <bits/stdc++.h>

using namespace std;

struct Liczba {
	// kazda zmienna typu 'Liczba' bedzie miala w sobie 2 zmienne
	int wartosc, indeks;
};

bool cmp(Liczba a, Liczba b) {
	//jezeli liczby sa takie same to uporzadkuj wg. indeksow
	if (a.wartosc == b.wartosc)
		return (a.indeks < b.indeks);

	// w przeciwnym wypadku uporzadkuj wg. wartosci
	else
		return (a.wartosc < b.wartosc);	
}

Liczba tab[1000000];

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int n;
	cin >> n;

	for (int i = 0; i < n; i ++) {
		// wczytuje wartosc tab[i].wartosc
		cin >> tab[i].wartosc;

		// a potem przypisuje indeks do tab[i].indeks
		// miej na uwadze, ze numeruje od zera :D
		tab[i].indeks = i;
	}

	sort(tab, tab + n, cmp);

	// wypisuje wartosci posortowane
	for (int i = 0; i < n; i ++)
		cout << tab[i].wartosc << ' ';
	cout << '\n';

	// a pod nimi ich indeksy
	for (int i = 0; i < n; i ++)
		cout << tab[i].indeks << ' ';
}

 

Comments

A funkcja cmp do czego służy?

---

Funkcja cmp() ma za zadanie porównywać dwa elementy do posortowania przez funkcję sort(). Podczas używania własnych struktur jest ona niezbędna, gdyż bez niej kompilator wypluje (i słusznie) błąd.

 

Podczas używania własnych struktur musisz stworzyć taką funkcję, aby funkcja sort wiedziała względem czego ma sortować, bo jak komputer ma się domyślić, czy chcesz posortować wg. indeksów, czy też może względem wartości, malejąco, czy też rosnąco.

 

Polecam przeczytać ten wątek: https://forum.pasja-informatyki.pl/568975/std-sort-c

---

tutaj też można dowiedzieć się czegoś ciekawego - nie znając jeszcze możliwości funkcji sort nie wiedziałem, że można zbudować własną funkcję, która rozbuduje sort()'a o dodatkową możliwość: https://forum.pasja-informatyki.pl/568972/spoj-zadanie-sort1

---

Napisałem kod w którym nie poprawnie sortują mi się dane. Wiesz może czemu?

#include <iostream>
#include <algorithm>

using namespace std;

const int MAXN = 2e5 + 5;

int rep[MAXN];

int Find(int a) {
	if (rep[a] == a)
		return a;
	rep[a] = Find(rep[a]);
	return rep[a];
}

void Union(int a, int b) {
	rep[Find(a)] = rep[Find(b)];
}
struct Liczba {
	// kazda zmienna typu 'Liczba' bedzie miala w sobie 2 zmienne
	int wartosc, indeks;
};

bool cmp(Liczba a, Liczba b) {
	//jezeli liczby sa takie same to uporzadkuj wg. indeksow
	if (a.wartosc == b.wartosc)
		return (a.indeks < b.indeks);

	// w przeciwnym wypadku uporzadkuj wg. wartosci
	else
		return (a.wartosc < b.wartosc);
}

Liczba tabx[MAXN];
Liczba taby[MAXN];

int main()
{
	int n, m;
	cin >> n >> m;

	for (int i = 1; i <= n; ++i) {
		int x, y;
		cin >> x >> y;
		
		tabx[i].wartosc = x;
		taby[i].wartosc = y;
		tabx[i].indeks = i;
		taby[i].indeks = y;
	}
	for (int i = 1; i <= n; ++i)
		rep[i] = i;
	sort(tabx+1, tabx + n+1 , cmp);
	sort(taby+1, taby + n+1, cmp);

	for (int i = 1; i <= n; ++i) {
		if (tabx[i].wartosc == tabx[i + 1].wartosc)
			Union(tabx[i].indeks, tabx[i + 1].indeks);
		if (taby[i].wartosc == taby[i + 1].wartosc)
			Union(taby[i].indeks, taby[i + 1].indeks);
	}
	for (int i = 1; i <= n; ++i)
		cout << rep[i] << ' ';
	for (int i = 0; i < m; ++i) {
		int x, y;
		cin >> x >> y;
		if (Find(x) == Find(y))
			cout << "TAK" << '\n';
		else
			cout << "NIE" << '\n';
	}

	return 0;
}

 

---

nie przeszukiwalem calego kodu, ale szczegolna uwage zwrocila 50. linia:

taby[i].indeks = y;

znalezienie bledu zostawiam tobie :D

---

Rzeczywiście, dziękuję Ci bardzo za pomoc :)

Answer 2

Utwórz strukturę zawierającą dwie liczby: wartości i indeks.
Napisz operator< dla tej struktury i przekaż go do funkcji sort
https://en.cppreference.com/w/cpp/algorithm/sort

Comments

Czy mógłbyś mi to rozpisać w kodzie, ponieważ nie do końca wiem jak napisać operator

Answer 3

W zasadzie to co @tangar napisał wyczerpuje temat, ale możesz użyć std::pair:

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>

int main() {
    using index_value = std::pair<unsigned, int>;
    std::vector<index_value> vec;
    vec.emplace_back(0, 3);
    vec.emplace_back(1, 1);
    vec.emplace_back(2, 4);
    vec.emplace_back(3, 2);
    vec.emplace_back(4, 9);

    std::sort(vec.begin(), vec.end(),
        [](auto const& rhs, auto const& lhs) { return rhs.second < lhs.second; });
    //std::ranges::sort(vec, {}, &index_value::second); C++20

    for (auto [index, value] : vec) {
        std::cout << index << " " << value << "\n";
    }
}

https://stackoverflow.com/questions/279854/how-do-i-sort-a-vector-of-pairs-based-on-the-second-element-of-the-pair

Comments

do czego służy 3 argument sortowania?

---

Podsyłasz adres funkcji lub obiekt funkcyjny, który porównuje dwie wartości podane przez std::sort. Możesz sortować dane rosnąco, malejąco, lub według dowolnego kryterium np. najpierw parzyste liczby.