Data Structure Laboratory
Experiment no.8
Title
Implementation of the Quick Sort Algorithm to Sort Floating-Point Student Scores.
Objective
To implement the Quick Sort algorithm using Python to efficiently sort an array of floating-point
student scores in ascending order, demonstrating proficiency in the divide-and-conquer sorting
technique.
Problem Statement
The university needs to efficiently sort floating-point student scores (out of 100) from a
programming exam to publish a ranked list. Write a program to sort an array of these scores in
ascending order using the Quick Sort algorithm.
Theory Concept in Brief
Quick Sort is a highly efficient, comparison-based, in-place sorting algorithm that follows the
divide-and-conquer paradigm. It works by selecting a pivot element from the array and
partitioning the other elements into two sub-arrays: those less than the pivot and those greater
than the pivot. The pivot is then placed in its final sorted position. The process is applied
recursively to the sub-arrays until the entire array is sorted. Its performance is generally fast,
with an average time complexity of O(n \log n). The algorithm's efficiency depends heavily on
the pivot selection, with a poor choice leading to a worst-case complexity of O(n^2).
Algorithm
* QUICKSORT(array, low, high):
a. If low < high:
i. pi \leftarrow \text{PARTITION}(\text{array}, low, high)
ii. \text{QUICKSORT}(\text{array}, low, pi - 1)
iii. \text{QUICKSORT}(\text{array}, pi + 1, high)
* PARTITION(array, low, high):
a. Select the pivot (e.g., \text{array}[high]).
b. Initialize i \leftarrow low - 1.
c. For j from low to high - 1:
i. If \text{array}[j] \le \text{pivot}, increment i and swap \text{array}[i] and \text{array}[j].
d. Swap \text{array}[i + 1] and \text{array}[high].
e. Return i + 1.
Code (Python)
# Function to perform the partitioning of the array
def partition(arr, low, high):
pivot = arr[high] # Pivot is the rightmost element
i = low - 1 # Index of the smaller element
for j in range(low, high):
if arr[j] <= pivot:
i=i+1
# Swap arr[i] and arr[j]
arr[i], arr[j] = arr[j], arr[i]
# Swap the pivot element with the element at i+1
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1
# Main function to implement Quick Sort
def quick_sort(arr, low, high):
if low < high:
# pi is the partitioning index
pi = partition(arr, low, high)
# Recursively sort the sub-arrays
quick_sort(arr, low, pi - 1)
quick_sort(arr, pi + 1, high)
# Floating-point student scores for demonstration
scores = [85.5, 92.0, 67.25, 78.5, 99.0, 55.0, 88.75, 70.0, 92.0]
n = len(scores)
print("Original Scores:", scores)
quick_sort(scores, 0, n - 1)
print("Sorted Scores:", scores)
Output
Original Scores: [85.5, 92.0, 67.25, 78.5, 99.0, 55.0, 88.75, 70.0, 92.0]
Sorted Scores: [55.0, 67.25, 70.0, 78.5, 85.5, 88.75, 92.0, 92.0, 99.0]
Conclusion
The experiment successfully implemented the Quick Sort algorithm in Python to sort an array of
floating-point student scores. The program efficiently arranged the scores in ascending order
using the recursive, divide-and-conquer approach, fulfilling the requirement for publishing a
ranked list. The implementation demonstrated the effective use of the partitioning strategy to
place the pivot element in its correct sorted position, confirming the average-case O(n \log n)
efficiency for practical sorting tasks.