1
SORTING ALOGARITHMS EXAM LATEST VERSION -2025/2026-
100+ Q AND ANS ALL THE BEST
What is the number of different executions of algorithm?
A new execution can be triggered only by comparison.
Let's imagine that each comparison induces a 0 or 1 in a k-bit string. E.g. 0 if
a[i]<a[j] and 1 if a[i]>=a[j].
There are 2^k such strings, or possible executions.
Now, pigeons are n! possible inputs, holes are 2^k possible executions.
If 2^k < n!, then two different inputs would have just the same execution path of
the algorithm, which is not possible.
So:
2^k >= n!
n! = n (n-1) (n-2) ... 1
half of these numbers are >= n/2
n! >= (n/2)^(n/2)
2^k >= (n/2) ^ (n/2)
k >= (n/2) log(n/2) = theta(nlog(n))
Bucket sort, Counting sort, Radix Sort
non-comparison based algorithms
Bucket Sort:
used when sorting samples from uniform distribution on [0,1]
, 2
E.g. sorting array of size n.
Pre-allocate k buckets with width 1/k
In one pass on the array: if element is between 0 and 1/k - put it to 1st bucket,
between 1/k and 2/k - 2nd bucket, and so on.
Because input data is supposed to be distributed uniformly at random, the
number of elements in each bucket will be extremely small, and you can use
insertion sort to sort each bucket.
motivation: nlogn algorithm that would work in-place:
algorithm:
QSort(array)
1) find pivot p
2) partition around the pivot - so that every element to the left is less than the
pivot, and every element to the right is bigger then the pivot
finds new pivot position k
3) qsort(left from k), qsort(right from k)
Partitioning routine:
a) let p be the 1st element. If not - just swap (1st element, p)
b) i = 1 - generic iterator
k = 1 - left/right separator
c) for i = 1 .. n-1
if(a[i]<a[k])
swap(i,k)
k++
i++
, 3
d) swap(0,k-1), return k-1
worst case - n^2
randomized pivot selections - n*log(n)
to get n*log(n) speed, we need each pivot to give at least 25-75 split
this happens with probability alpha = 0.5
see full proof in the text book
Lower bound on comparison-based sorts
Any comparison-based sorting algorithm can not run faster then n*log(n) time
by comparison-based we mean the we can not access the "guts" of objects, it can
only compare objects.
To prove the lower bound, we use pigeonhole principle: if there are n pigeons and
n-1 holes, two pigeons will end up in 1 hole.
Now, let's say we are sorting array of n elements. There are n! possible inputs.
Let's call k - maximum number of comparisons made by algorithm.
Counting Sort:
the same idea, but data are small integers, e.g. from [0,..,k].
again bucketing the data, but this time to k buckets
Radix Sort
assumes that data are small integers represented by binary strings, and sorts
them one bit at a time for least to most significant bit. Requires n additional
space.
Can actually sort decimal digits quite the same.
On first pass through the array: count how many elements you have for each value
(for values 0,1 in case of bit strings, for values [0,1,2, 3,...,9] in case of decimal
digits.
, 4
Calculate beginning and end indexes for elements with each value in resulting
array.
From end to beginning, start populating new array by putting elements to their
buckets (also from end to beginning)
Visualization: https://www.cs.usfca.edu/~galles/visualization/RadixSort.html
Bubble Sort
O(n^2)
public void sort(List<Integer> input) {
int size = input.size();
for(int i = 0; i < size; i++){
for(int j = i+1; j <size;j++){
if(input.get(i) > input.get(j)){
swap(input, i ,j);
}
}
}
}
number of comparisons: n + (n-1) + (n-2) + ... + 1 = n * (n-1)/2 = O(n^2)
another implementation:
public void sort(List<Integer> input) {
boolean swapped = false;
int finish_index = input.size()-1;
do{
swapped = false;
SORTING ALOGARITHMS EXAM LATEST VERSION -2025/2026-
100+ Q AND ANS ALL THE BEST
What is the number of different executions of algorithm?
A new execution can be triggered only by comparison.
Let's imagine that each comparison induces a 0 or 1 in a k-bit string. E.g. 0 if
a[i]<a[j] and 1 if a[i]>=a[j].
There are 2^k such strings, or possible executions.
Now, pigeons are n! possible inputs, holes are 2^k possible executions.
If 2^k < n!, then two different inputs would have just the same execution path of
the algorithm, which is not possible.
So:
2^k >= n!
n! = n (n-1) (n-2) ... 1
half of these numbers are >= n/2
n! >= (n/2)^(n/2)
2^k >= (n/2) ^ (n/2)
k >= (n/2) log(n/2) = theta(nlog(n))
Bucket sort, Counting sort, Radix Sort
non-comparison based algorithms
Bucket Sort:
used when sorting samples from uniform distribution on [0,1]
, 2
E.g. sorting array of size n.
Pre-allocate k buckets with width 1/k
In one pass on the array: if element is between 0 and 1/k - put it to 1st bucket,
between 1/k and 2/k - 2nd bucket, and so on.
Because input data is supposed to be distributed uniformly at random, the
number of elements in each bucket will be extremely small, and you can use
insertion sort to sort each bucket.
motivation: nlogn algorithm that would work in-place:
algorithm:
QSort(array)
1) find pivot p
2) partition around the pivot - so that every element to the left is less than the
pivot, and every element to the right is bigger then the pivot
finds new pivot position k
3) qsort(left from k), qsort(right from k)
Partitioning routine:
a) let p be the 1st element. If not - just swap (1st element, p)
b) i = 1 - generic iterator
k = 1 - left/right separator
c) for i = 1 .. n-1
if(a[i]<a[k])
swap(i,k)
k++
i++
, 3
d) swap(0,k-1), return k-1
worst case - n^2
randomized pivot selections - n*log(n)
to get n*log(n) speed, we need each pivot to give at least 25-75 split
this happens with probability alpha = 0.5
see full proof in the text book
Lower bound on comparison-based sorts
Any comparison-based sorting algorithm can not run faster then n*log(n) time
by comparison-based we mean the we can not access the "guts" of objects, it can
only compare objects.
To prove the lower bound, we use pigeonhole principle: if there are n pigeons and
n-1 holes, two pigeons will end up in 1 hole.
Now, let's say we are sorting array of n elements. There are n! possible inputs.
Let's call k - maximum number of comparisons made by algorithm.
Counting Sort:
the same idea, but data are small integers, e.g. from [0,..,k].
again bucketing the data, but this time to k buckets
Radix Sort
assumes that data are small integers represented by binary strings, and sorts
them one bit at a time for least to most significant bit. Requires n additional
space.
Can actually sort decimal digits quite the same.
On first pass through the array: count how many elements you have for each value
(for values 0,1 in case of bit strings, for values [0,1,2, 3,...,9] in case of decimal
digits.
, 4
Calculate beginning and end indexes for elements with each value in resulting
array.
From end to beginning, start populating new array by putting elements to their
buckets (also from end to beginning)
Visualization: https://www.cs.usfca.edu/~galles/visualization/RadixSort.html
Bubble Sort
O(n^2)
public void sort(List<Integer> input) {
int size = input.size();
for(int i = 0; i < size; i++){
for(int j = i+1; j <size;j++){
if(input.get(i) > input.get(j)){
swap(input, i ,j);
}
}
}
}
number of comparisons: n + (n-1) + (n-2) + ... + 1 = n * (n-1)/2 = O(n^2)
another implementation:
public void sort(List<Integer> input) {
boolean swapped = false;
int finish_index = input.size()-1;
do{
swapped = false;
