2.3.3 - Sorting Algorithms Flashcards
What is the purpose of a sorting algorithm?
To take a number of elements in any order and output them in a logical order, normally numerical or lexographic.
How do most sorting algorithms output elements?
In ascending order. This can typically be altered by reversing output or switching an inequality.
What does bubble sort do?
Bubble sort makes comparisons and swaps between pairs of elements. The largest element in the unsorted part of the input is said to “bubble” to the top of the data with each iteration of the algorithm.
How does bubble sort work?
Start at first element, compare to second.
If in wrong order, swap, else move on.
Repeat process for every adjacent element pair in the array until end is reached.
This is one pass - for an array with n elements, n passes must be performed.
Basic bubble sort pseudocode
for i = 0 to A.length - 1:
for j = 0 to A.length - 2:
if A[j] > A[j+1]:
temp = A[j]
A[j] = A[j+1]
A[j+1] = temp
endif
return A
Why can basic bubble sort be inefficient?
If the algorithm goes on until it terminates, it could possibly make many pointless comparisons.
How can bubble sort be improved?
Add a noSwap variable, which is set to true and changed to False if a swap is made.
change second loop to “for j = 0 to A.length - (i+1)”
Describe the speed of bubble sort
Fairly slow, time complexity 0 (n^2)
What does insertion sort do?
Insertion sort places elements into a sorted sequence one by one. In i iterations, the first i elements are sorted. However, they aren’t necessarily the i smallest.
How does insertion sort work?
It starts at the second element in the input and compares it to the element to its left. If the two elements are in the wrong order, the smaller element is placed in the lowest position.
The third element is selected, then inserted in the correct position of the sorted portion to its left. This continues until the last element is correctly inserted.
Insertion sort pseudocode
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
Why does insertion sort ignore the first element?
A single element is always a sorted sequence
What is merge sort?
Merge sort is an example of a class of algorithms known as “divide and conquer” algorithms.
How does merge sort work?
Merge sort is formed from two functions, MergeSort and Merge. MergeSort divides its input into two, recursively calling MergeSort on these two parts until they are length 1.
Merge then puts groups back together in a special way, ensuring they are sorted.
Merge Sort Pseudocode
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)
