If you are learning Dart, mastering sorting algorithms is a key step toward becoming a confident programmer. Sorting allows you to organize data in a meaningful order, which is essential for tasks like displaying search results, analyzing datasets, or processing large amounts of information efficiently. Quick Sort is one of the most popular sorting algorithms because it is fast and works well for most real-world applications.
with hands-on learning.
get the skills and confidence to land your next move.
Quick Sort follows a divide-and-conquer strategy, similar to Merge Sort, but with a different approach. It selects a pivot element, partitions the array around the pivot, and recursively sorts the partitions. Learning Quick Sort not only helps you write efficient code but also introduces you to recursion and problem-solving techniques. In this article, we will explore multiple ways to implement Quick Sort in Dart, making it accessible for beginners and easy to follow.
Program 1: Quick Sort Using Recursion
This first program shows the classic recursive implementation of Quick Sort. It selects a pivot, partitions the list into smaller elements and larger elements, and then recursively sorts each partition.
void quickSort(List<int> arr, int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
int partition(List<int> arr, int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
void main() {
List<int> numbers = [10, 7, 8, 9, 1, 5];
print('Original List: $numbers');
quickSort(numbers, 0, numbers.length - 1);
print('Sorted List: $numbers');
}In this program, the pivot divides the list into smaller and larger elements. Then, the function recursively sorts the sublists. Beginners can understand this approach easily, as it highlights the power of recursion and how dividing a problem into smaller parts can simplify sorting.
Program 2: Quick Sort with First Element as Pivot
This version demonstrates Quick Sort by choosing the first element as the pivot instead of the last. It is a small variation that helps beginners see how pivot selection affects the algorithm.
void quickSortFirstPivot(List<int> arr, int low, int high) {
if (low < high) {
int pi = partitionFirstPivot(arr, low, high);
quickSortFirstPivot(arr, low, pi - 1);
quickSortFirstPivot(arr, pi + 1, high);
}
}
int partitionFirstPivot(List<int> arr, int low, int high) {
int pivot = arr[low];
int i = low + 1;
int j = high;
while (true) {
while (i <= j && arr[i] <= pivot) i++;
while (arr[j] > pivot) j--;
if (i <= j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
} else {
break;
}
}
int temp = arr[low];
arr[low] = arr[j];
arr[j] = temp;
return j;
}
void main() {
List<int> numbers = [4, 2, 6, 9, 3];
print('Original List: $numbers');
quickSortFirstPivot(numbers, 0, numbers.length - 1);
print('Sorted List: $numbers');
}Choosing the first element as pivot introduces beginners to the concept that pivot selection can influence efficiency. This program is useful because it shows how minor changes in logic can affect the partitioning process while still achieving the same sorted result.
Program 3: Quick Sort in Descending Order
Quick Sort can be easily modified to sort a list in descending order. This version shows that by changing the comparison logic, the algorithm adapts to different requirements.
void quickSortDescending(List<int> arr, int low, int high) {
if (low < high) {
int pi = partitionDescending(arr, low, high);
quickSortDescending(arr, low, pi - 1);
quickSortDescending(arr, pi + 1, high);
}
}
int partitionDescending(List<int> arr, int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] > pivot) {
i++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
void main() {
List<int> numbers = [12, 4, 7, 19, 3];
print('Original List: $numbers');
quickSortDescending(numbers, 0, numbers.length - 1);
print('Sorted List in Descending Order: $numbers');
}By changing the comparison from < to >, Quick Sort sorts the list in descending order. This teaches beginners how small modifications can provide flexible solutions to different sorting requirements.
Program 4: Quick Sort Using Middle Element as Pivot
This program demonstrates a more balanced pivot selection by choosing the middle element. It can help prevent worst-case scenarios when sorting already sorted or nearly sorted lists.
void quickSortMiddlePivot(List<int> arr, int low, int high) {
if (low < high) {
int pi = partitionMiddlePivot(arr, low, high);
quickSortMiddlePivot(arr, low, pi - 1);
quickSortMiddlePivot(arr, pi + 1, high);
}
}
int partitionMiddlePivot(List<int> arr, int low, int high) {
int mid = low + (high - low) ~/ 2;
int pivot = arr[mid];
int i = low;
int j = high;
while (i <= j) {
while (arr[i] < pivot) i++;
while (arr[j] > pivot) j--;
if (i <= j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
}
}
return i - 1;
}
void main() {
List<int> numbers = [9, 3, 7, 5, 6, 2];
print('Original List: $numbers');
quickSortMiddlePivot(numbers, 0, numbers.length - 1);
print('Sorted List: $numbers');
}Using the middle element as a pivot can improve efficiency in some cases. Beginners can see how selecting the pivot carefully can impact performance while still understanding the core Quick Sort logic.
Program 5: Quick Sort Using Generic List
Quick Sort can be adapted to work with Dart’s generic lists, allowing sorting of numbers, strings, or other comparable data types.
void quickSortGeneric<T extends Comparable>(List<T> arr, int low, int high) {
if (low < high) {
int pi = partitionGeneric(arr, low, high);
quickSortGeneric(arr, low, pi - 1);
quickSortGeneric(arr, pi + 1, high);
}
}
int partitionGeneric<T extends Comparable>(List<T> arr, int low, int high) {
T pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j].compareTo(pivot) < 0) {
i++;
T temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
T temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
void main() {
List<String> words = ['banana', 'apple', 'cherry', 'date'];
print('Original List: $words');
quickSortGeneric(words, 0, words.length - 1);
print('Sorted List: $words');
}This generic implementation shows how Quick Sort can handle different data types in Dart. Beginners can learn how generics allow algorithms to be flexible and reusable, making the code more robust and versatile for real-world applications.
Frequently Asked Questions (FAQ)
Quick Sort is widely used, but beginners often have questions about it. Here are some common queries and answers.
Q1: What is the time complexity of Quick Sort?
Quick Sort has an average time complexity of O(n log n), but in the worst case, it can be O(n²). Proper pivot selection usually avoids the worst-case scenario.
Q2: Is Quick Sort stable?
No, Quick Sort is not stable by default. Equal elements may change their relative order during sorting.
Q3: Can Quick Sort be used on linked lists?
Yes, Quick Sort can be adapted for linked lists, but Merge Sort is often preferred because it handles linked structures more efficiently.
Q4: How does Quick Sort compare to Merge Sort?
Quick Sort is usually faster on average and uses less memory, but Merge Sort guarantees O(n log n) performance and is stable.
Q5: Can Quick Sort be implemented iteratively?
Yes, Quick Sort can be implemented iteratively using a stack to mimic recursion, which is useful for very large lists.
Conclusion
Quick Sort is a fundamental sorting algorithm that every Dart programmer should learn. It introduces beginners to recursion, partitioning logic, and efficient problem-solving strategies. In this article, we explored multiple implementations, including recursion, descending order, different pivot selections, and generic types.
For beginners, practicing Quick Sort and experimenting with different pivot choices and data types will strengthen algorithmic thinking. Sorting is a critical skill in programming, and mastering Quick Sort in Dart provides a solid foundation for tackling more advanced programming challenges.
