Introduction
Algorithms and data structures are one of the core sections of software engineering and play an important role in coding tests for employment.
In particular, sorting algorithms are a frequently tested topic in interviews. Today, we will look at Quick Sort, which can be implemented in Swift.
What is Quick Sort?
Quick Sort is an efficient sorting algorithm based on the divide and conquer principle.
On average, it has a time complexity of O(n log n) and a worst-case time complexity of O(n^2).
However, it exhibits very fast performance on sorted arrays. Quick Sort is recursive and consists of the following key steps.
- Select a pivot point. Usually, the last element is chosen.
- Move elements smaller than the pivot to the left and those larger to the right.
- Return the position of the pivot and recursively call Quick Sort on the left and right sublists.
Time Complexity of Quick Sort
Quick Sort takes O(n log n) time on average but has a worst-case time complexity of O(n^2).
This occurs when the method for selecting the pivot is poor. For example, if the first element is chosen as the pivot for an already sorted array.
To prevent this, various pivot selection strategies can be used, such as using the median, random selection, or the “median-of-three” method.
Implementing Quick Sort in Swift
Now, let’s implement the Quick Sort algorithm in Swift. Below is the Swift code that implements Quick Sort.
func quickSort(_ array: [T]) -> [T] {
// Return the array if it's empty or has one element
guard array.count > 1 else { return array }
// Choose the last element as the pivot
let pivot = array[array.count - 1]
// Create arrays for elements less than, equal to, and greater than the pivot
var left: [T] = []
var right: [T] = []
for element in array.dropLast() {
if element < pivot {
left.append(element)
} else {
right.append(element)
}
}
// Recursively apply Quick Sort to the left and right lists
return quickSort(left) + [pivot] + quickSort(right)
}
Explanation of Quick Sort Code
The above code shows the basic structure of Quick Sort implemented in Swift.
Let's explain it step by step.
- Generic Type:
<T: Comparable>allows Quick Sort to be performed on all comparable types. - Base Case: In a recursive algorithm, the base case is important. If the length of the array is 1 or less, there is no need to sort, so the original array is returned as is.
- Pivot Selection: The last element is chosen as the pivot. This provides simplicity in implementation, but other selection methods can be considered to avoid the worst case.
- Partitioning: Each element should be compared with the pivot to split into two arrays (left, right). Use
dropLast()to check the remaining elements excluding the pivot. - Recursive Call: Call the
quickSort()function on both sublists again. This ultimately generates a sorted array.
Example of Quick Sort
Let's visualize how Quick Sort works through the example below.
We will examine the process of sorting the array [3, 6, 8, 10, 1, 2, 1].
1. Array: [3, 6, 8, 10, 1, 2, 1], pivot: 1
left: [], right: [3, 6, 8, 10]
2. Array: [3, 6, 8, 10], pivot: 10
left: [3, 6, 8], right: []
3. Array: [3, 6, 8], pivot: 8
left: [3, 6], right: []
4. Array: [3, 6], pivot: 6
left: [3], right: []
The final sorted array will be [1, 1, 2, 3, 6, 8, 10].
Advantages and Disadvantages of Quick Sort
Quick Sort has the following advantages.
- It provides fast performance on average due to its divide and conquer approach.
- It has a low base memory usage; it can operate directly on the given array instead of using additional arrays.
- It can be written in a recursive manner, making it simple to implement.
However, there are also disadvantages.
- In the worst case, it can have a time complexity of O(n^2), in which case it might be replaced by another algorithm immediately.
- It can be inefficient for already sorted arrays, necessitating various pivot selection methods to avoid this.
Variations of Quick Sort
Variations of Quick Sort can be used depending on the situation.
For instance, changing the method of pivot selection or calling a different sorting algorithm (e.g., insertion sort) if certain conditions are met.
Additionally, instead of sorting with a fixed-size array, dynamic arrays can be used, or performance can be optimized by stopping the sort when certain conditions are met.
Conclusion
Quick Sort is a preferred sorting algorithm for many developers due to its efficiency and simplicity.
I hope this has helped you understand the basic concepts and workings of Quick Sort through its implementation in Swift.
Practice Quick Sort as a means to effectively learn and familiarize yourself with algorithms and data structures.
That concludes our discussion on Quick Sort. In the next lesson, we will cover other algorithms!