[go: up one dir, main page]
Scribd
Upload
35 views2 pages

Quick Sort

Quick Sort is an efficient divide-and-conquer sorting algorithm developed by Tony Hoare in 1959, known for its average-case performance and in-place sorting capability. It works by recursively partitioning an array around a pivot element, ensuring elements are sorted relative to the pivot. The algorithm has a time complexity of O(n log n) in the best and average cases, and O(n²) in the worst case, with a space complexity of O(log n).

Uploaded by

Subhadip Das
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
35 views2 pages

Quick Sort

Quick Sort is an efficient divide-and-conquer sorting algorithm developed by Tony Hoare in 1959, known for its average-case performance and in-place sorting capability. It works by recursively partitioning an array around a pivot element, ensuring elements are sorted relative to the pivot. The algorithm has a time complexity of O(n log n) in the best and average cases, and O(n²) in the worst case, with a space complexity of O(log n).

Uploaded by

Subhadip Das
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

Quick Sort – Report

1. Introduction

Quick Sort is a highly efficient divide-and-conquer sorting algorithm developed by Tony Hoare in
1959. It is widely used due to its superior average-case performance and in-place sorting
capability.

2. Purpose

Quick Sort is designed to sort elements efficiently by recursively partitioning the array around a
pivot element, ensuring elements less than the pivot come before it and elements greater come
after.

3. How It Works

Quick Sort works in the following steps:

1. Choose a pivot element from the array (commonly first, last, middle, or random).

2. Partition the array:

o Rearrange the elements so that all elements smaller than the pivot are on the left,
and all greater are on the right.

3. Recursively apply the above steps to the sub-arrays (left and right of the pivot).

4. Algorithm (Pseudocode)

plaintext

CopyEdit

function quickSort(arr, low, high)

if low < high:

pi = partition(arr, low, high)

quickSort(arr, low, pi - 1)

quickSort(arr, pi + 1, high)

function partition(arr, low, high)

pivot = arr[high]

i = low - 1

for j = low to high - 1:

if arr[j] < pivot:


i += 1

swap arr[i] and arr[j]

swap arr[i + 1] and arr[high]

return i + 1

5. Time and Space Complexity

Case Time Complexity

Best Case O(n log n)

Average Case O(n log n)

Worst Case O(n²) (when pivot is always the largest or smallest)

• Space Complexity: O(log n) due to recursive stack (in-place sorting).

6. Example

For array [10, 7, 8, 9, 1, 5]:

• Choose pivot = 5

• Partition: [1] [5] [10, 7, 8, 9]

• Recursively sort [1] and [10, 7, 8, 9]

• Final result: [1, 5, 7, 8, 9, 10]

You might also like