• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

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

VPS Starter Arubacloud
0 głosów
329 wizyt
pytanie zadane 17 lutego 2023 w C i C++ przez Dani Obywatel (1,420 p.)
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

3 odpowiedzi

+4 głosów
odpowiedź 17 lutego 2023 przez polandonion Mądrala (6,970 p.)
wybrane 17 lutego 2023 przez Dani
 
Najlepsza

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 << ' ';
}

 

komentarz 17 lutego 2023 przez Dani Obywatel (1,420 p.)
A funkcja cmp do czego służy?
2
komentarz 17 lutego 2023 przez polandonion Mądrala (6,970 p.)
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
2
komentarz 17 lutego 2023 przez polandonion Mądrala (6,970 p.)
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
komentarz 17 lutego 2023 przez Dani Obywatel (1,420 p.)

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;
}

 

1
komentarz 18 lutego 2023 przez polandonion Mądrala (6,970 p.)

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

taby[i].indeks = y;

znalezienie bledu zostawiam tobie :D

komentarz 18 lutego 2023 przez Dani Obywatel (1,420 p.)
Rzeczywiście, dziękuję Ci bardzo za pomoc :)
+2 głosów
odpowiedź 17 lutego 2023 przez tangarr Mędrzec (154,780 p.)
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
komentarz 17 lutego 2023 przez Dani Obywatel (1,420 p.)
Czy mógłbyś mi to rozpisać w kodzie, ponieważ nie do końca wiem jak napisać operator
+2 głosów
odpowiedź 17 lutego 2023 przez Great Stary wyjadacz (12,300 p.)

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

komentarz 17 lutego 2023 przez Dani Obywatel (1,420 p.)
do czego służy 3 argument sortowania?
1
komentarz 17 lutego 2023 przez Great Stary wyjadacz (12,300 p.)
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.

Podobne pytania

0 głosów
1 odpowiedź 585 wizyt
pytanie zadane 21 maja 2019 w C i C++ przez dudduss76 Początkujący (280 p.)
0 głosów
2 odpowiedzi 209 wizyt
pytanie zadane 25 lutego 2020 w JavaScript przez matedoo Nowicjusz (210 p.)
0 głosów
0 odpowiedzi 1,011 wizyt
pytanie zadane 22 maja 2019 w C i C++ przez resu Nowicjusz (120 p.)

92,453 zapytań

141,262 odpowiedzi

319,088 komentarzy

61,854 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Akademia Sekuraka 2024 zapewnia dostęp do minimum 15 szkoleń online z bezpieczeństwa IT oraz dostęp także do materiałów z edycji Sekurak Academy z roku 2023!

Przy zakupie możecie skorzystać z kodu: pasja-akademia - użyjcie go w koszyku, a uzyskacie rabat -30% na bilety w wersji "Standard"! Więcej informacji na temat akademii 2024 znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...