C ++ сортирует массив указателей на символы - PullRequest
Новая
       15

C ++ сортирует массив указателей на символы

1 голос
/ 21 марта 2010

Можете ли вы сказать мне, что не так с моим методом? Я заканчиваю тем, что помещаю одну и ту же вещь каждый раз, и это на самом деле не сортировка. 

void sortArrays(){

    int i, j;



    for(i=0; i<counter; i++){



        for( j=0; j<i; j++){

            if( strcmp(title_arr[i], title_arr[j]) < 0){

                char* title_temp = title_arr[i];

                title_arr[j] = title_temp;





            }

        }

    }

Ответы [ 3 ]

10 голосов
/ 21 марта 2010

Это: 

char* title_temp = title_arr[i];

title_arr[j] = title_temp;

Эквивалентно: 

title_arr[j] = title_arr[i];

Вы никогда не меняете их местами, вы просто копируете одно в другое. Вы должны добавить эту строку: 

title_arr[i] = title_arr[j];

Между двумя. Таким образом, вы будете перезаписывать [i] с помощью [j], но _temp по-прежнему содержит старое значение [i], поэтому вы можете скопировать это значение в [j], поменяв их местами.

Полагаю, это также время для урока по алгоритмам. Ваш алгоритм известен как «пузырьковая сортировка» алгоритм. Он известен своей простотой, но в реальных условиях он известен своей неэффективностью (технический термин - «sux», а настоящий технический термин - производительность O(n^2) («N в квадрате»)). Некоторые более распространенные (и более эффективные) алгоритмы включают, среди прочих, Quicksort , сортировка слиянием и Heapsort . Подробнее об измерении алгоритмической масштабируемости см. Статью о Big Oh нотации . *

Но, как указал vava в комментарии, если ваше задание не состоит в том, чтобы написать собственную функцию сортировки, вы получите лучшую производительность с qsort (в C) или std::sort (в C ++). 

int mystrsort(const void *a, const void *b)
{
    return strcmp(*(const char **)a, *(const char **)b);
}

// later:
qsort(title_arr, sizeof title_arr / sizeof(char *), sizeof(char *), mystrsort);

Я не собираюсь наносить удар по std::sort, но он будет работать примерно так же (возможно, проще). **

* Обратите внимание, что любой, кто любит, может свободно менять эти ссылки в Википедии на ссылки переполнения стека. Было бы лучше сделать ссылку на SO, я только что связался с Википедией, потому что я знал, как быстрее найти нужную информацию.
** Обратите внимание, что любой, кто любит, может добавить std::sort пример. Я просто недостаточно знаком с C ++.

2 голосов
/ 21 марта 2010

Вы не поменяли должным образом, поэтому это не сработало. 

#include <iostream>
#include <algorithm>

int const counter = 4;
char * title_arr[counter] = {
    "d", "c", "b", "a"
};

void sortArrays(){
    for(int i = 0; i < counter; i++){
        for(int j = 0; j < i; j++){
            if(strcmp(title_arr[i], title_arr[j]) < 0){
                char* title_temp = title_arr[i];
                title_arr[i] = title_arr[j];
                title_arr[j] = title_temp;
                //you wouldn't have made that stupid mistake this way.
                //std::swap(title_arr[i], title_arr[j]);
            }
        }
    }
}

int compare(void const * a, void const * b) {
    return strcmp(static_cast<char const *>(a), static_cast<char const *>(b));
}

struct StringLess : public std::binary_function<char const *, char const *, bool> {
    bool operator() (char const * a, char const * b) const {
        return strcmp(a, b) < 0;
    }
};

int main(int argc, char * argv[])
{
    sortArrays();
    //those ones better
//  qsort(title_arr, counter, sizeof(char *), compare);
//  std::sort(title_arr, title_arr + counter, StringLess());
    for (int i = 0; i < counter; i++) {
        std::cout << title_arr[i] << ", ";
    }
    return 0;
}
1 голос
/ 21 марта 2010

Плохой стиль кодирования:1. Не используйте глобальные переменные.Лучше передать ваш массив и длину в качестве аргументов в функцию сортировки.Зачем?Ваша функция не может быть повторно использована.Что если вам нужно будет отсортировать другой массив?Да, вам нужно написать другую функцию сортировки ...2. Более сложный совет: используйте эмуляцию функции высшего порядка.Что делать, если вам нужно будет сортировать не только символы?Целое число, число с плавающей запятой, строки или ваши собственные типы.В этом случае вы также можете передать функцию compare () в функцию сортировки, которая может сравнивать объекты вашего массива.

...