D04.8. Pros and Cons of the QuickSort?

[yazhezhuk]

D04.8. Pros and Cons of the QuickSort? D04.8. Переваги та недоліки Quicksort?

[yazhezhuk]

Обговорення на лекції: Переваги

• швидко працює,
• вимагає небагато додаткової пам'яті,
• нескладний в реалізації
• достатньо простий для розуміння

Недоліки

• не стабільний,
• в гіршому випадку працює за O(n^2) – вразливий
• можливість переповнення стека при малій кількості елементів більш примітивні алгоритми будуть працювати швидше

Discussed on lection: Pros

• high sorting speed
• have little additional memory requierments
• easy to implement
• clear enough to understand

Cons

• unstable
• in worst case working for O(n^2) - unstable
• there are a chance of stack overflow while working with low amount of elements so more primitive algorithms will work faster in this case.

[yazhezhuk]

Обговорення з попередніх років: Переваги

• Швидкість
• Мало пам’яті
• Простота

Недоліки

• Нестабільність
• Неадаптивний

Disscused on previous year: Pros

• high sorting speed
• have little additional memory requierments
• simplicity

Cons

• unstable
• non-adaptive

[glbter]

Переваги

• є можливість stream-out Недоліки
• в залежності від алгоритму вибору елементу для порівняння, алгоритм сортування може працювати гірше, або навіть уйти в рекусію без результату

[LavorM]

Серед плюсів можна додати, що його доволі легко розпалалелити (паралельно виконувати сортування підмасивів в паралельниї підпроцесах) (в java наприклад цей алгоритм можна розділити на кілька тредів і він працюватиме еффективніше (https://docs.oracle.com/javase/7/docs/api/java/lang/Thread.html)), також при правильній реалізації цих структур може також ефективно працювати зі списками

[Edward3635]

Переваги:

Один з самих швидкодіючих (на практиці) з алгоритмів внутрішнього сортування загального призначення. Простий в реалізації. Вимагає лише O (\ lg n) додаткової пам'яті для своєї роботи. (Не покращений рекурсивний алгоритм в гіршому випадку O (n) пам'яті) Добре поєднується з механізмами кешування і віртуальної пам'яті. Існує ефективна модифікація (алгоритм Седжвіка) для сортування рядків - спочатку порівняння з опорним елементом тільки по нульовому символу рядка, далі застосування аналогічної сортування для "більшого" і "меншого" масивів теж по нульовому символу, і для "рівного" масиву по вже першого символу. Працює на пов'язаних списках та інших структурах з послідовним доступом. Недоліки:

Сильно деградує по швидкості (до \ Theta (n ^ 2) ) При невдалих виборах опорних елементів, що може трапитися при невдалих вхідних даних. Цього можна уникнути, використовуючи такі модифікації алгоритму, як Introsort, або ймовірносно, вибираючи опорний елемент випадково, а не фіксованим чином. Наївна реалізація алгоритму може привести до помилки переповнення стека, так як їй може знадобитися зробити O (n) вкладених рекурсивних викликів. У покращених реалізаціях, в яких рекурсивний виклик відбувається тільки для сортування меншою з двох частин масиву, глибина рекурсії гарантовано не перевищить O (\ lg n) . Нестійкий - якщо потрібна стійкість, доводиться розширювати ключ.

[ZinchenkoArtem1]

The quicksort algorithm partitions an array of data into items that are less than the pivot and those that are greater than or equal to the pivot item. The first step is to create the partitions, in which a random pivot item is created, and the partition algorithm is applied to the array of items. This initial step is the most difficult part of the quicksort algorithm. The basic idea of the partitioning is that there are three regions: S1, S2, and the unknown. Each item from the unknown is placed into the appropriate region. Then the pivot is moved in between the two regions. The recursive quicksort algorithm works by applying the partition algorithm to each previously created partition until the entire array is sorted. Advantages include the efficient average case compared to any aforementioned sort algorithm, as well as the elegant recusrive definition, and the popularity due to its high efficiency. Disadvantages include the difficulty of implementing the partitioning algorithm and the average efficiency for the worst case scenario, which is not offset by the difficult implementation.

[DmytroTarasov]

I want to add that quicksort uses an approach Divide and Conquer. Pros: When implemented well, it can be two or three times faster than, for example, mergesort or heapsort. Google's V8 uses quicksort for arrays larger than 10. Cons: It doesn't guarantee O(n*log n) every time unlike mergesort.

[khilchuk-ol]

Варто також зазначити, що бажано перед самим сортуванням "перемішати" елементи, так можна отримати кращу ефективність. Також, якщо при розбитті масивів на частини по опорному елементу (partitioning) ті, що еквівалентні опорному не відділяються окремо, то для вхідних даних із великою кількістю дублікатів алгоритм працює із квадратичною складністю.