Sorts And Searches

Willie Loyd Tandingan BSCompE-2 Gnome Sort Worst case performance: Best case performance: O(n)

O(n*n)

void GnomeSort(int arr[], int size) { int i; for (i = 0; i < size - 1; i++) { if (arr[i] > arr[i+1]) { element? (ascending) Swap(&arr[i], &arr[i+1]); if (i > 0) i-=2; move left

swap if current position is not start, (decrement by 2 because of loop

update) }

iterate from start to end-1 current element > next

}

} Merge Sort function merge_sort(m) var list left, right, result if length(m) ≤ 1 0, 1 return m var middle = length(m) / 2 – 1 for each x in m up to middle add x to left one list for each x in m after middle add x to right list left = merge_sort(left) right = merge_sort(right) result = merge(left, right) return result

list is sorted if length(m) =

splt/divide list merge left side elements into merge right side elements into one

function merge(left,right) var list result while length(left) > 0 and length(right) > 0 the lists becomes empty if first(left) ≤ first(right) lesser than the right append first(left) to result left = rest(left) else append first(right) to result right = rest(right) end while while length(left) > 0 append left to result while length(right) > 0 append right to result return result

sort left list sort right list merge lists

merged list iterate while until one of if left element is move left to new list else move right to new list

append left list to new list append right list to new list

Quicksort with 3-way partitioning O(log n) extra space Worst case performance: O(n*n) Average case performance: O(n log n) Best case performance: O(n) when O(1) unique keys This algorithm is optimal for data sets with multiple equal keys void quicksort(Item a[], int l, int r) { int i = l-1, j = r, p = l-1, q = r; Item v = a[r]; if (r <= l) return;

lbound crossed with rbound

for (;;) { while (a[++i] < v); while (v < a[--j]) if (j == l) break; if (i >= j) break; exch(a[i], a[j]); if (a[i] == v) { p++; exch(a[p], a[i]); } if (v == a[j]) { q--; exch(a[j], a[q]); } }

pointer from left pointer from right left end start for equalities right end start for equalities pivot

partition: find element not lesser than pivot find element not greater than pivot

stop if pointers have crossed (nothing to swap) swap check if left element is equal to pivot increment position swap check if right element is equal to pivot decrement position swap

exch(a[i], a[r]); j = i-1; i = i+1; move pivot in place for (k = l; k < p; k++, j--) exch(a[k], a[j]); swap left elements equal to pivot to center for (k = r-1; k > q; k--, i++) exch(a[i], a[k]); swap right elements equal to pivot to center quicksort(a, l, j); quicksort(a, i, r); } Partial partition: Full partition:

sort left partition sort right partition [ equal | lesser | pivot | greater | equal ] [ lesser | equal | greater ]

Linear/Sequential Search Worst case performance: Best case performance: O(1)

О(n)

public int linearSearch(int a[], int valueToFind) { for (int i=0; i
iterate from start to end if current element is equal found

}

} return -1;

not found

Binary Search/Chop Data structure: Array Worst case performance: О(log n) Best case performance: O(1) Average case performance: O(log n) Requirement: Sorted array BinarySearch(A[0..N-1], value, low, high) { if (high < low) return -1 not found mid = low + ((high - low) / 2) calculate midpoint location if (A[mid] rel="nofollow"> value) if midpoint element is greater than searchee return BinarySearch(A, value, low, mid-1) search left of midpoint else if (A[mid] < value) if midpoint is lesser than searchee return BinarySearch(A, value, mid+1, high) search right of midpoint else return mid found (equal) }