Сортировка двумерного массива методом qsort

@vfhbf · Регистрация: 14.01.2017

Author24 — интернет-сервис помощи студентам

C++

#include <iostream>
 
using namespace std;
std::string data[][3];
 
int cmp(const void *a, const void *b)
{
    string *arr1 = (string*)a; //{213,321}
    string *arr2 = (string*)b; //{13,999}
    
    return  (arr1< arr2) - (arr2<arr1);
 
    //return (arr1[0] + arr1[1]) < (arr2[0] + arr2[1]) ? -1 : 1;
}
 
int main()
{
    //const int N = 5;
    //
    //int arr[][2] = {
    //  {-213,-321},
    //  {13,999},
    //  {93,123},
    //  {3,1},
    //  {32,12}
    //};
 
    size_t i = 0;
        qsort(data, 200, sizeof(data[i++][0]), cmp);
    
    //std::vector<int> vc = { 23,3214,4536,6547,76,23,23 };
    //auto it = vc.
 
    //sort(vc.begin(), vc.end());
    
    
    
 
    /*for (size_t i = 0; i < N; i++)
    {
        printf("%d %d \n", arr[i][0], arr[i][1]);
    }
    std::cout << std::endl;
*/
    
    for (size_t i = 0; i < 200; i++)
    {
        std::cout << data[i][0].c_str() << "\t" << data[i][1].c_str() << "\t" << data[i][2].c_str()<< "\n";
    }
    system("pause");
    return 0;
}
 
std::string data[][3] = {
        { "x", "67", "16" },
        { "w", "98", "93" },
        { "g", "1", "71" },
        { "p", "21", "3" },
        { "q", "88", "35" },
        { "b", "76", "61" },
        { "w", "83", "25" },
        { "u", "19", "94" },
        { "t", "98", "90" },
        { "w", "6", "79" },
        { "e", "45", "66" },
        { "r", "16", "14" },
        { "s", "55", "94" },
        { "o", "47", "30" },
        { "p", "6", "52" },
        { "e", "5", "59" },
        { "k", "36", "22" },
        { "g", "54", "8" },
        { "h", "38", "98" },
        { "n", "75", "29" },
        { "x", "12", "3" },
        { "b", "3", "62" },
        { "r", "61", "2" },
        { "q", "81", "79" },
        { "g", "39", "6" },
        { "z", "99", "74" },
        { "b", "32", "88" },
        { "s", "50", "1" },
        { "q", "26", "71" },
        { "u", "40", "69" },
        { "a", "70", "93" },
        { "k", "95", "42" },
        { "b", "88", "31" },
        { "w", "79", "44" },
        { "u", "3", "21" },
        { "m", "39", "23" },
        { "a", "46", "51" },
        { "t", "86", "8" },
        { "h", "46", "11" },
        { "r", "53", "85" },
        { "e", "49", "12" },
        { "h", "32", "23" },
        { "y", "54", "39" },
        { "p", "85", "17" },
        { "f", "46", "38" },
        { "a", "47", "21" },
        { "a", "51", "63" },
        { "a", "67", "75" },
        { "b", "38", "17" },
        { "p", "94", "37" },
        { "d", "68", "12" },
        { "k", "9", "90" },
        { "f", "48", "77" },
        { "m", "52", "91" },
        { "m", "25", "71" },
        { "w", "4", "51" },
        { "b", "10", "40" },
        { "o", "52", "67" },
        { "x", "52", "72" },
        { "n", "42", "50" },
        { "w", "92", "55" },
        { "l", "17", "24" },
        { "c", "24", "56" },
        { "r", "29", "6" },
        { "w", "51", "4" },
        { "k", "57", "41" },
        { "x", "93", "51" },
        { "r", "67", "25" },
        { "x", "27", "93" },
        { "f", "45", "49" },
        { "h", "60", "4" },
        { "y", "81", "60" },
        { "y", "68", "6" },
        { "k", "19", "9" },
        { "e", "94", "74" },
        { "h", "39", "6" },
        { "f", "35", "1" },
        { "k", "30", "49" },
        { "z", "55", "41" },
        { "v", "4", "69" },
        { "s", "80", "58" },
        { "r", "67", "83" },
        { "u", "26", "61" },
        { "d", "4", "47" },
        { "t", "48", "21" },
        { "z", "49", "76" },
        { "k", "2", "81" },
        { "o", "26", "87" },
        { "i", "86", "51" },
        { "i", "85", "76" },
        { "o", "8", "23" },
        { "o", "70", "65" },
        { "d", "7", "38" },
        { "x", "14", "12" },
        { "d", "50", "18" },
        { "p", "95", "11" },
        { "j", "35", "32" },
        { "z", "57", "38" },
        { "e", "68", "13" },
        { "t", "58", "31" },
        { "b", "23", "56" },
        { "u", "37", "5" },
        { "b", "7", "62" },
        { "l", "61", "96" },
        { "z", "6", "31" },
        { "w", "30", "23" },
        { "z", "14", "58" },
        { "g", "86", "84" },
        { "r", "21", "96" },
        { "b", "11", "90" },
        { "q", "97", "59" },
        { "c", "42", "28" },
        { "f", "86", "93" },
        { "f", "98", "55" },
        { "x", "72", "53" },
        { "k", "33", "38" },
        { "l", "18", "87" },
        { "i", "15", "36" },
        { "e", "45", "60" },
        { "v", "63", "88" },
        { "s", "78", "9" },
        { "u", "63", "77" },
        { "g", "32", "78" },
        { "b", "9", "6" },
        { "b", "77", "76" },
        { "r", "67", "97" },
        { "q", "74", "98" },
        { "w", "88", "91" },
        { "n", "9", "46" },
        { "d", "90", "5" },
        { "a", "81", "74" },
        { "o", "82", "41" },
        { "a", "7", "52" },
        { "j", "46", "12" },
        { "o", "90", "51" },
        { "z", "8", "24" },
        { "a", "40", "10" },
        { "o", "64", "80" },
        { "z", "15", "36" },
        { "r", "25", "85" },
        { "u", "38", "83" },
        { "i", "95", "93" },
        { "c", "42", "54" },
        { "h", "49", "5" },
        { "x", "48", "72" },
        { "z", "2", "89" },
        { "r", "48", "30" },
        { "a", "90", "49" },
        { "h", "56", "39" },
        { "r", "32", "40" },
        { "r", "3", "12" },
        { "w", "27", "19" },
        { "g", "26", "52" },
        { "c", "35", "60" },
        { "z", "60", "94" },
        { "k", "24", "51" },
        { "z", "98", "36" },
        { "o", "61", "93" },
        { "o", "23", "34" },
        { "i", "34", "44" },
        { "r", "54", "47" },
        { "s", "20", "22" },
        { "n", "53", "24" },
        { "j", "88", "76" },
        { "y", "45", "89" },
        { "d", "85", "24" },
        { "t", "8", "84" },
        { "r", "75", "69" },
        { "v", "12", "69" },
        { "k", "37", "43" },
        { "l", "64", "74" },
        { "g", "60", "13" },
        { "a", "83", "1" },
        { "q", "50", "59" },
        { "m", "62", "51" },
        { "p", "15", "97" },
        { "l", "34", "30" },
        { "f", "29", "26" },
        { "y", "76", "71" },
        { "e", "86", "99" },
        { "j", "13", "92" },
        { "l", "76", "90" },
        { "d", "59", "38" },
        { "j", "19", "36" },
        { "j", "88", "11" },
        { "c", "98", "4" },
        { "y", "46", "25" },
        { "y", "38", "84" },
        { "y", "60", "97" },
        { "z", "8", "24" },
        { "l", "68", "8" },
        { "s", "5", "20" },
        { "z", "81", "32" },
        { "f", "65", "91" },
        { "f", "23", "63" },
        { "n", "41", "59" },
        { "r", "94", "42" },
        { "z", "70", "72" },
        { "d", "23", "74" },
        { "l", "74", "23" },
        { "a", "1", "84" },
        { "u", "72", "12" },
        { "o", "30", "2" },
        { "r", "57", "97" },
        { "d", "4", "13" },
        { "v", "66", "94" },
        { "g", "63", "86" },
        { "z", "88", "64" },
        { "z", "89", "59" },
        { "g", "37", "4" },
        { "n", "47", "45" },
        { "l", "2", "32" },
        { "k", "54", "79" },
        { "b", "52", "28" },
        { "r", "10", "32" },
        { "d", "1", "58" },
        { "m", "51", "68" },
        { "q", "69", "69" },
        { "f", "95", "65" },
        { "p", "20", "41" },
        { "v", "88", "23" },
        { "a", "76", "66" },
        { "x", "19", "41" },
        { "e", "94", "40" },
        { "q", "86", "77" },
        { "p", "42", "38" },
        { "m", "4", "26" },
        { "k", "51", "97" },
        { "n", "55", "77" },
        { "a", "54", "9" },
        { "h", "47", "42" },
        { "r", "72", "59" },
        { "e", "94", "77" },
        { "l", "32", "86" },
        { "i", "71", "99" },
        { "j", "13", "69" },
        { "m", "93", "4" },
        { "g", "52", "39" },
        { "c", "91", "69" },
        { "a", "28", "17" },
        { "j", "33", "23" },
        { "b", "56", "97" },
        { "d", "87", "83" },
        { "p", "4", "74" },
        { "c", "19", "21" },
        { "s", "46", "69" },
        { "m", "64", "30" },
        { "h", "25", "29" },
        { "t", "33", "62" },
        { "a", "4", "6" },
        { "y", "59", "59" },
        { "v", "32", "2" },
        { "o", "40", "7" },
        { "r", "91", "58" },
        { "o", "37", "85" },
        { "e", "22", "67" },
        { "d", "49", "30" },
        { "g", "4", "33" },
        { "b", "60", "97" },
        { "k", "37", "20" },
        { "z", "99", "48" },
        { "j", "3", "41" },
        { "p", "44", "79" },
        { "n", "95", "55" },
        { "t", "49", "1" },
        { "v", "97", "23" },
        { "t", "19", "61" },
        { "v", "67", "11" },
        { "y", "7", "63" },
        { "i", "55", "65" },
        { "g", "70", "56" },
        { "h", "98", "1" },
        { "m", "45", "71" },
        { "y", "78", "87" }
};

Подскажите что не так?! Пожалуйсто

@Kuzia domovenok · 15.08.2018, 14:41

не так то, что ты пытаешься хранить совершенно разнородные данные в массиве.
не надо так. Как минимум для этого есть структуры.

Добавлено через 9 минут
кстати, насколько я знаю, поправьте если не так, Сишным Qsortom сортировать Си++ строки бесполено, он оператор = не вывзовет из С++, или я не прав?

Добавлено через 5 минут

C++

#include <fstream>
#include <iostream>
#include <cstdlib>
//using namespace std;
std::string data[][3];
int cmp(const void *a, const void *b)
{
    std::string *arr1 = (std::string*)a;
    std::string *arr2 = (std::string*)b; 
 
    return  (*arr1< *arr2) ? -1 : 1;
 
}
int main()
{
    size_t i = 0;
    qsort(data, 274, 3*sizeof(std::string), cmp);
 
    for (size_t i = 0; i < 200; i++)
    {
        std::cout << data[i][0].c_str() << "\t" << data[i][1].c_str() << "\t" ;
        std::cout<< data[i][2].c_str() << "\n";
    }
    system("pause");
    return 0;
}
 
std::string data[][3] = {
    { "x", "67", "16" },

@vfhbf · 15.08.2018, 14:49 **[ТС]**

Kuzia domovenok, почему разнотипные данные в строках что нельзя целые числа хранить?

Добавлено через 2 минуты
Kuzia domovenok, Спасибо большое) А что означает 3*sizeof(std::string) ?

@Kuzia domovenok · 15.08.2018, 15:47

аффтар, учи что к чему последовательно, а не тупо хватай по верхам.
Кусорт очень старая функция, которая работает на манипулировании укаателями. Для того, чтобы сортировать массивы любых типов до того как появились шаблоны, ей нужно знать указатель на начало массива, размер элемента и их число, чтобы иметь возможность выбирать элемент массива из нетипизированного указателя void*.
Чтобы, например, выбрать iй элемент массива внутри функции, надо сместить указатель от начала на i*sizeof(размер элемента) байт
И сразу говорю, все эти указатели это уже оффтопик, суть в том, что твой код - говно. Кусорт в коде для С++ и стд;;стринг лютое говно.

@vfhbf · 15.08.2018, 17:20 **[ТС]**

Kuzia domovenok, Спасибо что вы помогли в решении задачи и прояснили, хотя и грубовато, а код дал препод

Добавлено через 1 минуту
Kuzia domovenok, Сказал просто переделать чтобы по первому столбцу сортировало а я не могла понять как работала эта фу-кция.

@Kuzia domovenok · 15.08.2018, 20:16

vfhbf, ну по сути вся переделка будет состоять в том, чтобы указать в функции сортировки трёхкратный размер элемента, чтобы она их выхватывала и обменивала пачками по 3,

а в функции сравнения размер элемента не менять, чтобы на проверку отправляла только по первому из каждой выбранной троицы.

@rat0r · 16.08.2018, 10:56

vfhbf, Kuzia domovenok,

Сообщение от http://eel.is/c++draft/alg.c.library

[ Note: The header <cstdlib> declares the functions described in this subclause. — end note]

C++

void* bsearch(const void* key, const void* base, size_t nmemb, size_t size,
              c-compare-pred* compar);
void* bsearch(const void* key, const void* base, size_t nmemb, size_t size,
              compare-pred* compar);
void qsort(void* base, size_t nmemb, size_t size, c-compare-pred* compar);
void qsort(void* base, size_t nmemb, size_t size, compare-pred* compar);

Effects: These functions have the semantics specified in the C standard library.
Remarks: The behavior is undefined unless the objects in the array pointed to by base are of trivial type.

@Kuzia domovenok · 16.08.2018, 14:53

rat0r, я в первом же сообщении написал, что не уверен но кажется нельзя сортировать классы. Но у меня не было аргументов против этого. Я думал, что кусорт не умеет в конструкторы, деструкторы и операторы=, однако, взявшись за этот код, я к великому удивлению обнаружил, что кусорт работает, поэтому свои претензии опустил. Я даже намерянно тестировал его со строками значительно разной длины, думая, что бе нормальных конструкторов копирования он уж точно переместит типа большую строку в меньшую и вызовет коррупцию кучи, но на удивления все мои тесты проходились..

@rat0r · 16.08.2018, 15:29

Сообщение от Kuzia domovenok

взявшись за этот код, я к великому удивлению обнаружил, что кусорт работает

Из одного своего случая ты сделал вывод, что нет UB?

Сообщение от Kuzia domovenok

Я даже намерянно тестировал его со строками значительно разной длины

Оно и на коротких валится (так вот устроено short string optimization в libstdc++ (~gcc))

C++

#include <fstream>
#include <iostream>
#include <cstdlib>
 
std::string data[][3] = {
        { "x", "67", "16" },
        { "w", "98", "93" },
        { "g", "1", "71" },
        { "p", "21", "3" },
        { "q", "88", "35" },
        { "b", "76", "61" },
        { "w", "83", "25" },
        { "u", "19", "94" },
        { "t", "98", "90" },
        { "w", "6", "79" },
};
 
int cmp(const void *a, const void *b)
{
    std::string *arr1 = (std::string*)a;
    std::string *arr2 = (std::string*)b; 
    
    return  (*arr1< *arr2) ? -1 : 1; 
}
 
int main()
{
    qsort(data, std::size(data), sizeof(data[0]), cmp);
 
    for (size_t i = 0; i < std::size(data); i++)
    {
        std::cout << data[i][0] << "\t" << data[i][1] << "\t" ;
        std::cout<< data[i][2] << "\n";
    }
}

https://wandbox.org/permlink/0xOZzKAscxxE5hH5

Код

*** Error in `./prog.exe': munmap_chunk(): invalid pointer: 0x0000000000604490 ***
======= Backtrace: =========
/lib/x86_64-linux-gnu/libc.so.6(+0x777e5)[0x7f45ab8887e5]
/lib/x86_64-linux-gnu/libc.so.6(cfree+0x1a8)[0x7f45ab895698]
./prog.exe[0x402cf4]
./prog.exe[0x402b0f]
./prog.exe(_ZNSt7__cxx1112basic_stringIcSt11char_traitsIcESaIcEE10_M_destroyEm+0x44)[0x402976]
./prog.exe(_ZNSt7__cxx1112basic_stringIcSt11char_traitsIcESaIcEE10_M_disposeEv+0x36)[0x402794]
./prog.exe(_ZNSt7__cxx1112basic_stringIcSt11char_traitsIcESaIcEED2Ev+0x18)[0x402662]
./prog.exe[0x4018a5]
/lib/x86_64-linux-gnu/libc.so.6(+0x39ff8)[0x7f45ab84aff8]
/lib/x86_64-linux-gnu/libc.so.6(+0x3a045)[0x7f45ab84b045]
/lib/x86_64-linux-gnu/libc.so.6(__libc_start_main+0xf7)[0x7f45ab831837]
./prog.exe[0x401699]
…

@Kuzia domovenok · 16.08.2018, 16:16

Сообщение от rat0r

Оно и на коротких валится (так вот устроено short string optimization в libstdc++ (~gcc))

говорю же, в моей IDE всё работает. И твой код тоже. Я очень старался найти ошибку и не нашёл

@rat0r · 16.08.2018, 16:29

Сообщение от Kuzia domovenok

говорю же, в моей IDE всё работает. И твой код тоже.

И что отсюда следует?

Сообщение от Kuzia domovenok

Я очень старался найти ошибку и не нашёл

http://eel.is/c++draft/alg.c.library#3

@vfhbf -1 / 1 / 1 Регистрация: 14.01.2017 Сообщений: 322
	15.08.2018, 14:49 [ТС]	3
	Kuzia domovenok, почему разнотипные данные в строках что нельзя целые числа хранить? Добавлено через 2 минуты Kuzia domovenok, Спасибо большое) А что означает 3*sizeof(std::string) ? 0

@Kuzia domovenok 4064 / 3318 / 924 Регистрация: 25.03.2012 Сообщений: 12,493 Записей в блоге: 1
	15.08.2018, 15:47	4
	аффтар, учи что к чему последовательно, а не тупо хватай по верхам. Кусорт очень старая функция, которая работает на манипулировании укаателями. Для того, чтобы сортировать массивы любых типов до того как появились шаблоны, ей нужно знать указатель на начало массива, размер элемента и их число, чтобы иметь возможность выбирать элемент массива из нетипизированного указателя void. Чтобы, например, выбрать iй элемент массива внутри функции, надо сместить указатель от начала на isizeof(размер элемента) байт И сразу говорю, все эти указатели это уже оффтопик, суть в том, что твой код - говно. Кусорт в коде для С++ и стд;;стринг лютое говно. 0

@vfhbf -1 / 1 / 1 Регистрация: 14.01.2017 Сообщений: 322
	15.08.2018, 17:20 [ТС]	5
	Kuzia domovenok, Спасибо что вы помогли в решении задачи и прояснили, хотя и грубовато, а код дал препод Добавлено через 1 минуту Kuzia domovenok, Сказал просто переделать чтобы по первому столбцу сортировало а я не могла понять как работала эта фу-кция. 0

@Kuzia domovenok 4064 / 3318 / 924 Регистрация: 25.03.2012 Сообщений: 12,493 Записей в блоге: 1
	15.08.2018, 20:16	6
	vfhbf, ну по сути вся переделка будет состоять в том, чтобы указать в функции сортировки трёхкратный размер элемента, чтобы она их выхватывала и обменивала пачками по 3, а в функции сравнения размер элемента не менять, чтобы на проверку отправляла только по первому из каждой выбранной троицы. 1

@Kuzia domovenok 4064 / 3318 / 924 Регистрация: 25.03.2012 Сообщений: 12,493 Записей в блоге: 1
	16.08.2018, 14:53	8
	rat0r, я в первом же сообщении написал, что не уверен но кажется нельзя сортировать классы. Но у меня не было аргументов против этого. Я думал, что кусорт не умеет в конструкторы, деструкторы и операторы=, однако, взявшись за этот код, я к великому удивлению обнаружил, что кусорт работает, поэтому свои претензии опустил. Я даже намерянно тестировал его со строками значительно разной длины, думая, что бе нормальных конструкторов копирования он уж точно переместит типа большую строку в меньшую и вызовет коррупцию кучи, но на удивления все мои тесты проходились.. 0

@Kuzia domovenok 4064 / 3318 / 924 Регистрация: 25.03.2012 Сообщений: 12,493 Записей в блоге: 1
	16.08.2018, 16:16	10
	Сообщение от rat0r Оно и на коротких валится (так вот устроено short string optimization в libstdc++ (~gcc)) говорю же, в моей IDE всё работает. И твой код тоже. Я очень старался найти ошибку и не нашёл 0

@rat0r 285 / 176 / 21 Регистрация: 16.02.2018 Сообщений: 666
	16.08.2018, 16:29	11
	Сообщение было отмечено MrGluck как решение Решение Сообщение от Kuzia domovenok говорю же, в моей IDE всё работает. И твой код тоже. И что отсюда следует? Сообщение от Kuzia domovenok Я очень старался найти ошибку и не нашёл http://eel.is/c++draft/alg.c.library#3 0

Сортировка двумерного массива методом qsort

Решение