Sorting Algorithms Flashcards
A sorting algorithm is ______________ if its sorts by comparing the items
Comparison based sorting
Bubble sort Best, Average, and Worst Case
O(n^2)
Selection Sort Best, Average, and Worst Case
O(n^2)
Heapsort Best, Average, and Worst Case
O(n log n)
divides the array to sorted and unsorted sections, and keeps on inserting elements to the sorted section from the unsorted part
Insertion Sort
An algorithm that doesn’t require extra proportional space.,
in-place algorithm (eg. Insertion Sort)
divide and conquer sorting algorithms
Merge Sort & Quick Sort
Insertion Sort Pseudo code
insertionsort(int a[], int n){
int i,j;
for(i=1;i<n;i++)
for(j=i: j>0; j–)
if(a[j-1] > a[j])
swap(&a[j-1],&a[j]_)
else
break;
}
Merge Sort Pseudo codeO(n log n)
mergesort(int a[], int
lower, int upper){
int mid;
if(upper-lower>0){
mid = (lower + upper)/2;
mergesort(a,lower,mid);
mergesort(a,mid+1,upper);
merge(a, lower,mid,upper);
Merge sort runs in ____________ time.
O(n log n)
T or F:
Merge sort sorts in-place.
False. Merge sort uses extra memory
QuickSort Pseudo code
QUICKSORT(A,start,pivot):
if start < pivot:
q = PARTITION(A,start,pivot)
QUICKSORT(A,start,q-1)
QUICKSORT(A,q+1,pivot)
PARTITION(A,start,pivot):
x = A[pivot]
i = start-1
for j = start to pivot-1:
if A[j] <= x:
i = i+1
swap A[i] with A[j]
swap A[i+1] with A[PIVOT]
return i+1
Quicksort runs in ______ time in the worst-case
O(n^2)
Quicksort runs in the ____________ time for best and average cases.
O(n log n)
T or F
Quicksort sorts in-place
T
Insertion sort Best, Average, and Worst Case Run Time
BEST: O(n)
AVERAGE: O(n^2)
WORST: O(n^2)
Merge sort Best, Average, and Worst Case Run Time
O(n log n) for all
Quicksort Best, Average, and Worst Case Run Time
BEST: O(n log n)
AVERAGE: O(n log n)
WORST: O(n^2)
Examples of non comparison-based Sorting
Counting Sort
Radix Sort
__________________ assumes that the elements are integers that range from 0 to k, for some integer k.
Counting sort
Counting Sort Pseudo code
COUNTING-SORT(A,n,k):
let B[1:n] and C[0:k] be arrays
for i=0 to k: //init
C[i] = 0
for j=1 to n: //freq
C[A[j]] = C[A[j]] + 1
for i=1 to k: //position
C[i] = C[i] + C[i-1]
//copy A to B, start from end of A
for j=n downto 1:
B[C[A[j]]] = A[j]
C[A[j]] = C[A[j]]-1
return B
Counting sort runtime
O(n+k) time
A sorting algorithm is said to be _________, when elements with the same value appear in the output array in the same order as they did in the input array
Stable (ie. Counting Sort)
Used by card-sorting machines for punch cards
Radix Sort
