The Partition Subroutine: Difference between revisions
Jump to navigation
Jump to search
| Line 1: | Line 1: | ||
=Internal= | =Internal= | ||
* [[Algorithms#Partitioning|Algorithms]] | * [[Algorithms#Partitioning|Algorithms]] | ||
= | =Problem Statement= | ||
The partition subroutine is an essential part of the [[Quicksort]] algorithm. | Given an array and an element of it - the pivot element - rearrange the array so it has the following property: any element that is at the left of the pivot should be smaller or equal with the pivot, and any element that is at the right of the pivot should be grater that the pivot. | ||
=Discussion= | |||
After partitioning, the pivot element ends up in its rightful position in the (eventually) sorted array. The implementation is linear time and in-place. The partition subroutine is an essential part of the [[Quicksort]] algorithm. | |||
Revision as of 22:54, 21 September 2021
Internal
Problem Statement
Given an array and an element of it - the pivot element - rearrange the array so it has the following property: any element that is at the left of the pivot should be smaller or equal with the pivot, and any element that is at the right of the pivot should be grater that the pivot.
Discussion
After partitioning, the pivot element ends up in its rightful position in the (eventually) sorted array. The implementation is linear time and in-place. The partition subroutine is an essential part of the Quicksort algorithm.