2. 3. 3 Sorting Algorithms Flashcards
1
Q
Keep in mind
A
For any sort make sure you check what the question is asking, it can easily catch you out by doing descending order rather than ascending order.
2
Q
Bubble Sort
A
- Makes comparisons, swaps between pairs of elements
- Algorithm compares first element in array with second element
- If they are in wrong order, switch places else algorithm moves on
- Process repeats till end of array is reached (Largest element in last position of array)
- This is referred to as a “pass” of the algorithm
- An array with n elements, algorithm will perform n passes through the data
- Clear that Bubble sort prone to wasting time by doing unnecessary checks
- Time complexity of O(n^2)
- Example in next flashcard demonstrates this
3
Q
Pseudocode for Bubble Sort
A
- A = Array of data
- for i = 0 to A.length - 1:
- noSwap = True
- for j = 0 to A. length - (i + 1):
- if A[j] > A[j+1]:
- temp = A[j]
- A[j] = A[j+1]
- A[j+1] = temp
- noSwap = False
- if noSwap:
- break
- return A
4
Q
Example of a Bubble Sort
A
- Use Bubble Sort to arrange following elements into ascending order
- |4| |9| |1| |6| |7|
- 4 and 9 compared, stay in place, 9 and 1 compared, switch places
- |4| |1| |9| |6| |7|
- 9 and 6 compared, switch places, 9 and 7 compared, switch places
- |4| |1| |6| |7| |9|
- This is the end of first pass, second pass begins
- 4 and 1 compared, switch places
- |1| |4| |6| |7| |9|
- Everything else compared again, marks end of second pass
- Another 2 passes occur ending on pass 5 (remember 5 elements 5 passes)
5
Q
Insertion Sort
A
- Places elements into a sorted sequence
- First element compared to element on the left
- Second element compared to element on the left, if it is smaller swap
- Moves on to the third, same process occurs again
- Keep in mind that a pass still occurs even if no swap were made
- Each time a pass occurs, the sorted list increases by one value
6
Q
Pseudocode for Insertion Sort
A
- A = Array of data
- for i = 1 to A.length - 1:
- elem = A[i]
- j = i − 1
- while j > 0 and A[j] > elem:
- A[j+1] = A[j]
- j = j − 1
- A[j+1] = elem
7
Q
Example of an Insertion Sort
A
- |4||9||1||6||7|
- Algorithm ignores first element as it is a part of the “sorted list”, starts with second element
- Second element compared to 4, bigger, stays in place, one pass occurs everything remains in place
- |4||9||1||6||7|
- Third element compared to 9, smaller, swaps places, compared to 4, smaller, swaps places
- |1||4||9||6||7|
- Fourth element compared to 9, smaller swaps places, compared to 4, bigger, stays in place
- |1||4||6||9||7|
- Fifth element compared to 9, smaller, swaps places, compared to 6, bigger, stays in place
- |1||4||6||7||9|
- Left with our sorted list
- Each time a pass occurs, the sorted list increases by one value
8
Q
Merge Sort
A
- Example of a class of algorithms known as “divide and conquer”
- Pseudocode below is not an exact implementation but demonstrates how it works
- Merge sort splits array evenly into smaller arrays till there is one value per array (isolation)
- The arrays are then “merged” back together in the desired order (Alphabetic, ascending, descending)
- It is more efficient than bubble and insertion sort with a worse case complexity of 0(n logn)
9
Q
Pseudocode for Merge Sort
A
- A = Array of data
- MergeSort (A)
- if A.length <= 1:
- return A
- else:
- mid = A.length / 2
- left = A[0…mid]
- right = A[mid+1…A.length-1]
- leftSort = MergeSort(left)
- rightSort = MergeSort(right)
- return Merge(leftSort, rightSort)
10
Q
Example of a Merge Sort
A
- Sort the following array using a merge sort in ascending order
- |7||4||2||6|
- |7||4| |2||6|
- |7| |4| |2| |6|
- |4||7| |2||6|
- |2||4||6||7|
11
Q
Quick Sort
A
- An element is selected, often the central element known as the pivot
- Elements smaller than pivot placed in array to the left of the pivot, others placed right of the array
- Process repeated recursively on each new array till every element is either an old pivot or an array of length 1
- Not particularly fast, time complexity of O(n^2)
12
Q
Example of a Quick Sort
A
- Sort the following list using a quick sort in ascending order
- |9||4||7||8||6||3||1||5||2|
- Central element is first pivot, pivot is 6
- Elements compared from left to right, larger than pivot placed in array to the right, smaller than pivot placed in array to the left
- Array on the left is |4||3||1||5||2| and consists of 5 elements
- Array on the right is |9||7||8| and consists of 3 elements
- 6 is now an old pivot and is the correct place, new pivot selected for each array
- Pivot for array on left is 1 and pivot for array on right is 7
- No elements smaller than 1, no new left array, 4 elements greater than 1 creating new array on the right
- New array on the right of 1 is |4||3||5||2| and consists of 4 elements
- No elements smaller than 7, no new left array, 2 elements greater than 7 creating new array on right
- New array on right of 7 is |8||9| and consists of 2 elements
- Elements 1, 6 and 7 are all old pivots leaving us with a 4-element list and a 2-element list
- The same process repeats till we are left with the sorted list
- |1||2||3||4||5||6||7||8||9|
13
Q
Example with just workings
A
- Bold black border means that element is the new pivot
- Shaded in black element means the element is an old pivot
- As we can see, sort stops because all that’s left is single element arrays and old pivots
