Раз пошло такое дело и я опубликовал свою реализацию быстрой сортировки, с которой вы можете ознакомиться, то как можно обойти стороной самую популярную сортировку? Вообще, спроси у любого студента: «Какую сортировку ты знаешь?», и получишь ответ: «Пузырьком!». Нельзя просто взять и пройти мимо этого факта, мой святой долг стать одним из тысячи человек, которые опубликуют реализацию сортировки пузырьком. Поэтому усаживайтесь поудобнее, мы начинаем!
Суть пузырьковой сортировки
Алгоритм представляет собой проходы по сортируемому массиву, в которых сравниваются два соседних элемента, и, если порядок в них нарушен, то они меняются местами. За каждый проход минимум один элемент встает на свое место — «всплывает» в массиве.
Проход осуществляется двумя циклами: по i и по j. Внешний цикл по i идет от 0 до size-1, где size — размер массива. Важно заметить, что внутренний цикл достаточно прогнать от 0 до size-i-1 так как на i-ом шаге элементы после i-го индекса уже гарантированно отсортированы.
Реализация «пузырька» на C/C++
Вот собственно сам исходный код сортировки, два цикла и не более.
void bubleSort(int *mas, int size) {
for(int i = 0; i < size; i++) {
for(int j = 0; j < size - i - 1; j++) {
if(mas[j] > mas[j+1]) {
int tmp = mas[j];
mas[j] = mas[j+1];
mas[j+1] = tmp;
}
}
}
}
Однако у алгоритма возможна оптимизация. Мы точно знаем, что если на шаге внутреннего алгоритма никакие два элемента местами не поменяются, то массив уже отсортирован и дальнейшие проходы по внешнему циклу не нужны. Поэтому можно добавить флаг прерывания прохода по внешнему циклу.
void bubleSort(int *mas, int size) {
bool interruptFlag;
for(int i = 0; i < size; i++) {
interruptFlag = true;
for(int j = 0; j < size - i - 1; j++) {
if(mas[j] > mas[j+1]) {
int tmp = mas[j];
mas[j] = mas[j+1];
mas[j+1] = tmp;
//Была хотя бы одна замена элементов => нужен еще проход по i
interruptFlag = false;
}
}
//Если не было замен, то заканиваем проходы
if(interruptFlag) {
cout << "break" << endl;
break;
}
}
}
Заключение
Почему я назвал статью «реализация на C/C++», если код на чистом Си? Отвечаю, в моей голове, которую уже четвертый год(на данный момент) натачивают на информационную безопасность, чистый Си ассоциируется с низкоуровневым системным программированием исключительно. А все алгоритмы на чуть более высоком уровне, чаще всего написаны на смеси C и C++, поэтому такой язык я привык называть С/C++.
Мысленно вернулся на первый курс, чудесное ощущение, когда реализация пузырька кажется великим достижением, эх. Больше добавить мне нечего, спасибо за внимание!