Quicksort

Quicksort

Quicksort is a recursive algorithm that sorts n items by selecting a random item r, separating the other items into those that precede r and those that succeed r, and calling itself recursively on those two subsets. The idea behind quicksort is to recursively split the unsorted array into two parts that can be sorted independently. The classical quick sort works by selecting a pivot element from all the original elements and partitioning the other elements into two subsets (those are larger and those are smaller than the pivot element), and then recursively sorting these two subsets. Although quicksort has a worst-case running time of O(n²), it is typically O(n log n).From: Linear Optimization and Duality [2020], Statistical Computing in C++ and R [2011], Adaptive Order-of-Addition Experiments via the Quick-Sort Algorithm [2023], Roadmap to Greener Computing [2019]

Introduction

View Chapter

Purchase Book

Published in Randall L. Eubank, Ana Kupresanin, Statistical Computing in C++ and R, 2011

Randall L. Eubank, Ana Kupresanin

The idea behind quicksort is simple: recursively split the unsorted array into two parts that can be sorted independently. The easiest way to achieve this is to ensure that each value in the first part is no greater than any in the second part. This is perhaps best illustrated with a specific example. For that purpose consider the following unordered collection of integers. 1511828271949386240

Adaptive Order-of-Addition Experiments via the Quick-Sort Algorithm

View Article

Journal Information

Published in Technometrics, 2023

Dennis K. J. Lin, Jianbin Chen

The classical quick sort works by selecting a pivot element from all the original elements and partitioning the other elements into two subsets (those are larger and those are smaller than the pivot element), and then recursively sorting these two subsets. Motivated by the basic idea of quick sort, the proposed methodology divides the all components into two subsets: the left subset contains those components which are preceded by the pivot component, and the right subset contains those components which are behind the pivot component. Recursively applying the method to these two subsets, the optimal order can then be obtained by combining all optimal subsets together. The procedure of the proposed method is presented in Algorithm 1, with an illustrative example in Section 3.

Explore chapters and articles related to this topic

Introduction

Adaptive Order-of-Addition Experiments via the Quick-Sort Algorithm