🎓 Top 15 Udemy Courses (80-90% Discount): My Udemy Courses - Ramesh Fadatare — All my Udemy courses are real-time and project oriented courses.
▶️ Subscribe to My YouTube Channel (178K+ subscribers): Java Guides on YouTube
▶️ For AI, ChatGPT, Web, Tech, and Generative AI, subscribe to another channel: Ramesh Fadatare on YouTube
1. Introduction
In this blog post, we will learn how to write a Python program to implement Quick Sort on a list.
Quick Sort is a popular and efficient divide-and-conquer sorting algorithm that works by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then sorted recursively.
2. Program Overview
In this program, we will:
1. Define a function to partition the array.
2. Define the main quickSort function that selects a pivot, partitions the array, and then recursively sorts the two sub-arrays.
3. Test the quick sort implementation on a sample list.
3. Code Program
def quickSort(arr):
# Base case: If the array has one or zero elements, it's already sorted.
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
# Recursively sort the left and right half and combine them with the middle (pivot)
return quickSort(left) + middle + quickSort(right)
# Test the function
arr = [38, 27, 43, 3, 9, 82, 10]
sorted_arr = quickSort(arr)
print("Original Array:", arr)
print("Sorted Array:", sorted_arr)
Output:
Original Array: [38, 27, 43, 3, 9, 82, 10] Sorted Array: [3, 9, 10, 27, 38, 43, 82]
4. Step By Step Explanation
1. A pivot element is chosen from the array. For simplicity, we've chosen the middle element here.
2. Elements less than the pivot are moved to its left, and elements greater than the pivot are moved to its right.
3. quickSort is then called recursively on the left and right sub-arrays.
4. The process continues until the base case is reached, i.e., the array to be sorted has 1 or 0 elements.
5. The sorted array is constructed by combining the sorted left sub-array, the pivot, and the sorted right sub-array.
My Top and Bestseller Udemy Courses. The sale is going on with a 70 - 80% discount. The discount coupon has been added to each course below:
Build REST APIs with Spring Boot 4, Spring Security 7, and JWT
![[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25](https://img-c.udemycdn.com/course/750x422/6852721_b512_2.jpg "[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25")
[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25
ChatGPT + Generative AI + Prompt Engineering for Beginners
Spring 7 and Spring Boot 4 for Beginners (Includes 8 Projects)
Available in Udemy for Business
Building Real-Time REST APIs with Spring Boot - Blog App
Available in Udemy for Business
Building Microservices with Spring Boot and Spring Cloud
Available in Udemy for Business
Java Full-Stack Developer Course with Spring Boot and React JS
Available in Udemy for Business
Build 5 Spring Boot Projects with Java: Line-by-Line Coding
Testing Spring Boot Application with JUnit and Mockito
Available in Udemy for Business
Spring Boot Thymeleaf Real-Time Web Application - Blog App
Available in Udemy for Business
Master Spring Data JPA with Hibernate
Available in Udemy for Business
Spring Boot + Apache Kafka Course - The Practical Guide
Available in Udemy for Business
Comments
Post a Comment
Leave Comment