Quick Sort Algorithm | Python Programming Tutorial

Introduction

Quick Sort is a popular sorting algorithm that uses a divide-and-conquer approach to sort an array or a list. It is a comparison-based algorithm that works by partitioning an array into two sub-arrays, then recursively sorting the sub-arrays. Quick Sort is widely used because of its efficiency and simplicity.

Skills Graph

%%%%{init: {'theme':'neutral'}}%%%% flowchart RL python(("`Python`")) -.-> python/BasicConceptsGroup(["`Basic Concepts`"]) algorithm(("`Algorithm`")) -.-> algorithm/BasicAlgorithmsGroup(["`Basic Algorithms`"]) python(("`Python`")) -.-> python/ControlFlowGroup(["`Control Flow`"]) python(("`Python`")) -.-> python/DataStructuresGroup(["`Data Structures`"]) python(("`Python`")) -.-> python/FunctionsGroup(["`Functions`"]) python(("`Python`")) -.-> python/ObjectOrientedProgrammingGroup(["`Object-Oriented Programming`"]) python(("`Python`")) -.-> python/ErrorandExceptionHandlingGroup(["`Error and Exception Handling`"]) python/BasicConceptsGroup -.-> python/comments("`Comments`") algorithm/BasicAlgorithmsGroup -.-> algorithm/sorting_searching("`Sorting Searching`") python/ControlFlowGroup -.-> python/conditional_statements("`Conditional Statements`") python/ControlFlowGroup -.-> python/for_loops("`For Loops`") python/DataStructuresGroup -.-> python/lists("`Lists`") python/DataStructuresGroup -.-> python/tuples("`Tuples`") python/FunctionsGroup -.-> python/function_definition("`Function Definition`") python/ObjectOrientedProgrammingGroup -.-> python/classes_objects("`Classes and Objects`") python/ObjectOrientedProgrammingGroup -.-> python/encapsulation("`Encapsulation`") python/ErrorandExceptionHandlingGroup -.-> python/raising_exceptions("`Raising Exceptions`") python/FunctionsGroup -.-> python/build_in_functions("`Build-in Functions`") subgraph Lab Skills python/comments -.-> lab-268878{{"`Efficient Quick Sort Algorithm`"}} algorithm/sorting_searching -.-> lab-268878{{"`Efficient Quick Sort Algorithm`"}} python/conditional_statements -.-> lab-268878{{"`Efficient Quick Sort Algorithm`"}} python/for_loops -.-> lab-268878{{"`Efficient Quick Sort Algorithm`"}} python/lists -.-> lab-268878{{"`Efficient Quick Sort Algorithm`"}} python/tuples -.-> lab-268878{{"`Efficient Quick Sort Algorithm`"}} python/function_definition -.-> lab-268878{{"`Efficient Quick Sort Algorithm`"}} python/classes_objects -.-> lab-268878{{"`Efficient Quick Sort Algorithm`"}} python/encapsulation -.-> lab-268878{{"`Efficient Quick Sort Algorithm`"}} python/raising_exceptions -.-> lab-268878{{"`Efficient Quick Sort Algorithm`"}} python/build_in_functions -.-> lab-268878{{"`Efficient Quick Sort Algorithm`"}} end

Quick Sort

Problem

Implement Quick Sort algorithm in Python. The algorithm should take an unsorted list as input and return a sorted list. The algorithm should work for lists of any size, including empty lists and lists with duplicate elements. The algorithm should also handle invalid input gracefully.

The Quick Sort algorithm works as follows:

Choose a pivot element from the list.
Partition the list into two sub-lists: one with elements less than the pivot, and one with elements greater than the pivot.
Recursively apply the Quick Sort algorithm to the sub-lists.
Concatenate the sorted sub-lists with the pivot element in the middle.

Requirements

To implement Quick Sort algorithm in Python, the following requirements should be met:

The algorithm should not be an in-place solution.
The algorithm should handle duplicate elements in the list.
The algorithm should handle invalid input, such as None or non-list input.
The algorithm should be able to handle lists of any size, including empty lists.

Example Usage

The following are some examples of how to use the Quick Sort algorithm in Python:

None -> Exception

quick_sort(None)

Empty input -> []

quick_sort([])

One element -> [element]

quick_sort([5])

Two or more elements

quick_sort([5, 2, 8, 3, 1, 9])

Summary

Quick Sort is a popular sorting algorithm that uses a divide-and-conquer approach to sort an array or a list. The algorithm works by partitioning the list into two sub-lists, then recursively sorting the sub-lists. The Quick Sort algorithm is efficient and simple, making it widely used. To implement Quick Sort in Python, the algorithm should meet the requirements of not being an in-place solution, handling duplicate elements, handling invalid input, and being able to handle lists of any size.

Efficient Quick Sort Algorithm