Проблема с программой сортировки по алфавиту - PullRequest
Новая
       29

Проблема с программой сортировки по алфавиту

2 голосов
/ 11 мая 2019

У меня проблема с домашней работой, связанной с концепцией сортировки выбора. Нам дали скелетный код, в котором нам нужно выполнить функции bool compare(...) и void selectionsort(...), что я и сделал. Затем, запустив программу, следует отсортировать строки, заданные в main() в алфавитном порядке, и распечатать их в алфавитном порядке после печати исходных строк. Тем не менее, мой не сортирует его по алфавиту, и после попытки изменить несколько вещей, я застрял в выяснении, почему.

Обратите внимание, что единственное, что мне разрешено редактировать, это методы compare и selectionsort, больше ничего. Мы должны использовать метод compare (который возвращает истину, если первая строка появляется в алфавите раньше, чем другая строка, и сделал это) в методе selectionsort, чтобы сравнивать их, а не простое сравнение < > = заявление.

Я полагаю, что моя проблема как-то связана с этим оператором if в цикле for, но у меня много проблем с поиском правильного способа сделать это. Любая помощь будет высоко ценится! 

#include<iostream>
using namespace std;

bool compare(char *str1, char *str2, int strLen1, int strLen2) { // complete this method
    int small;
    if(strLen1 > strLen2)
        small = strLen2;
    else
        small = strLen1;

    //compare lexicographic values
    for(int i=0; i<small;i++){
        if(str1[i] < str2[i])
            return true;
        else if (str2[i] < str1[i])
            return false;
    }

    if (strLen1 < strLen2)
        return true;
    else
        return false;
}

void selectionsort(char **strings, int numStrings, int *eachStringLen) { // complete this method
    /* strings = jagged array
    numStrings = numRows
    eachStringLen = numColumnsInEachRow*/

    for(int i=0; i<numStrings-1;i++){
        int minIndex = i;
        if(compare(strings[i], strings[i+1], eachStringLen[i], eachStringLen[i+1]) == false){
        for(int j=i+1;j<numStrings;j++){
            if(strings[j]<strings[minIndex])
                minIndex = j;
        }
    }

        //swap strings[minIndex] and strings[i]
        char *tempA = strings[i];
        strings[i] = strings[minIndex];
        strings[minIndex] = tempA;

        int tempB = eachStringLen[i];
        eachStringLen[i] = eachStringLen[minIndex];
        eachStringLen[minIndex] = tempB;

    }//end for i
}//end selectionsort

int main() {
    char str0[] = { 'a', 'b', 'c' };
    char str1[] = { 'x', 'y', 'z', 'w' };
    char str2[] = { 'x', 'y', 'z', 'a', 'b' };
    char str3[] = { 'a', 'b', 'c', 'd', 'x' };
    char str4[] = { 'w', 'x', 'c', 'd', 'x' };
    char str5[] = { 'a', 'b', 'c', 'x', 'y' };
    char str6[] = { 'a', 'a', 'c' };
    char str7[] = { 'w', 'x', 'c', 'd', 'x' };
    char str8[] = { 'a', 'b', 'c', 'x'};
    char *strings[] = { str0, str1, str2, str3, str4, str5, str6, str7, str8 };
    int eachStringLength[] = { sizeof(str0) / sizeof(char), sizeof(str1)
            / sizeof(char), sizeof(str2) / sizeof(char), sizeof(str3)
            / sizeof(char), sizeof(str4) / sizeof(char), sizeof(str5)
            / sizeof(char), sizeof(str6) / sizeof(char), sizeof(str7)
            / sizeof(char), sizeof(str8)
            / sizeof(char) };
    int numStrings = 9;
    cout << "*** Original Strings ***" << endl;
    for (int i = 0; i < numStrings; i++) {
        for (int j = 0; j < eachStringLength[i]; j++) {
            cout << strings[i][j];
        }
        cout << endl;
    }
    selectionsort(strings, numStrings, eachStringLength);
    cout << endl << "*** Sorted Strings ***" << endl;
    for (int i = 0; i < numStrings; i++) {
        for (int j = 0; j < eachStringLength[i]; j++) {
            cout << strings[i][j];
        }
        cout << endl;
    }
}

1 Ответ

1 голос
/ 11 мая 2019

Ваша логика сортировки слегка отключена.Вам нужно два цикла, поскольку выбор сортировки равен O (N ^ 2), а никакая сортировка сравнения не может быть быстрее, чем O (NlogN) * ​​1004 *.

Внешний цикл долженперебирать каждый индекс i.Внутренний цикл должен найти наименьший элемент в диапазоне от i до N и поменять его местами с элементом в i.

Я бы также предложил вам использовать std::swap, чтобы сделать ваш код более читабельным.

Таким образом, содержимое вашего кода должно выглядеть следующим образом: 

for(int i=0; i<numStrings;++i){
    int minIndex = i;
    for(int j=i+1;j<numStrings;++j){
        if(compare(strings[j], strings[minIndex], eachStringLen[j], eachStringLen[minIndex])){
            minIndex = j;
        }
    }

    std::swap(strings[i], strings[minIndex]);
    std::swap(eachStringLen[i], eachStringLen[minIndex]);
}//end for i

Обратите внимание, что вы можетенапишите свой внешний цикл, чтобы продолжить на i<numStrings вместо i<numStrings-1, потому что последний элемент обязательно поменяется с собой.Но оба условия выхода в порядке.

Вывод: 

*** Original Strings ***
abc
xyzw
xyzab
abcdx
wxcdx
abcxy
aac
wxcdx
abcx

*** Sorted Strings ***
aac
abc
abcdx
abcx
abcxy
wxcdx
wxcdx
xyzab
xyzw
...