Difference between revisions of "User:William-chin"

Revision as of 02:09, 27 April 2022

Reflection in a Soap Bubble

Background[edit]

Read Quick Sort Algorithm (Wikipedia)
View Quick Sort Algorithm (YouTube)
View Quick Sort Algorithm (YouTube)

Introduction[edit]

The quicksort algorithm is generally known as one of the fastest sorting algorithms, many times faster than heap sort. If implemented well, quick sort algorithms can have a complexity of O(n log n)

Algorithm[edit]

The quicksort algorithm calls for a pivot during its recursive calls, here is an overview:

Pick an element as a pivot
Create 2 markers, which will be compared with a < function in order to set values up for a partition
Create a partition, which will be used to put elements in an array smaller than x and greater than x
Repeat steps 2 and 3 until the array is sorted

Implementation[edit]

Quicksort algorithms vary, partitions and pivot elements can be different for each algorithm. The partition and method of obtaining a pivot element usually depend on what is being sorted, and what level of Big O complexity the algorithm is aiming for.

First, create a partition

* A partition will take the pivot point(x) and put all smaller elements before x, and all larger elements after x
* in order to do this, we will need to keep track of the leftmost and rightmost index with 2 pointers( or markers)
* While traversing elements, if we find a smaller element (an element smaller than x), we will swap the lower element to the left
* Otherwise, if there aren't any smaller elements, we will ignore the current element

Then recursive calls of these partitions will be made until the array is sorted

Quicksort partition diagram

Performance[edit]

As seen before, the average performance of quicksort is O(n log n) complexity, but how quicksort algorithms work, depends on the method of obtaining a pivot point, and how partitions are made (based on how array elements were originally inputted), quicksort can have a worse case complexity of O(n^2).

Exercises[edit]

Exercises

M1352-10 Complete Merlin Mission Manager Mission M1352-10.

@@ Line 5: / Line 5: @@
 == Background ==
-* Read [https://en.wikipedia.org/wiki/Quicksort] (Wikipedia)
+* Read [https://en.wikipedia.org/wiki/Quicksort Quick Sort Algorithm] (Wikipedia)
 * View [https://www.youtube.com/watch?v=SLauY6PpjW4 Quick Sort Algorithm] (YouTube)
 * View [https://www.youtube.com/watch?v=7h1s2SojIRw Quick Sort Algorithm] (YouTube)
@@ Line 15: / Line 15: @@
 == Algorithm ==
-The quick sort algorithm calls for a pivot during its recursive calls, here is an overview:
+The quicksort algorithm calls for a pivot during its recursive calls, here is an overview:
-# Iterate, with an index, over all array elements
+# Pick an element as a pivot
-# If the element on the left is '''greater than''' the element on the right, swap the elements
+# Create 2 markers, which will be compared with a < function in order to set values up for a partition
-# Repeat steps 1 & 2 until there are no more swaps to complete
+# Create a partition, which will be used to put elements in an array smaller than x and greater than x
+# Repeat steps 2 and 3 until the array is sorted
 === Implementation ===
-Although the algorithm is simple, the implementation takes a bit more thought. Here are some things to keep in mind:
+Quicksort algorithms vary, partitions and pivot elements can be different for each algorithm. The partition and method of obtaining a pivot element usually depend on what is being sorted, and what level of Big O complexity the algorithm is aiming for.
-* You'll need a variable to count the number of swaps you've made, in total and after each pass
-* Before a swap, you'll need to store one of the values in a '''temporary variable'''
-* You'll need a '''nested loop''' (the outer loop to continue until the array is sorted, and the inner loop to iterate over the array)
-* Consider which type of loop is the best option ('''Hint:''' you'll need the outer loop to always run at least once)
-==== Swaps ====
-You can write the swap implementation within the nested loop or within a separate function. Note that if you choose to write a separate function, you'll want to pass the array into the function '''by reference''' to avoid making a copy of the array each time you need to make a swap. However you choose to implement the swap, you'll need to store at least one of the values (the left or the right) outside of the array. If you just swap without storing one of the values:
-<syntaxhighlight>
-integers[index-1] = integers[index]
-integers[index] = integers[index-1]
-</syntaxhighlight>
-After the execution of the above code, the elements/integers at '''''index''''' and '''''index - 1''''' would be equal to whatever the element/integer at '''''index''''' originally was. In order to solve this, you'll need to store either initial element into a temporary variable, swap the elements, then assign the remaining element to your stored value.
-=== Example ===
+* First, create a partition
-Here's an example of a bubble sort for an array with 3 elements:
+ * A partition will take the pivot point(x) and put all smaller elements before x, and all larger elements after x
+ * in order to do this, we will need to keep track of the leftmost and rightmost index with 2 pointers( or markers)
+ * While traversing elements, if we find a smaller element (an element smaller than x), we will swap the lower element to the left
+ * Otherwise, if there aren't any smaller elements, we will ignore the current element
+* Then recursive calls of these partitions will be made until the array is sorted
-<syntaxhighlight>
+[[File:Quicksort algorithm diagram.png|thumb|right|Quicksort partition diagram]]
-Array: [42, 82, 40] | Initial, Pass: 0
-Array: [42, 40, 82] | Swaps: 1, Pass: 1
-Array: [40, 42, 82] | Swaps: 1, Pass: 2
-Array: [40, 42, 82] | Swaps: 0, Pass: 3
-Sorted in 3 iterations
-</syntaxhighlight>
-Iteration #
-# The array was initially set to <syntaxhighlight inline>[42, 82, 40]</syntaxhighlight>. Remember that we compare each element with the one before it, so the algorithm will compare '''42''' and '''82''' first. Since 42 < 82, there there's nothing to swap. However, for the next two elements '''82''' and '''40''', 82 > 40 so the elements are swapped.
-# For the second iteration, the array starts at <syntaxhighlight inline>[42, 40, 82]</syntaxhighlight>. The first two elements, '''42''' and '''40''' are compared. Because 42 > 40, the first two elements are swapped. Then, the next two elements: '''42''' and '''82''' are compared. Because 42 < 82, they are already in order and no swaps need to be made.
-# For the third iteration, the array start at <syntaxhighlight inline>Array: [40, 42, 82]</syntaxhighlight>. The first two elements, '''40''' and '''42''' are compared. Because 40 < 42, no swaps need to be made. Then, the next two elements, '''42''' and '''82''' are compared. Because 42 < 82, no swaps need to be made. Because no swaps were made at all in this iteration, we know the array is sorted and we can exit the loop.
 === Performance ===
-Although bubble sort is a simple algorithm to implement, it is rarely used for real-world applications because of its poor performance ( O(n^2) ) and is usually seen in an academic environment.
+As seen before, the average performance of quicksort is O(n log n) complexity, but how quicksort algorithms work, depends on the method of obtaining a pivot point, and how partitions are made (based on how array elements were originally inputted), quicksort can have a worse case complexity of O(n^2).