Comments 24
А еще лучше, если массив полностью уже отсортирован=)
Я бы посмотрел на реализацию пирамидальной сортировки на разных языках. Особенно транслируемых.
Я бы посмотрел на реализацию пирамидальной сортировки на разных языках. Особенно транслируемых.
Начинать надо было с пузырька. Сортировка вставками сразу это как-то негуманно совсем.
Сортировка вставками имеет сложность n2 на практике же приблизительное количество перестановок вычисляется по формуле n2/2.Вы забываете про O. В данном случае временная сложность O(n2), то есть время работы T(n) ограничено функцией C*n2 для некоторого C > 0.
Для доказательства был написан следующий код:Этот код ничего не доказывает, у вас просто частный случай. Доказывается эта формула в общем виде совсем не так.
А почему при разных n количество перестановок n2/2? Я просто еще студент, учусь еще)
Или вы имеете ввиду что c=1/2?
Имеется ввиду, что вы взяли определенное n с определенной перестановкой элементов и делаете очень «громкие» выводы. Возьмите и сделайте 1000 тестов. При разных n и при разной степени «сортированности» последовательности. Тогда вам явно станет более все наглядно. А лучше конечно почитать трушную теорию — Кормена например, или что-то в этом духе.
Сделал много тестов, рандомные числа, и худший случай для сортировки — массив отсортированный в обратном порядке. Выяснил вот что, там не n^2/2 там n*(n-1)/2 сравнений. Читаю именно Кормена, Бентли уже прочёл… Кто не верит пусть проверит, зря вы мне карму минусуете…
Вам хотели объяснить, что есть такое понятие, как асимптотическая сложность алгоритма. Она записывается для данного алгоритма так: O(n^2). Это означает, что рост количества реальный действий, совершаемых программой — T(n) — не может расти быстрее, чем функция C*n^2, где C — некоторая константа.
Вообще говоря, при учете сложности алгоритмов на эту константу нечасто обращают внимание. Потому что важна именно зависимость скорости работы от размера входных данных. Для алгоритмов сортировок, основанных на сравнении элементов, доказано, что не может существовать алгоритма со сложностью лучшей, чем n*log(n).
Опять же, взять в сравнение эту самую сортировку вставками и, например, HeapSort. У второго алгоритма эта константа намного больше — сами операции более сложные, плохо используется кеш, и т.д. Но тем не менее, HeapSort лучше именно тем, что при достаточно больших значениях n он превзойдет InsertionSort именно за счет того, что его асимптотическая сложность O(n*log(n)), и это при достаточно большом n «компенсирует» сколько угодно большую константу этого алгоритма.
Вообще говоря, при учете сложности алгоритмов на эту константу нечасто обращают внимание. Потому что важна именно зависимость скорости работы от размера входных данных. Для алгоритмов сортировок, основанных на сравнении элементов, доказано, что не может существовать алгоритма со сложностью лучшей, чем n*log(n).
Опять же, взять в сравнение эту самую сортировку вставками и, например, HeapSort. У второго алгоритма эта константа намного больше — сами операции более сложные, плохо используется кеш, и т.д. Но тем не менее, HeapSort лучше именно тем, что при достаточно больших значениях n он превзойдет InsertionSort именно за счет того, что его асимптотическая сложность O(n*log(n)), и это при достаточно большом n «компенсирует» сколько угодно большую константу этого алгоритма.
Спасибо большое, за объяснение) В оценках путаюсь бывает — Тетта и О…
Для алгоритмов сортировок, основанных на сравнении элементов, доказано, что не может существовать алгоритма со сложностью лучшей, чем n*log(n).
А можно поподробней про доказательство? Т.е., понятно, что алгоритмов с лучшей асимптотикой пока не придумали, но интересно было посмотреть именно на формальное доказательство.
Т.е., понятно, что алгоритмов с лучшей асимптотикой пока не придумали
И не придумают, ведь доказано, что минимум это O(nlogn)
Правда есть алгоритмы которые работают за время O(n), вроде BucketSort и Radix Sort. Но они не могут отсортировать произвольный набор данных, а только определенный, заранее известный.
посмотреть именно на формальное доказательство
classes.soe.ucsc.edu/cmps102/Fall01/solutions7.pdf — Смотрите проблему N2
Если в двух словах — представим, что нам нужно отсортировать массив из N элементов, для простоты условимся, что все ключи попарно различны. Эти элементы поступают на вход алгоритма сортировки в виде одной из N! различных перестановок этих элементов. Фактически, задачей алгоритма сортировки является нахождение такой перестановки, применение которой к входной перестановке ее отсортирует. Причем для каждой из возможных входных перестановок существует 1 единственная перестановка, переводящая входной массив в отсортированный.
Алгоритм сортировки постепенно «уточняет» необходимую перестановку так, чтобы в итоге осталась одна единственная, сортирующая именно эту входную последовательность. Здесь можно представить работу алгоритма как дерево принятия решений — на каждом шаге множество возможный перестановок «делится» на те, которые точно не подходят и те, среди которых есть искомая. Т.е., например, до первого шага алгоритма у нас есть N! вариантов, а после первого шага — t1,1 вариантов, и исключены t1,2 вариантов. Причем t1,1 + t1,2 = N!.. На втором шаге уже t1,1 делится на t2,1 и t2,2 так что t2,1 + t2,2 = t1,1 и т.д. В этом дереве каждый лист соответствует одной перестановке — следовательно, их N! штук. Дерево строго бинарно. Если h — высота этого дерева, значит, на i-м уровне дерева не более, чем 2^(i — 1) вершин. И всего вершин — не более 2^h. Так получается неравенство 2^h >= N!.. После логарифмирования обеих частей можно получить следующую цепочку: h >= log_2(N!) >= (N/2) * log_2(N/2). Т.е. высота дерева не может расти медленнее, чем N*log_2(N), получается, h = O(N*log_2(N)) — это и является нижней оценкой на высоту дерева.
Немного скомкано получилось, уж извините, но идея, надеюсь, понятна.
Алгоритм сортировки постепенно «уточняет» необходимую перестановку так, чтобы в итоге осталась одна единственная, сортирующая именно эту входную последовательность. Здесь можно представить работу алгоритма как дерево принятия решений — на каждом шаге множество возможный перестановок «делится» на те, которые точно не подходят и те, среди которых есть искомая. Т.е., например, до первого шага алгоритма у нас есть N! вариантов, а после первого шага — t1,1 вариантов, и исключены t1,2 вариантов. Причем t1,1 + t1,2 = N!.. На втором шаге уже t1,1 делится на t2,1 и t2,2 так что t2,1 + t2,2 = t1,1 и т.д. В этом дереве каждый лист соответствует одной перестановке — следовательно, их N! штук. Дерево строго бинарно. Если h — высота этого дерева, значит, на i-м уровне дерева не более, чем 2^(i — 1) вершин. И всего вершин — не более 2^h. Так получается неравенство 2^h >= N!.. После логарифмирования обеих частей можно получить следующую цепочку: h >= log_2(N!) >= (N/2) * log_2(N/2). Т.е. высота дерева не может расти медленнее, чем N*log_2(N), получается, h = O(N*log_2(N)) — это и является нижней оценкой на высоту дерева.
Немного скомкано получилось, уж извините, но идея, надеюсь, понятна.
Сложность алгоритмов сортировки определяется не количеством операций перестановки, а количеством операций сравнения элементов.
Мне кажется что эта статься не для хабра. (и пусть это останется моим имхо) (P.S. сори немного промахнулся, надо было на уровень выше)
Я просто не нашёл на хабре ничего подобного, и решил что было бы здорово брать какой-либо алгоритм и рассматривать его подробно)
Ну стоит начать с того, что объем статьи — не для подробного описания. Алгоритмы сортировок (за исключением чего-то нестандартного) разжеваны по всему интернету и поиск не составляет никакого труда…
Ну а на постскриптум, статья оригинал (во всяком случае анимация именно оттуда)- куда более широко отвечает на поставленный вопрос (и даже на русской вики всё понятно)=)
Ну а на постскриптум, статья оригинал (во всяком случае анимация именно оттуда)- куда более широко отвечает на поставленный вопрос (и даже на русской вики всё понятно)=)
Писать — это хорошо: как минимум развивает умение грамотно формулировать свои мысли. То, что вас раскритиковали — тоже хорошо: именно критика и указание на ошибки дают вектор для дальнейшего развития. Однако, перед написанием сделайте пару вещей:
1. Подумайте, интересено ли будет пользователям читать вашу статью. Вы пишете в первую очередь для сообщества, а не для себя. Иначе зачем вообще это нужно?
2. Хорошо изучите материал. Если вы завели тему, будьте готовы поддержать разговор на неё.
3. Определите для себя цель написания статьи. Возможно, вы хотите рассказать сообществу о новом, малоизвестном алгоритме; возможно, собрать воедино и структурировать информацию о чём-то, чтобы другие люди могли прочитать одну статью вместо 2-х десятков противоречивых и устаревших страниц по теме; возможно, обоснованно высказать своё мнение. Но должна быть цель, некий посыл, с которым вы пришли.
У вас же получается статья о сортировке, которую все и так хорошо знают, анализ алгоритмов вы пока ещё не очень освоили и поддержать разговор на хорошем уровне ещё не получается, а цель статьи остаётся неясной. Сообщество старается селекционировать наиболее полезные и интересные материалы и отсеивать остальные, поэтому вас и минусуют. Создавайте хороший, полезный материал, и вас будут плюсовать ;)
1. Подумайте, интересено ли будет пользователям читать вашу статью. Вы пишете в первую очередь для сообщества, а не для себя. Иначе зачем вообще это нужно?
2. Хорошо изучите материал. Если вы завели тему, будьте готовы поддержать разговор на неё.
3. Определите для себя цель написания статьи. Возможно, вы хотите рассказать сообществу о новом, малоизвестном алгоритме; возможно, собрать воедино и структурировать информацию о чём-то, чтобы другие люди могли прочитать одну статью вместо 2-х десятков противоречивых и устаревших страниц по теме; возможно, обоснованно высказать своё мнение. Но должна быть цель, некий посыл, с которым вы пришли.
У вас же получается статья о сортировке, которую все и так хорошо знают, анализ алгоритмов вы пока ещё не очень освоили и поддержать разговор на хорошем уровне ещё не получается, а цель статьи остаётся неясной. Сообщество старается селекционировать наиболее полезные и интересные материалы и отсеивать остальные, поэтому вас и минусуют. Создавайте хороший, полезный материал, и вас будут плюсовать ;)
Я новичёк на Хабре, это моя первая статья, обязательно будем расти… Целью было как раз объединить информацию об алгоритме в одну статью… Я на самом деле благодарен за критику, она обоснована и помогает развиваться) Всем комментаторам спасибо:) Задумка была начать с простого алгоритма и в следующих статьях рассматривать алгоритмы всё сложнее и сложнее. Когда ты можешь написать статью об алгоритме он у тебя невольно остаётся в памяти) Я не считаю этот алгоритм вершиной сложности, наоборот решил начать с простого. Моя фамилия Дроздов и это «В мире алгоритмов», в следующий раз всё будет лучше:)
Для тех камрадов, кто любит танцы и программирование: Insert-sort with Romanian folk dance
Sign up to leave a comment.
В мире алгоритмов: Сортировка Вставками