FUTURE INSTITUE OF TECHNOLOGY

240, Garia Boral Main Road, Kolkata - 700154 West Bengal

(Affiliated To MAKAUT)

Detailed Report on

ubmitted as CA2 in
Subject Name (Subject
Code)
for
the partial fulfillment of
B. Tech in
Mechanical Engineering
ubmitted as CA2 in
Subject Name (Subject
Code)
for
the partial fulfillment of
B. Tech in
Mechanical Engineering
Quick Sort

Submitted as CA2 in

Design and Analysis of Algorithm

(PCCCS404)

for

the partial fulfilment of

B. Tech in

Computer Science and Engineering (AI & ML)

Submitted by:

Eshika Giri

(34230822009)

Submitted on: 16th of March, 2024

Index
1. Abstract 3
2. Introduction 3
3. Methods
a. Algorithm 4
b. Visual Illustration of Quicksort Algorithm 5
c. Implementation 6
d. Output 8
e. Description 8
f. Time Complexity 9
4. Discussion
a. Advantages 10
b. Disadvantages 11
c. Applications 11
5. Conclusion 11
6. References 12
Abstract
This comprehensive report delves into the intricacies of the Quick Sort algorithm, a pivotal
method in the realm of sorting algorithms renowned for its efficiency and practicality.
Beginning with an introduction to sorting algorithms and the significance of Quick Sort, the
report progresses to explore its algorithmic intricacies, implementation details, nuanced
outputs, followed by a thorough discussion on its advantages, disadvantages, and wide-
ranging applications. Finally, the report concludes with a reflection on the significance of
Quick Sort in computer science and references to further scholarly works.

Introduction
Sorting algorithms serve as the bedrock of computer science, underpinning countless
computational tasks by arranging data in an ordered sequence for efficient retrieval, analysis,
and manipulation. From simple lists to complex data structures, the ability to organize
information in a systematic manner is indispensable across various domains, including
database management, information retrieval, and algorithmic problem-solving.

Among the plethora of sorting algorithms that have been devised over the years, Quick Sort
occupies a preeminent position, celebrated for its exceptional efficiency and elegance.
Originating from the seminal work of Tony Hoare in 1960, Quick Sort has garnered
widespread recognition and adoption due to its favorable average-case time complexity of
O(n log n) and its ability to outperform many other sorting algorithms in practice.

The significance of sorting algorithms like Quick Sort extends beyond mere data
organization; it embodies the quintessence of algorithmic design principles, efficiency
optimization, and algorithm analysis. As computer scientists grapple with ever-expanding
datasets and computational challenges, the quest for sorting algorithms that strike a balance
between speed, space efficiency, and simplicity remains a perennial pursuit.

In this report, we embark on an in-depth exploration of the Quick Sort algorithm, unraveling
its inner workings, discussing its implementation intricacies, evaluating its performance
characteristics, and elucidating its applications across diverse computational domains. By
dissecting Quick Sort from various angles, we aim to provide a comprehensive understanding
of its functionality, strengths, weaknesses, and real-world relevance in the landscape of
computer science. Through this endeavor, we endeavor to shed light on the enduring
significance of Quick Sort as a fundamental tool in the arsenal of computational techniques,
shaping the way data is processed, analyzed, and utilized in the digital age.
Methods

Algorithm
The Quick Sort algorithm operates by selecting a 'pivot' element from the array and
partitioning the remaining elements into two sub-arrays based on whether they are lesser or
greater than the pivot. This partitioning process is recursively applied to the sub-arrays until
the entire array is sorted.

Below are the steps involved in the Quick Sort algorithm:

1. Choose a Pivot: The first step in Quick Sort is to select a pivot element from the
array. The pivot can be chosen in various ways, but commonly it is the first element,
last element, or a randomly selected element from the array.

Fig. [1] Choosing a pivot

2. Partitioning: Once the pivot is chosen, the next step is to partition the array around
the pivot. This partitioning process rearranges the elements of the array such that all
elements less than the pivot are moved to the left side of the pivot, and all elements
greater than the pivot are moved to the right side. At the end of this step, the pivot
element is in its final sorted position.

3. Recursion: After partitioning, the array is divided into two sub-arrays based on the
position of the pivot. One sub-array consists of elements less than the pivot, while the
other sub-array contains elements greater than the pivot. Recursive calls are made to
apply the same partitioning process to each sub-array until the entire array is sorted.

4. Base Case: The recursion terminates when the sub-arrays become sufficiently small,
typically when they contain zero or one element. Arrays of one or fewer elements are
considered sorted by definition.
 5. Combine: As the recursion unwinds, the sorted sub-arrays are combined to produce
the final sorted array. This combination involves concatenating the sorted sub-arrays
around the pivot in sorted order.

By following these steps recursively, Quick Sort efficiently sorts the entire array in ascending
or descending order. The effectiveness of Quick Sort lies in its ability to partition the array
efficiently around the chosen pivot, reducing the number of comparisons and swaps required
to achieve the final sorted arrangement. Additionally, the use of recursion allows Quick Sort
to handle large datasets with relatively low memory overhead. However, the choice of pivot
and the partitioning strategy can significantly influence the algorithm's performance,
especially in edge cases where the array is already sorted or contains many duplicate
elements.

Visual Illustration of Quicksort Algorithm

We can understand the working of quicksort algorithm with the help of the illustrations
below.

Fig. [2] Sorting the elements on

the
Fig.right of pivotthe
[3] Sorting using recursion
elements on
the right of pivot using recursion

Implementation
To write a 'quickSort' method that splits the array into shorter and shorter sub-arrays we use
recursion. This means that the 'quickSort' method must call itself with the new sub-arrays to
the left and right of the pivot element. Read more about recursion here.

To implement the Quicksort algorithm in a programming language, we need:

1. An array with values to sort.

2. A quickSort method that calls itself (recursion) if the sub-array has a size larger than
1.

3. A partition method that receives a sub-array, moves values around, swaps the pivot
element into the sub-array and returns the index where the next split in sub-arrays
happens.

The resulting code looks like this:

Quicksort Algorithm

QUICKSORT (array A, start, end)

{
1. if (start < end)
2. {
3. p = partition(A, start, end)
4. QUICKSORT (A, start, p - 1)
5. QUICKSORT (A, p + 1, end)
6. }
}

Partition Algorithm

The partition algorithm rearranges the sub-arrays in a place.

PARTITION (array A, start, end)

{
1. pivot ? A[end]
 2. i ? start-1
3. for j ? start to end -1 {
4. do if (A[j] < pivot) {
5. then i ? i + 1
6. swap A[i] with A[j]
7. }}
8. swap A[i+1] with A[end]
9. return i+1
}

Output
The output generated from entering eight numbers:

Description
1. Initial Array: The initial array before sorting is [64, 34, 25, 12, 22, 11, 90, 5].

2. Partitioning:

 The partition function selects the pivot element, which in this case is the last
element, 5.
  The array is partitioned such that elements less than or equal to the pivot (5)
are moved to its left, and elements greater than the pivot are moved to its right.

 After partitioning, the pivot element (5) is in its correct sorted position.

 The partitioned array now looks like [5, 34, 25, 12, 22, 11, 90, 64].

3. Recursive Calls:

 The quicksort function is recursively called on the sub-arrays to the left and
right of the pivot.

 For the left sub-array [5, 34, 25, 12, 22, 11], the process is repeated, resulting
in the pivot element 5 staying in its position.

 For the right sub-array [34, 25, 12, 22, 11, 90, 64], the partitioning process is
applied, resulting in the pivot element 64 staying in its position.

 The recursion continues until all sub-arrays are sorted.

4. Combining Results:

 As the recursion unwinds, the sorted sub-arrays are combined around their
respective pivot elements to produce the final sorted array.

 After all recursive calls are completed, the sorted array is [5, 11, 12, 22, 25,
34, 64, 90].

5. Output:

 The sorted array [5, 11, 12, 22, 25, 34, 64, 90] is printed as the output of the
program.

Quicksort Time Complexity

The time complexity of Quick Sort is typically described in terms of its average-case, best-
case, and worst-case scenarios.

1. Average-Case Time Complexity: The average-case time complexity of Quick Sort is

O(n log n), where n is the number of elements in the array. This means that, on
average, the algorithm takes proportional to n log n time to sort an array of n
elements.
 2. Best-Case Time Complexity: The best-case time complexity of Quick Sort occurs
when the pivot elements divide the array into roughly equal halves during each
partitioning step. In this scenario, the algorithm exhibits its best performance, and the
time complexity is O(n log n).

3. Worst-Case Time Complexity: The worst-case time complexity of Quick Sort is

O(n^2). This occurs when the pivot selection consistently results in unbalanced
partitions, such as selecting the smallest or largest element as the pivot in a sorted or
nearly sorted array. In such cases, Quick Sort degrades to quadratic time complexity,
which can be inefficient for large
datasets. Fig. [4] Time complexity for Quicksort

Overall, Quick Sort's average and best-case time complexities make it a highly efficient
sorting algorithm for most practical scenarios, but its worst-case time complexity highlights
the importance of pivot selection strategies to ensure optimal performance. Additionally,
randomized pivot selection or median-of-three pivot selection can mitigate the likelihood of
encountering the worst-case scenario, further enhancing the algorithm's efficiency.

The recursion part of the Quicksort algorithm is actually a reason why the average sorting
scenario is so fast, because for good picks of the pivot element, the array will be split in half
somewhat evenly each time the algorithm calls itself. So, the number of recursive calls do not
double, even if the number of values n double.
Discussion

Advantages
1. Efficiency: Quick Sort is highly efficient, especially for large datasets, with an
average time complexity of O(n log n). This makes it one of the fastest sorting
algorithms in practice.

2. In-Place Sorting: Quick Sort sorts the elements within the array itself, requiring only
a constant amount of additional memory space. This makes it memory-efficient and
suitable for applications with limited memory resources.

3. Widely Implemented: Quick Sort is supported and implemented in many

programming languages and libraries, making it easily accessible and practical for
developers across different platforms.

4. Adaptive: Quick Sort's performance adapts well to the characteristics of the input
data, particularly when the data is nearly sorted or contains a small range of values.

Disadvantages
1. Worst-Case Complexity: In its basic form, Quick Sort may exhibit poor performance
in the worst-case scenario, particularly when the pivot selection results in unbalanced
partitioning. This can lead to a worst-case time complexity of O(n^2), although this
scenario is rare with randomized pivot selection or careful implementation.

2. Lack of Stability: Quick Sort is not a stable sorting algorithm, meaning the relative
order of equal elements may not be preserved after sorting. This can be a drawback in
applications where maintaining the original order of equal elements is important.

3. Dependency on Pivot Selection: The choice of pivot element significantly impacts

the efficiency of Quick Sort. Poorly chosen pivots can lead to inefficient partitioning
and degrade the algorithm's performance.

Applications
1. Sorting Large Datasets: Quick Sort is widely used in applications that require
sorting large datasets efficiently, such as database management systems, search
algorithms, and data processing pipelines.
 2. Real-Time Systems: Its speed and efficiency make Quick Sort suitable for real-time
systems, including financial trading platforms, where fast processing of streaming
data is essential.

3. Programming Libraries: Quick Sort is commonly employed as a default sorting

algorithm in programming libraries and languages due to its speed and ease of
implementation.

4. External Sorting: Quick Sort's ability to efficiently handle large datasets with limited
memory overhead makes it suitable for external sorting applications, such as sorting
large files that cannot fit entirely into memory.

5. Parallel Computing: Quick Sort can be parallelized efficiently, allowing it to take

advantage of multi-core processors and distributed computing environments to further
enhance its performance on large-scale datasets.

Conclusion
In the world of sorting algorithms, Quick Sort reigns supreme, known for its lightning-fast
speed and widespread use. After delving into its inner workings, practical applications, and
performance characteristics, it's clear that Quick Sort is a powerhouse in the realm of
computer science.

Quick Sort's greatest strength lies in its ability to rapidly sort large datasets, thanks to its
average-case time complexity of O(n log n). Its knack for sorting in-place with minimal
memory requirements makes it a favorite among developers tackling big data challenges.

However, Quick Sort isn't without its flaws. In certain cases, especially when the pivot
selection goes awry, it can slow down significantly, showcasing its worst-case time
complexity of O(n^2).

Despite its imperfections, Quick Sort remains a go-to solution across various fields, from
managing databases to powering real-time systems. Its speed, simplicity, and widespread
support make it an indispensable tool in the toolkit of any programmer.

As we wrap up our exploration of Quick Sort, it's clear that its impact extends far beyond
mere sorting. It symbolizes the spirit of efficiency and innovation in computer science,
paving the way for countless applications and advancements in technology.

References
The following reference links were consulted to gather additional insights and information for
this report, enriching the analysis and providing a comprehensive understanding of the topic.

 https://www.w3schools.com/dsa/dsa_algo_quicksort.php
 https://www.javatpoint.com/quick-sort
 https://www.geeksforgeeks.org/quick-sort/
 https://www.programiz.com/dsa/quick-sort