Существует множество методов сортировки в зависимости от скорости работы и сложности реализации. Самый простой, который приходит в голову большинству начинающих программистов - создать новый массив и в цикле искать наименьшим значения в основном массиве с переносом их в новый. Найдя первое наименьшее значение, начинают искать следующее, и так пока весь цикл не будет перенесен. Страшное дело, ведь алгоритм ест память, выполняется долго, а если массив уже отсортирован, то тратится тонна времени абсолютно впустую.
Недавно я увидел подобный код у опытного программиста, который хорошо знает базы данных и прекрасно решает производственные задачи. На вопрос: "А почему так", он сказал, что сложное придумывать лень а это реализовать очень просто.
Не просто, потому что более оптимальный алгоритм сортировки пузырями использует в 2 раза меньше памяти, работает намного быстрее (особенно, если элементы расположены более менее в порядке возрастания), а реализуется меньшим количеством строк кода, потому что не нужно выделять память, достаточно простого цикла. Если ты никогда не слышал о пузырях (не тех, которые ты пускаешь в ванной после сорокового супа), то эта статья поможет тебе увидеть все прелести банального знания эффективных алгоритмов.
Смысл алгоритма прост и в то же время очень красив. Беру первые два элемента массива и сравниваем их между собой. Если второй элемент меньше первого, то они меняются местами. Следующим шагом проверяем следующую пару элементов. Пройдя цикл проверяем, если во время цикла какие-либо элементы менялись местами, то надо повторить все сначала, иначе массив отсортирован.
Красиво? Если массив отсортирован, то алгоритм выполнится только один раз, чтобы убедиться в этом. Но даже если данные разбросаны в случайном порядке, количество шагов цикла будет меньше, чем если бы вы полностью переставали данные переносом в новый массив.
А теперь немного практики. Я тут набросал небольшой пример на С#, который показывает реализацию сортировки для простого массива из 20 чисел. Конечно, размер массива вы можете безболезненно изменять в любую сторону.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace BubblesSorting
{
class Program
{
static void Main(string[] args)
{
int[] array;
array = new int[20];
// fill array
Console.WriteLine("Source array: ");
Random rnd = new Random(array.Length);
for (int i = 0; i < array.Length; i++)
{
array[i] = rnd.Next(1, 100);
Console.Write("{0} ", array[i]);
}
bool bSort = false; ;
// we have to check array at list once
do
{
bSort = false;
for (int i = 1; i < array.Length; i++)
{
if (array[i] < array[i - 1])
{
int c = array[i];
array[i] = array[i - 1];
array[i - 1] = c;
bSort = true;
}
}
} while (bSort);
Console.WriteLine("\n");
Console.WriteLine("Sorted array: ");
for (int i = 0; i < array.Length; i++)
{
Console.Write("{0} ", array[i]);
}
}
}
}
Самое интересное в этом примере - это генерации случайных чисел для заполнения массива. Я несколько раз запускал пример и каждый раз у меня получался один и тот же массив. Совсем недавно я говорил об этой опасной функции и о том, что ее не хотят исправлять. Если использовать такой генератор для генерации ключа шифрования, то лучше не тратить время на шифровку, потому что хакеры смогут быстро угадать ключик.
Пузырьковая сортировка тоже медленная, но она решается намного красивее. В реальных приложениях я бы рекомендовал использовать Quicksort, который работает быстро.
Понравилось? Кликни Лайк, чтобы я знал, какой контент более интересен читателям. Заметку пока еще никто не лайкал и ты можешь быть первым
Паника, что-то случилось!!! Ничего не найдено в комментариях. Срочно нужно что-то добавить, чтобы это место не оставалось пустым.
Хотите найти еще что-то интересное почитать? Можно попробовать отфильтровать заметки на блоге по категориям.
Программист, автор нескольких книг серии глазами хакера и просто блогер. Интересуюсь безопасностью, хотя хакером себя не считаю
Copyright © 2024 Михаил Флёнов. Тираж 1 штука. Отпечатано на ноутбуке. А за права отвечаю, или постараюсь.
А здесь еще и копирайт поставлю: Professional Web Development.
Добавить Комментарий