Нужно отсортировать числа ? Понимаем методы сортировок чисел

Discussion in 'С/С++, C#, Rust, Swift, Go, Java, Perl, Ruby' started by UnPazz, 14 Sep 2008.

  1. UnPazz

    UnPazz Elder - Старейшина

    Joined:
    30 Aug 2008
    Messages:
    96
    Likes Received:
    43
    Reputations:
    6
    Урок 1. Необходимая теория.
    Пусть дана последовательность чисел 4,2,1,5,3. Необходимо переставить элементы последовательности так, чтобы они были расставлены в возрастающем или убывающем порядке (например, 1,2,3,4,5).

    Существует более 10 методов (алгоритмов) сортировки последовательностей чисел. В чем их отличие? В основном в быстроте сортировки. Например, быстрые методы отсортируют последовательность из 5000 чисел за 2 секунды, а самые простые за 15 секунд.

    Помимо скорости выполнения сортировки, есть более «глубокие» способы оценить метод сортировки – это кол-во сравнений и пересылок элементов. Во время сортировки элементов, происходят их пересылки - 2 меняем с 4, 5 меняем с 1 – так чтобы они были отсортированы в возрастающем порядке. Во время пересылок, алгоритм сортировки определяет какой элемент из двух меньше, какой больше (1<2 или 2>1) и меняет их в возрастающем порядке – это называется сравнения.

    В самое ближайшее время Вам нужно будет понимать, что за обозначение О(n). Это единица измерения, определяющая кол-во пересылок M или сравнений C. Понимать её стоит так,
    M = O(n) – для того, чтобы алгоритм сортировки отсортировал числа в последовательности, потребуется, не больше n пересылок.
    C=O(n) тоже самое, только для сравнений.
    Ниже, будем обозначать кол-во чисел (элементов) в последовательности или массиве как n.

    Переработал текст, новички должны понять )
     
    2 people like this.
  2. UnPazz

    UnPazz Elder - Старейшина

    Joined:
    30 Aug 2008
    Messages:
    96
    Likes Received:
    43
    Reputations:
    6
    Урок 2. Простые (квадратичные) методы сортировки чисел.

    Метод прямого выбора
    Метод прямого выбора, самый простой. Суть : находим наименьший элемент массива и обмениваем его с первым элементом массива. После этого, первый элемент больше не рассматриваем. Среди оставшихся элементов находим наименьший элемент и обмениваем его со вторым элементом массива. Среди оставшихся элементов находим наименьший и переставляем его на третье место и так далее.

    Например, наш массив состоит из n чисел.
    Количество M = 3*(n-1), а C = (n*n-n)/2. Метод не зависит от исходной отсортированности массива, т.е. значения М и С не меняются, даже если сортируется уже отсортированный массив. Сортировка методом прямого выбора неустойчива.

    Приводится код на Паскале. Количество M и C считается, чтобы Вам было все понятно.


    Вывод : метод самый простой. Кол-во пересылок не меняется сортировке любого массива, т.е. он «тупо» сортирует все и даже где не нужно делает сравнения и пересылки. При сортировке любого (упорядоченного/неупорядоченного) массива из 100 чисел получим M=297, C=4950.


    Пузырьковая сортировка​
    Просматриваем элементы от конца массива к началу, сравниваем между собой соседние элементы. Если правый элемент aj будет меньше чем левый aj-1, j=n, n-1, … ,2, то поменяем их местами. После этого, при первом проходе наименьший элемент переместится на первое место и можно не учитывать его при сортировке оставшейся части массива. При втором проходе наименьший элемент из оставшихся перейдет на второе место. После (n-1) проходов массив отсортируется.

    Количество C = (n*n-n)/2 (равно кол-ву сравнений в методе прямого выбора), количество пересылок будет меньше : если сортируем уже упорядоченный по возрастанию массив, то M = 0; если сортируем упорядоченный по убыванию, то M=3*(n*n-n)/2.

    Вывод : метод зависит от начальной упорядоченности массива, а это уже плюс, по сравнению с методом Прямого выбора. Для случайного массива, получим M = 7977 и C = 4950, для упорядоченного M=0 и C = 4950. При сортировке упорядоченного массива уже прогресс – кол-во пересылок намного меньше.


    Шейкерная сортировка​

    Теперь немного проанализируем. Возьмем метод Пузырьковой сортировки.
    1) Если при движении по части массива перестановки не происходят, то эта часть массива уже отсортирована, получается мы ее можем исключить из рассмотрения.
    2) Также, при движении от конца массива к началу минимальный элемент переходит на первую позицию, а максимальный элемент сдвигается только на одну позицию вправо.
    Т.е. можно немного модифицировать метод пузырьковой сортировки. А именно, границы рабочей части массива (часть массива, к которой происходит сортировка и M и C) устанавливаются в месте последнего обмена на каждом проходе. Массив просматривается поочередно справа налево и слева направо.

    Количество пересылок если сортируем уже упорядоченный по возрастанию массив, то M = 0; если сортируем упорядоченный по убыванию, то M=3*(n*n-n)/2. Количество сравнений : если массив отсортирован перед сортировкой в возрастающем порядке, то C = n-1; если в убывающем, C = (n*n-n)/2.
    При сортировке упорядоченного по возрастанию массива (100 элементов) получим M = 0 и C=99 , для случайног M = 6579 и C = 3142.

    Вывод : метод ещё более совершенен по сравнению с двумя первыми.


    В алгоритмах, нужно дописать, только ввод массива, вывод его на экран и вывод M и C.
     
  3. NorB

    NorB Elder - Старейшина

    Joined:
    20 Jul 2007
    Messages:
    109
    Likes Received:
    12
    Reputations:
    -2
    0_о в учебниках везде такое есть зачем тут еше писать...
     
    1 person likes this.
  4. desTiny

    desTiny Elder - Старейшина

    Joined:
    4 Feb 2007
    Messages:
    1,005
    Likes Received:
    444
    Reputations:
    94
    а нахрена? где сортировки за n log n? Где за линейное время? Писать, так целиком. Да и всё равно нах не нужно...

    Я не знаю алгоритмов, которым на это понадобится даже 2 секунды.


    PS А у Кнута на сортировки целая книжка ушла!
     
    #4 desTiny, 14 Sep 2008
    Last edited: 14 Sep 2008
    1 person likes this.
  5. astrologer

    astrologer Elder - Старейшина

    Joined:
    30 Aug 2007
    Messages:
    837
    Likes Received:
    267
    Reputations:
    59
    1 person likes this.
  6. Dr.Jekill

    Dr.Jekill New Member

    Joined:
    4 Nov 2009
    Messages:
    13
    Likes Received:
    0
    Reputations:
    0
    Есть ошибки.
     
  7. Thenno

    Thenno Member

    Joined:
    3 Jul 2009
    Messages:
    77
    Likes Received:
    21
    Reputations:
    0
    Я уже как-то предлагал (месяца 2 назад) написать статью на подобную тему, но товарищ desTiny меня от этого отговорил (за что я ему благодарен, честно). В принципе, неплохо, но есть один серьезный (для меня) недостаток - вообще не оформлен исходный код, читать такое практическе нереально.
    Думаю, что подобную штуку надо закончить ссылкой на нормальную литературу по теме (тот же Кнут), ибо тянет она лишь на "средство для пробуждения желания у новоиспеченных адептов программирования ознакомится с темой подробнее".
     
  8. Gar|k

    Gar|k Moderator

    Joined:
    20 Mar 2009
    Messages:
    1,166
    Likes Received:
    266
    Reputations:
    82
    форум (или раздел, честно в остальные даже страшно заходить такой тупизм) превращается не в хакерский форум и уже давно не в поделись с собратом кодом и даже не в помоги ламеру, а в научи нуба программированию )

    скоро похоже он будет полезен только девочкам первокурсницам с кафедры прикладной информатики....
     
    _________________________
  9. Thenno

    Thenno Member

    Joined:
    3 Jul 2009
    Messages:
    77
    Likes Received:
    21
    Reputations:
    0
    Так всегда бывает со всеми форумами :) Но я все такие бы так не сказал пока насчет Ачата, тут "поделись с собратом кодом" еще встречается довольно часто.
     
  10. XimiK69

    XimiK69 Member

    Joined:
    2 Jan 2010
    Messages:
    45
    Likes Received:
    5
    Reputations:
    0
    хорошо о сортировках расписано в книге Кнут........
     
Loading...