Sorting Algorithms Flashcards
What is the Bubble Sort Algorithm
- The algorithm starts at the first element in an array and compares it to the second
- If they are in the wrong order, the algorithm swaps the pair. Otherwise, the algorithm moves on
- The process is then repeated for every adjacent pair of elements in the array until the end of the array is reached (at which point the largest element is in the last position of the array).
Describe the psudocode for a Bubble Sort Algorithm
Function BubbleSort (int[] data)
numItems = data.length - 1
For i = 0 to numItems - 2
For j = 0 to numItems - i - 2
If data[j] > data[j + 1]
temp = data[j]
data[j] = data[j + 1]
data[j + 1] = temp
end if
next j
next i
end fucntion
Describe the pseudocode for a Improved Bubble Sort Algorithm
Function BubbleSort (int[] data)
numItems = data.length - 1
Swapped = true
WHILE numItems > 0 AND swapped
Swapped = False
numItem = numItems – 1
FOR count = 0 to numItems – 1
IF data[count] > data[count + 1] THEN
temp = data[count + 1]
data[count + 1] = data[count]
data[count] = temp
Swapped = True
END IF
NEXT Count
END WHILE
return data
END FUNCTION
Why do we use an Improved Bubble Sort Algorithm
- Oridnary Bubble Sort could make many pointless comparisons which waste time
- Improved Bubble Sort has a flag recording whether a swap has occurred. If a full pass is made without any swaps, then the algorithm terminates earlier than it would have done originally saving time
- Improved Bubble Sort has the inclusion of j in the second for loop. This means that as j increases, fewer comparisons are made. This works because the largest element is always in place at the end of the first pass, and the second largest element is in place at the end of the second pass and so on. There is no need to check these elements as we know they’re in the right place
What is the Time Complexity and Space Complexity of the Bubble Sort
Best Case Time Complexity- O (n)
Wosrt Case Time Complexity - O (n2)
Space Complexity - 0 (n)
What is the Insertion Sort Algorithm
- Insertion sort 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 in the input is then selected, it is inserted into the correct position in the sorted portion of the input to its left
- This continues until the last element is inserted into the correct position
Describe the pseudocode for a Insertion Sort
Function insertionSort(int[] data)
For count = 1 to data.length
currentdata = data[count]
While (count > 0 AND data[count –1] > currentdata
temp = data[count]
data[count] = data[count - 1]
data[count - 1] = temp
count = count - 1
End while
data[count] = currentdata
NEXT COUNT
END FUNCTION
return A
What is the Time Complexity of an Insertion Sort
Worst Time Complexity - O (n2)
Best Time Complexity - O (n)
Space Complexity - O (k)
What is a Merge Sort Algorithm
- Merge sort is formed from two functions
- One called MergeSort and another called Merge
- MergeSort divides its input into two parts and recursively calls MergeSort on each of those two parts until they are of length 1 at which point Merge is called
- Merge puts groups of elements back together in a special way, ensuring that the final group produced is sorted
What is the Time Complexity and Space Complexity of a Merge Sort
Best and Worst Time Complexity - O(n logn)
Space Complexity - O (n) because the merge sort needs extra space for the left and right sublists that are created whenever items is split, if the original list has n items, then the sublists will also need to hold n items in total
What is a Quick Sort Algorithm
- Quick sort works by selecting an element, often the central element (called a pivot), and dividing the input around it
- Elements smaller than the pivot are placed in a list to the left of the pivot and others are placed in a list to the right
- This process is then repeated recursively on each new list until all elements in the input are old pivots themselves or form a list of length 1
What is the Time Complexity of a Quick Sort Algorithm
O (n log n)
