Практически любой алгоритм сортировки состоит из комбинации двух элементарных операций: сравнение элементов и перестановка элементов. Алгоритмы сортировки не зависят от того, чем являются элементы массива: числами, символами, строками, структурами и т.д. Однако реализация этих двух операций может различаться. Рассмотрим, как данные операции реализуются при сортировке массива строк.
Для начала нужно определиться с тем, как будет выполняться сортировка. Данный вопрос возникает потому, что строки можно сортировать по алфавиту, по длине строки, по первой букве и т.д. Кроме того, как и всегда порядок может быть прямым (по возрастанию) и обратным (по убыванию).
Вначале вспомним алгоритм сортировки методом прямого выбора (по возрастанию):
Находим минимальный элемент и меняем его местами с первым;
Находим минимальный элемент, начиная со второго, и меняем его местами со вторым;
Находим минимальный элемент, начиная с третьего, и меняем его местами с третьим;
…
Теперь рассмотрим, как применить этот алгоритм для сортировки массива строк по алфавиту по возрастанию. Для поиска минимального элемента следует использовать оператор > или <. Перестановка элементов осуществляется стандартно в три присваивания. Расширим наш список писателей и отсортируем его.
#include "stdafx.h"
#include <iostream>
#include <string>
using namespace std;
//Объявляем массив глобально, чтобы
//его видели все функции
const int size = 10;
string writers[size] = {
"Толстой", "Достоевский", "Твен",
"Майн Рид", "Горький", "Чехов",
"Дефо", "Тургенев", "Островский",
"Берроуз"
};
//Вывод на экран
void printWriters() {
for (int i=0; i<size; i++) {
cout << writers[i] << endl;
}
}
//Меняем местами строки номер i и j
void swap(int i, int j) {
string temp;
temp = writers[i];
writers[i] = writers[j];
writers[j] = temp;
}
//Поиск индекса минимального элемента,
//начиная с элемента номер startPosition
int findMin(int startPosition) {
int j_min = startPosition;
for (int j=startPosition; j<size; j++) {
//Сравнение элементов
if (writers[j_min] > writers[j]) {
j_min = j;
}
}
return j_min;
}
//Сортировка методом прямого выбора
void sortWriters() {
for (int i=0; i<size-1; i++) {
//Ищем индекс минимального, начиная с i-го
int j_min = findMin(i);
//меняем местами его и i-ый
swap(i, j_min);
}
}
int main() {
setlocale(LC_ALL, "Russian");
cout << "Исходный массив:\n";
printWriters();
sortWriters();
cout << "\nОтсортированный массив:\n";
printWriters();
return 0;
}
Для сортировки массива строк по длине достаточно изменить сравнение:
…
if (writers[j_min].length() > writers[j].length()) {
