DSA - Sorting

Question 1

Merge sort which techniques are used to implement this

Answer 1

• usually done by using recursion
• do using divide and conquer

Question 2

what is first step in merge sort

Answer 2

• continue to divide array in equal half’s until we get individual elements

Question 3

what is second step after dividing array into individual elements

Answer 3

examine individual items
compare their values
and merge them into temporary arrays

Question 4

whats next step

Answer 4

jump up the recursion stack

we continue merging smaller arrays into a larger one inserting items in the correct order

Question 5

write pseudocode

Answer 5

mergesort(array a)
if n == 1
return a

arrOne = a[0]…….a[n/2]
arrTwo = a[n / 2 + 1] …… a[n]

arrOne = mergesort(arrOne)
arrTwo = mergesort(arrTwo)

return merge (arrOne, arrTwo)

merge(arr a, arr b)
array c

while( a and b have elements )
if a[0] > b[0]
add b[0] to the end of c
remove b[0] from b
else
add a[0] to the end of c
remove a[0] from a

// at this point either a or b is empty

while ( a has elements )
add a[0] to the end of c
remove a[0] from a

while( b has elements)
add b[0] to the end of c
remove b[0] from b
return c

Question 6

what is worst case time complexity of merge sort

Answer 6

O (n log n)

Question 7

write code in C

Answer 7

include <stdio.h></stdio.h>

void merge_sort(int a[], int length);
void merge_sort_rec(int a[], int l, int r);
void merge_sorted_arrays(int a[], int l, int m, int r);

int main()
{
printf(“hello there”);

int array[] = {9, 6, 7, 8, 0, 3, 2, 1, 4, 5 }
int length = 10;


merge_sort(array, length);

for (int i=0; i < length; i++) 
    printf("%d", array[i]);
printf("\n");




return 0; }

void merge_sort(int a[], int length){
merge_sort_rec(a, 0, length - 1);
}

void merge_sort_rec(int a[], int l, int r){
int m = 1 + (r - 1) / 2;
}

// incomplete -yt: portfolio courses

Question 8

another video

Answer 8

https://www.youtube.com/watch?v=9vLuZ2SSLlI

Question 9

explain quick sort

Answer 9

QS is also an recursive algorithm

Question 10

which word to think off when QS comes

Answer 10

pivot

Question 11

is QS preferred more than other sorting algorithms

Answer 11

yes, more efficient and effectiveness

Question 12

QS in C

Answer 12

include <stdio.h></stdio.h>

// Function to swap two elements
void swap(int* a, int* b) {
int t = *a;
*a = *b;
*b = t;
}
int partition(int arr[], int low, int high) {
int pivot = arr[high];
int i = (low - 1);

for (int j = low; j <= high - 1; j++) {  
    if (arr[j] < pivot) {  
        i++;  
        swap(&arr[i], &arr[j]);  
    }  
}  
swap(&arr[i + 1], &arr[high]);  
return (i + 1);   }   void quickSort(int arr[], int low, int high) {  
if (low < high) {  
    int pi = partition(arr, low, high);  
    quickSort(arr, low, pi - 1);  
    quickSort(arr, pi + 1, high);  
}   }  

// Function to print the array
void printArray(int arr[], int size) {
int i;
for (i = 0; i < size; i++)
printf(“%d “, arr[i]);
printf(“\n”);
}

int main() {
int arr[] = { 12, 17, 6, 25, 1, 5 };
int n = sizeof(arr) / sizeof(arr[0]);
quickSort(arr, 0, n - 1);
printf(“Sorted array: \n”);
printArray(arr, n);
return 0;
}
</stdio.h>

Question 13

bubble sort