Sortowanie tablic dwuwymiarowych

Question

Tak jak w tytule mam problem z sortowaniem tablic dwuwymiarowych, konkretnie trójek tylko po pierwszej kolumnie, np: 1 2 4 , 8 3 2 , 4 2 1 ,  2 5 7  na  1 2 4 , 2 5 7 , 4 2 1 , 8 3 2.

Nie mam pojęcia jak to napisać. Piszę w dev 5.11 (mówię o tym, ponieważ jeden z kodów, który widziałem nie był zgodny z moim kompilatorem.

Rozumiem, że gotowcy tu nie dajecie, więc proszę chociaż o drobną podpowiedź

Comments

Jaka złożoność Cię interesuje? Najprościej będzie napisać to przy pomocy sortowania bąbelkowego.

---

liniowa od n tz ilości trójek

---

Żadne sortowanie nie jest O(n), co najwyżej możesz osiągnąć ograniczenie dolne liniowe, co daje sortowanie bąbelkowe miedzy innymi,

---

mam na myśli, że O(n) to max na jaki mogę sobie pozwolić

---

Jakie sortowanie według Ciebie ma złożoność O(n)? Ogólnie, nie związane z Twoim problemem.

---

chyba nie zrozumiałeś, nie znam sortowania O(n) - prawda, ale nie wiedząc jakie sortowania mają złożoności po prostu podałem najwyższą złożoność, która będzie dobra

---

O(n) to dobra złożoność przy sortowaniu. Nie ma sortowania, bynajmniej ja nie znam takiego, które ma O(n), omega(n) tak. Skorzystaj z bąbelkowego po prostu. Chyba, że juz masz rozwiązanie.

---

@Nie Wiem, Dodatkowo https://www.geeksforgeeks.org/time-complexities-of-all-sorting-algorithms/

---

sortowanie przez scalanie wydaje mi się w miarę dobrym rozwiązaniem

Answer 1

Sprawdź to: How to sort multidimensional array by column in C++?
szczególnie ten przykład. Przerobiłem go "trochę" , żeby dopasować do:

konkretnie trójek tylko po pierwszej kolumnie, np:
       1 2 4 , 8 3 2 , 4 2 1 ,  2 5 7  
na  1 2 4 , 2 5 7 , 4 2 1 , 8 3 2.

#include <iostream>
#include <array>
#include <algorithm>
#include <iterator>

int main()
{
    std::array<int, 3> data[] =
    {
        { { 1, 2, 4 } },
        { { 8, 3, 2 } },
        { { 4, 2, 1 } },
        { { 2, 5, 7 } }
    };

    for ( const auto &row : data )
    {
        for ( const auto &s : row ) {
            std::cout.width(2);
            std::cout << s << ' ';
        }
        std::cout << std::endl;
    }

    std::cout << std::endl;

    std::sort( std::begin( data ), std::end( data ),
               []( const auto &a, const auto &b )
               {
                   return a[0] < b[0];
               } );

    for ( const auto &row : data )
    {
        for ( const auto &s : row ) {
            std::cout.width(2);
            std::cout << s << ' ';
        }
        std::cout << std::endl;
    }
}

Comments

i od 27-31 jest całe sortowanie?

---

Tak.

---

Tak. 

Sortowanie według pierwszej kolumny

return a[0] < b[0];

Sortowanie według drugiej kolumny

return a[1] < b[1];

 

---

dzieki

---

Wiecie może gdzie jest ta opcja?

Answer 2

Od zwykłego sortowania różni się to tylko tym, że zamiast zamieniać miejscami 2 elementy zamieniasz 2 tablice. Zakładam że tablica jest nx3 wymiarowa, czyli sortujesz po [i][0] (pierwszej kolumnie)

Comments

Hmm jak ma dokładnie wyglądać te zamienianie tablic? Pytanie może głupie ale zawsze korzystałem z funkcji sort()

---

Najprościej to tak jak dla zamiany 2 zmiennych. Potrzebna jest trzecia pomocnicza.

int zmienna1, zmienna2, pomocnicza;
pomocnicza=zmienna1;
zmienna1=zmienna2;
zmienna2=pomocnicza;

Tylko potrzebujesz tablic i kopiować każdy element do wybranej tablicy

---

dzięki, popróbuję