31251 Lecture Notes - Lecture 7: Merge Sort, Quicksort, Sorting Algorithm
30 Jun 2018
School
Department
Course
Professor
Sorting
Bubble Sort
bubbleSort(int a[]) {
//assume array is length n
bool swapHappened;
do {
swapHappened = false;
for (int i = 0; i < n; i++){
if (a[i] > a[i+1]){
swap(a[i], a[i+1]);
swapHappened = true;
}
}
} while (swapHappened);
}
Easy to code.
Bad at almost everything else.
Best case time: O(n), Average case: O(n 2 ), Worst case: O(n 2 ).
Only O(1) extra space need though!
Insertion Sort
insertionSort(int a[]){
for (int i = 1; i < n; i++){
int x = a[i];
int pos = i-1;
while (pos >= 0 && a[pos] > x){
a[pos + 1] = a[pos];
pos--;
}
a[pos + 1] = x;
}
}
1 | P a g e
find more resources at oneclass.com
find more resources at oneclass.com
