.png)
Mobiprep has created last-minute notes for all topics of Sorting to help you with the revision of concepts for your university examinations. So let’s get started with the lecture notes on Hashing and Sorting.
Data Structure
Linked List
Doubly Linked List
Circular Linked List
Queues
Stacks
Hashing and Searching
Sorting
Our team has curated a list of the most important questions asked in universities such as DU, DTU, VIT, SRM, IP, Pune University, Manipal University, and many more. The questions are created from the previous year's question papers of colleges and universities.
Question 1 - Explain Bubble Sort Algorithm and its complexity?
Answer - In bubble sort algorithm the array of n elements is sorted by comparing the elements one by one. Array can be sorted in either ascending or descending order.
Algorithm:
To sort array of n elements in ascending order first compare the 1st element with the 2nd .
If first element > second one
swap them, else
keep them as it is.
Now compare the 2nd and 3rd elements and check if it is needed to swap them.
Stop this when the greatest element is at the last.
If there are n elements in an array ,unsorted array will be converted into the sorted array by repeating the above process for n-1 times.
Example:
Source: studytonight
Program for bubble sort:
#include<stdio.h>
int main()
{
int n,i,j,val,t;
printf("Enter the no. of elements in array:\t");
scanf("%d",&n);
int arr[n];
printf("Enter the array elemets: \n");
for(j=0;j<n;j++)
{
scanf("%d",&arr[j]);
}
for(i=0;i<n;i++)
{
for(j=0;j<n-i-1;j++)
{
if(arr[j]>arr[j+1])
{
t=arr[j];
arr[j]=arr[j+1];
arr[j+1]=t;
}
}
}
printf("Sorted array list: \n");
for(i=0;i<n;i++)
{
printf("%d\n",arr[i]);
}
}
Pseudo code for bubble sort in c:
procedure bubbleSort( list : array of items )
loop = list.count;
for i = 0 to loop-1 do:
swapped = false
for j = 0 to loop-1 do:
/* compare the adjacent elements */
if list[j] > list[j+1] then
/* swap them */
swap( list[j], list[j+1] )
swapped = true
end if
end for
/*if no number was swapped that means
array is sorted now, break the loop.*/
if(not swapped) then
break
end if
end for
end procedure return list
In bubble sort in first pass we need n-1 comparisons, in 2nd pass we need n-2,in 3rd n-3 comparisons, so the total number of comparisons are
(n-1)+(n-2)+(n-3)+……+2+1=n*(n-1)/2
So the time complexity of bubble sort algorithm is O(n**2)
Worst case time complexity:O(n**2)
Average case time complexity:O(n**2)
Best case time complexity:O(n)
So,this is how bubble sort works and above mentioned are the time complexities of it.
Notes: 1> Don’t write as second person or as 3rd person.
2> Try to write pseudo code instead of long paragraph to explain the code
3> Add answers in format as if you are answering a question in your exams.
Question 2 - Explain Insertion Sort Algorithm and its complexity?
Answer - In Insertion sort: Compare the current element with the elements before it i.e. predecessors.
If (current element < its predecessors)
move to it’s appropriate position.
else
Assume current position is correct for it and move to the next element.
In insertion sort as we start sorting we divide array into two parts i.e. sorted and unsorted. We assume that the first element is by default sorted.
Program for insertion sort:
#include<stdio.h>
int main()
{
int n,i,j,c,d,t;
printf("Enter the no. of elements in array: ");
scanf("%d",&n);
int arr[n];
printf("Enter the array elemets: \n");
for(j=0;j<n;j++)
{
scanf("%d",&arr[j]);
}
for(c=1;c<n;c++)
{
d=c;
while(d>0 && arr[d]<arr[d-1])
{
t=arr[d];
arr[d]=arr[d-1];
arr[d-1]=t;
d--;
}
}
printf("Sorted list:\n");
for(i=0;i<n;i++)
printf("%d\n",arr[i]);
}
Pseudo code for insertion sort:
procedure insertionSort( A : array of items )
int holePosition
int valueToInsert
for i = 1 to length(A) inclusive do:
/* select value to be inserted */
valueToInsert = A[i]
holePosition = i
/*locate hole position for the element to be inserted */
while holePosition > 0 and A[holePosition-1] > valueToInsert do:
A[holePosition] = A[holePosition-1]
holePosition = holePosition -1
end while
/* insert the number at hole position */
A[holePosition] = valueToInsert
end for
end procedure
Say an array to be sorted is given as:
2, 5, 1a, 9, 20, 3, 7, 12, 1b
Now insertion sort works as:
Insert element one by one in the correct place. That is:
1. Insert 2. Array=2, 5, 1a, 9, 20, 3, 7, 12, 1b
2. Insert 5. Array=2, 5, 1a, 9, 20, 3, 7, 12, 1b
3. Insert 1. Array=1a, 2, 5, 9, 20, 3, 7, 12, 1b
4. Insert 9. Array=1a, 2, 5, 9, 20, 3, 7, 12, 1b
5. Insert 20. Array=1a, 2, 5, 9, 20, 3, 7, 12, 1b
6. Insert 3. Array=1a, 2, 3, 5, 9, 20, 7, 12, 1b
7. Insert 7. Array=1a, 2, 3, 5, 7, 9, 20, 12, 1b
8. Insert 12. Array=1a, 2, 3, 5, 7, 9, 12, 20, 1b
9. Insert 1. Array =1a, 1b, 2, 3, 5, 7, 9, 12, 20
Note now the array is sorted.
Insertion sort is in place and stable sorting technique.
Best case TC=O(1)
Since, at each insertion, max possible comparisons is n, its worst case TC=O(n2).
Average case TC will be same as worst case.
Notes : 1> Don’t write as second person or as 3rd person.
2> Try to write pseudo code for better explanation.
3> Add time complexities.
Question 3 - Explain Merge Sort Algorithm and its complexity?
In merge sort the unsorted array is divided into two subarrays. Keep dividing the arrays until the subarray contains single element in it. After dividing arrays now merge the subarrays with single elements. While merging if elements from two smaller subarrays are not sorted first sort them and then merge. Keep merging until a array contains all elements in sorted order.
Example:
Source: www.java2novice.com
Pseudo code for merge sort:
PROCEDURE function mergeSort
FOR each element of the master list indexed by i
if ( i <= 1 ) return a
var left = a[0] to a[i/2]
var right = a[i/2+1] to a[i]
left = mergeSort( left )
right = mergeSort( right )
return merge( left,right )
END FOR
END PROCEDURE
PROCEDURE function mergeSort
WHILE length(left) > 0 and length(right) > 0
if first(left) ≤ first(right)
append first(left) to result
left = rest(left)
else
append first(right) to result
right = rest(right)
IF length(left) > 0
append left to result
END IF
IF length(right) > 0
append right to result
END IF
return result
END PROCEDURE
Average case ,best case and worst case time complexity for merge sort are all same i.e.
O(n*log n).This is all about merge sort.
Notes : 1>. Add pseudo code for better explanation.
2> Add answer as if you are answering in your exams.
3> Don't write as 2nd or third person.
Question 4 - Explain Selection Sort Algorithm and its complexity?
Answer - In selection sort first find the smallest number in unsorted array and place it in the first place or swap the positions of smallest number and first place. Repeat for second smallest number and continue till the array is sorted.
Following is the example of selection sort that how it works.
Program for selection sort :
#include <stdio.h>
int main()
{
int a[100], n, i, j, position, swap;
printf("Enter number of elementsn");
scanf("%d", &n);
printf("Enter %d Numbersn", n);
for (i = 0; i < n; i++)
scanf("%d", &a[i]);
for(i = 0; i < n - 1; i++)
{
position=i;
for(j = i + 1; j < n; j++)
{
if(a[position] > a[j])
position=j;
}
if(position != i)
{
swap=a[i];
a[i]=a[position];
a[position=swap;
}
}
printf("Sorted Array:n");
for(i = 0; i < n; i++)
printf("%dn", a[i]);
return 0;
}
Example:
Souce: studytonight
Pseudo code for selection sort:
procedure selection sort
list : array of items
n : size of list
for i = 1 to n - 1
/* set current element as minimum*/
min = i
/* check the element to be minimum */
for j = i+1 to n
if list[j] < list[min] then
min = j;
end if
end for
/* swap the minimum element with the current element*/
if indexMin != i then
swap list[min] and list[i]
end if
end for
end procedure
As in above program there are two for loops which are nested hence the Best,Worst and Average case time complexity for selection sort is O(n**2).Selection sort is the simplest sorting algorithm. So, this is all about selection sort.
Notes : 1>. Add pseudo code for better explanation.
2> Add answer as if you are answering in your exams.
3> Don't write as 2nd or third person.
Question 5 - Explain Quick Sort Algorithm and its complexity?
Answer - In quick sort sort a array by taking help of pivot. Here pivot considered as the array element with the highest index. By comparing pivot with the other elements of array divide array into two parts one which have smaller values than pivot and one which have higher values than pivot. Now repeat the same procedure with these two sub arrays .Continue till subarrays contains one element and all are sorted.
Source: tutorialspoint
Pseudo code for quick sort :
function partitionFunc(left, right, pivot)
leftPointer = left
rightPointer = right - 1
while True do
while A[++leftPointer] < pivot do
//do-nothing
end while
while rightPointer > 0 && A[--rightPointer] > pivot do
//do-nothing
end while
if leftPointer >= rightPointer
break
else
swap leftPointer,rightPointer
end if
end while
swap leftPointer,right
return leftPointer
end function
procedure quickSort(left, right)
if right-left <= 0
return
else
pivot = A[right]
partition = partitionFunc(left, right, pivot)
quickSort(left,partition-1)
quickSort(partition+1,right)
end if
end procedure
Quicksort pivot algorithm:
Step 1 − Choose the highest index value has pivot
Step 2 − Take two variables to point left and right of the list excluding pivot
Step 3 − left points to the low index
Step 4 − right points to the high
Step 5 − while value at left is less than pivot move right
Step 6 − while value at right is greater than pivot move left
Step 7 − if both step 5 and step 6 does not match swap left and right
Step 8 − if left ≥ right, the point where they met is new pivot
Quicksort Algorithm:
Step 1 − Make the right-most index value pivot
Step 2 − partition the array using pivot value
Step 3 − quicksort left partition recursively
Step 4 − quicksort right partition recursively
Program for quick sort:
#include<stdio.h>
void quicksort(int number[25],int first,int last){
int i, j, pivot, temp;
if(first<last){
pivot=first;
i=first;
j=last;
while(i<j){
while(number[i]<=number[pivot]&&i<last)
i++;
while(number[j]>number[pivot])
j--;
if(i<j){
temp=number[i];
number[i]=number[j];
number[j]=temp;
}
}
temp=number[pivot];
number[pivot]=number[j];
number[j]=temp;
quicksort(number,first,j-1);
quicksort(number,j+1,last);
}
}
int main(){
int i, count, number[25];
printf("How many elements are u going to enter?: ");
scanf("%d",&count);
printf("Enter %d elements: ", count);
for(i=0;i<count;i++)
scanf("%d",&number[i]);
quicksort(number,0,count-1);
printf("Order of Sorted elements: ");
for(i=0;i<count;i++)
printf(" %d",number[i]);
return 0;
}
The time complexities for quick sort are as follows:
Worst case:O(n**2)
Average case: O(n log n)
Best case: O(n log n)
So quicksort is divide and conquer algorithm and this how it works.
Notes : 1>. Add code of quick sort.
2> Write only 1 algorithm/ pseudo code.
3>.Add relevant diagrams and flowcharts.
4> Please proofread before submission.
Question 6 - Explain Heap Sort Algorithm and its complexity?
Answer - Heap sort is very fast and widely used. In heap sort first build a heap. Heap is a tree structure which have all the levels of tree are balanced or complete and it may be either min heap( parents are smaller) or max heap(parents are greater than children). After creating heap pick first element of heap and keep it in array and recreate the heap with remaining elements. Then pick first element from the newly created heap and again recreate the heap continue this till array is sorted.
Pseudo code for heap sort:
Heapify(A as array, n as int, i as int)
{
max = i
leftchild = 2i + 1
rightchild = 2i + 2
if (leftchild <= n) and (A[i] < A[leftchild])
max = leftchild
else
max = i
if (rightchild <= n) and (A[max] > A[rightchild])
max = rightchild
if (max != i)
swap(A[i], A[max])
Heapify(A, n, max)
}
Heapsort(A as array)
{
n = length(A)
for i = n/2 downto 1
Heapify(A, n ,i)
for i = n downto 2
exchange A[1] with A[i]
A.heapsize = A.heapsize - 1
Heapify(A, i, 0)
}
C program for Heap sort:
#include <stdio.h>
void main()
{
int heap[10], no, i, j, c, root, temp;
printf("\n Enter no of elements :");
scanf("%d", &no);
printf("\n Enter the nos : ");
for (i = 0; i < no; i++)
scanf("%d", &heap[i]);
for (i = 1; i < no; i++)
{
c = i;
do
{
root = (c - 1) / 2;
if (heap[root] < heap[c]) /* to create MAX heap array */
{
temp = heap[root];
heap[root] = heap[c];
heap[c] = temp;
}
c = root;
} while (c != 0);
}
printf("Heap array : ");
for (i = 0; i < no; i++)
printf("%d\t ", heap[i]);
for (j = no - 1; j >= 0; j--)
{
temp = heap[0];
heap[0] = heap[j /* swap max element with rightmost leaf element */
heap[j] = temp;
root = 0;
do
{
c = 2 * root + 1; /* left node of root element */
if ((heap[c] < heap[c + 1]) && c < j-1)
c++;
if (heap[root]<heap[c] && c<j) /* again rearrange to max heap array */
{
temp = heap[root];
heap[root] = heap[c];
heap[c] = temp;
}
root = c;
} while (c < j);
}
printf("\n The sorted array is : ");
for (i = 0; i < no; i++)
printf("\t %d", heap[i]);
printf("\n Complexity : \n Best case = Avg case = Worst case = O(n logn) \n");
}
Time complexities for all cases of heap sort are O(n* logn)
Notes : 1>. Add pseudo code for better explanation.
2> Add relevant diagrams and flowcharts
3> Specify time complexity in the end.
Question 7 - Explain Radix Sort Algorithm and its complexity?
Answer - In radix sort:
Compare the unit place of each number and sort them according to their unit places.
Compare according to decimal place and sort them.
Repetition of this procedure is based on the highest element. Say if the highest number has 4 digits, we repeat it for 4 times.
Below example will help to know how radix sort works.
Example:
Source:programizz
Radix sort algorithm :
radixSort(array)
d <- maximum number of digits in the largest element
create d buckets of size 0-9
for i <- 0 to d
sort the elements according to ith place digits using countingSort
countingSort(array, d)
max <- find largest element among dth place elements
initialize count array with all zeros
for j <- 0 to size
find the total count of each unique digit in dth place of elements and
store the count at jth index in count array
for i <- 1 to max
find the cumulative sum and store it in count array itself
for j <- size down to 1
restore the elements to array
decrease count of each element restored by 1
Radix sort program in c:
#include<stdio.h>
int get_max (int a[], int n){
int max = a[0];
for (int i = 1; i < n; i++)
if (a[i] > max)
max = a[i];
return max;
}
void radix_sort (int a[], int n){
int bucket[10][10], bucket_cnt[10];
int i, j, k, r, NOP = 0, divisor = 1, lar, pass;
lar = get_max (a, n);
while (lar > 0){
NOP++;
lar /= 10;
}
for (pass = 0; pass < NOP; pass++){
for (i = 0; i < 10; i++){
bucket_cnt[i] = 0;
}
for (i = 0; i < n; i++){
r = (a[i] / divisor) % 10;
bucket[r][bucket_cnt[r]] = a[i];
bucket_cnt[r] += 1;
}
i = 0;
for (k = 0; k < 10; k++){
for (j = 0; j < bucket_cnt[k]; j++){
a[i] = bucket[k][j];
i++;
}
}
divisor *= 10;
printf ("After pass %d : ", pass + 1);
for (i = 0; i < n; i++)
printf ("%d ", a[i]);
printf ("\n");
}
}
int main (){
int i, n, a[10];
printf ("Enter the number of items to be sorted: ");
scanf ("%d", &n);
printf ("Enter items: ");
for (i = 0; i < n; i++){
scanf ("%d", &a[i]);
}
radix_sort (a, n);
printf ("Sorted items : ");
for (i = 0; i < n; i++)
printf ("%d ", a[i]);
printf ("\n");
return 0;
}
Time complexity for radix sort is O(d(n+k)).
Here, d is the number cycle and O(n+k) is the time complexity of counting sort where n are keys which are integers of word size k.
So, this is all about radix sort.
Notes : 1>.Mention what does n and k means in radix sort time complexity.
2> Add pseudo code if possible.
3> Don't write as 2nd or 3rd person
Question 8 - What is Divide and Conquer? Explain with merge sort.
Answer - Divide and Conquer means:
Divide the main problem into two or more subproblems .Continue dividing till the subproblems can not be divided further.
Now solve these subproblems and
merge their solutions to get the solution of its main problem.
Many sorting algorithm follows Divide and Conquer technique and merge sort is one of them:
In merge sort divide the unsorted array into two. Keep dividing the arrays until get the subarray with single element in it. After dividing arrays now merge the subarrays with single elements. While merging if elements from two smaller subarrays are not sorted first sort them and then merge. Keep merging until a array is sorted with all elements.
In following example the array is a unsorted array. First split the array in mid. Then divide subarrays and keep on dividing them until get a subarray with a single element in it. Now dividing array process is complete now its time for merging them. While merging merge the smallest subarrays first and continue merging them and stop when get a sorted array [3,9,10,27,38,43,82]
Pseudo code for divide and conquer using merge sort:
PROCEDURE function mergeSort
FOR each element of the master list indexed by i
if ( i <= 1 ) return a
var left = a[0] to a[i/2]
var right = a[i/2+1] to a[i]
left = mergeSort( left )
right = mergeSort( right )
return merge( left,right )
END FOR
END PROCEDURE
PROCEDURE function mergeSort
WHILE length(left) > 0 and length(right) > 0
if first(left) ≤ first(right)
append first(left) to result
left = rest(left)
else
append first(right) to result
right = rest(right)
IF length(left) > 0
append left to result
END IF
IF length(right) > 0
append right to result
END IF
return result
END PROCEDURE
Example:
Source: www.java2novice.com
Notes : 1>. Add pseudo code for better explanation.
Comments