сортировка массива по алфавиту с ++

Question

Напишите программу для сортировки и отображения имен в алфавитном порядке (используйте сортировку выбора). Программа предлагает пользователю ввести искомое имя (используйте двоичный поиск). Программа также вносит исправления в верхний регистр первого символа имени и фамилии.

Я могу только выяснить, как поступить с библиотекой алгоритмов, но я не могу ее использовать.

#include <iostream>
#include <string>
#include <string.h>
#include <conio.h>
using namespace std;


int main() {
    const int SIZE = 20;
char temp;
int i, j;
bool madeAswap;
char arr[SIZE][SIZE] = { "Collins, Bill", "Smith, Bart", "Michalski, Joe",
    "Griffin, Jim","Sanchez, Manny", "Rubin, Sarah", "Taylor, Tyrone",
    "Johnson, Jill","Allison, Jeff", "Moreno, Juan", "Wolfe, Bill",
    "Whitman, Jean","Moretti, Bella", "Wu, Hong", "Patel, Renee",
    "Harrison, Rose","Smith, Cathy", "Conroy, Pat", "Kelly, Sean", "Holland, Beth" };
do {
    madeAswap = false;
    for (i = 1; i < SIZE; i++)
    {
        for (j = 1; j < SIZE; j++)
        {
            if (strcmp(arr[j - 1], arr[j]) > 0)
            {
                temp = arr[i][i];
                arr[i][i] = arr[i + 1][i + 1];
                arr[i + 1][i + 1] = temp;
                madeAswap = true;
            }
        }
    }
    }while (madeAswap);
for (int j = 0; j < SIZE; j++) {
    cout << arr[j][j] << endl;
}
system("pause");
return 0;

}

Answer 1

Вы сказали, что вам нужно использовать «сортировку выбора», но вы используете «пузырьковую сортировку». Я изменил вашу программу на обоих циклах (для), а также на обмен строк (движение).

#include <iostream>
#include <string>
#include <string.h>
using namespace std;

int main() {
    const int SIZE = 20;
    string temp;
    int i, j;
    string arr[SIZE] = { "Collins, Bill", "Smith, Bart", "Michalski, Joe",
        "Griffin, Jim","Sanchez, Manny", "Rubin, Sarah", "Taylor, Tyrone",
        "Johnson, Jill","Allison, Jeff", "Moreno, Juan", "Wolfe, Bill",
        "Whitman, Jean","Moretti, Bella", "Wu, Hong", "Patel, Renee",
        "Harrison, Rose","Smith, Cathy", "Conroy, Pat", "Kelly, Sean", "Holland, Beth" };
    for (i = 0; i < (SIZE - 1); i++)
    {
        for (j = (i+1); j < SIZE; j++)
        {
            if ( arr[i] > arr[j])
            {
               temp = arr[i];
               arr[i] = arr[j];
               arr[j] = temp;
            }
        }
    }
    for (int j = 0; j < SIZE; j++) {
        cout << arr[j] << endl;
    }
    system("pause");
    return 0;
}

Истинный «сортировка выбора» имеет сложность сравнения O (n ^ 2) и сложность движения O (n). Я считаю, что правильный способ его реализации должен быть таким:

#include <iostream>
#include <string>
#include <string.h>
using namespace std;

int main() {
    const int SIZE = 20;
    string temp;
    int i, j;
    string arr[SIZE] = { "Collins, Bill", "Smith, Bart", "Michalski, Joe",
        "Griffin, Jim","Sanchez, Manny", "Rubin, Sarah", "Taylor, Tyrone",
        "Johnson, Jill","Allison, Jeff", "Moreno, Juan", "Wolfe, Bill",
        "Whitman, Jean","Moretti, Bella", "Wu, Hong", "Patel, Renee",
        "Harrison, Rose","Smith, Cathy", "Conroy, Pat", "Kelly, Sean", "Holland, Beth" };
    for (i = 0; i < (SIZE - 1); i++)
    {
        int k = i;
        for (j = (i+1); j < SIZE; j++)
        {
            if ( arr[k] > arr[j])
            {
               k = j;
            }
        }
        if (i != k) {
            temp = arr[i];
            arr[i] = arr[k];
            arr[k] = temp;
        }
    }
    for (int j = 0; j < SIZE; j++) {
        cout << arr[j] << endl;
    }
    system("pause");
    return 0;
}

Объяснение кода: String - это класс C ++, который содержит массив символов. Оператор 'string arr [SIZE]' является массивом строк размером SIZE. Вы можете обратиться к строковому классу в 'http://www.cplusplus.com/reference/string/string/'.

Другая проблема в вашем коде касается порядка. «Сортировка выбора» сортирует список, сравнивая элемент с последующими элементами, поэтому ваш второй цикл неверен, это должно быть: 'for (j = (i + 1); j

Наконец, вам нужно сделать своп (движение) только после того, как вы прошли через весь j.

Answer 2

Во-первых, это не какой-либо алгоритм сортировки, но он близок к Bubble Sort, алгоритму, требующему много времени. Опять же, вы имеете дело с символами случайным образом, а не со строками. Посмотрите на эту модификацию, которую я сделал, она будет сортировать только ваши массивы

#include <iostream>
#include <string>
using namespace std;

int main() {
    const int SIZE = 20;
    string temp;
    int i, j;
    string arr[SIZE] = { "Collins, Bill", "Smith, Bart", "Michalski, Joe",
        "Griffin, Jim","Sanchez, Manny", "Rubin, Sarah", "Taylor, Tyrone",
        "Johnson, Jill","Allison, Jeff", "Moreno, Juan", "Wolfe, Bill",
        "Whitman, Jean","Moretti, Bella", "Wu, Hong", "Patel, Renee",
        "Harrison, Rose","Smith, Cathy", "Conroy, Pat", "Kelly, Sean", "Holland, Beth" };
    for (i = 1; i < SIZE; i++)
    {
        for (j = 1; j < SIZE; j++)
        {
            if ( arr[j-1] > arr[j])
            {
               temp = arr[j-1];
               arr[j-1] = arr[j];
               arr[j] = temp;
            }
        }
    }
    for (int j = 0; j < SIZE; j++) {
        cout << arr[j] << endl;
    }
    system("pause");
    return 0;
}