CST201 DATA STRUCTURES
Assignment-2
Name: Shreyaj Dinesh
Class: S3 CSE
Roll No: 60
Date of submission :05/11/2024
1. Explain Quick Sort with an example ?
Answer:
Initial Array: [38, 27, 43, 3, 9, 82, 10]
1. Let’s pick the last element, 10, as our pivot.
2. Partitioning:
- Move elements smaller than 10 to the left and elements greater than 10 to the right.
- We initialize two pointers, `i` and `j`. `i` keeps track of the boundary between elements
smaller than 10 and those larger than it. `j` will iterate through the array.
Partition process:
- ( j=0 ): 38 > 10, so we leave it in place.
- ( j=1 ): 27 > 10, so no swap.
- ( j=2 ): 43 > 10, no swap.
- ( j=3 ): 3 < 10, so swap 3 with the element at ( i+1 ) (38), resulting in [3, 27, 43, 38, 9, 82, 10];
increment ( i ) to 0.
- ( j=4 ): 9 < 10, so swap 9 with the element at ( i+1 ) (27), giving [3, 9, 43, 38, 27, 82, 10];
increment ( i ) to 1.
Finally, we place the pivot in its correct position by swapping 10 with the element at ( i+1) (43),
giving us [3, 9, 10, 38, 27, 82, 43].
3. Recursively Apply Quick Sort:
- Now we have two subarrays: [3, 9] and [38, 27, 82, 43\].
4. Sort Left Subarray[3, 9]:
- Choose 9 as the pivot.
- Since 3 < 9, it remains in place.
- Array stays [3, 9].
5. Sort Right Subarray [38, 27, 82, 43]:
- Choose 43 as the pivot.
- Partition process:
- ( j=3 ): 38 < 43, no swap needed.
- ( j=4 ): 27 < 43, no swap.
- ( j=5 ): 82 > 43, so we leave it.
- Place the pivot 43 in its correct position by swapping with 82, resulting in [38, 27, 43, 82].
6. Further sorting will yield the final sorted array.
Sorted Array: [3, 9, 10, 27, 38, 43, 82]
Final Sorted Array: [3, 9, 10, 27, 38, 43, 82]
2. Write an algorithm for Quick sort ?
Answer:
Algorithm_QUICKSORT(A, low, high)
if low < high
pivotIndex = PARTITION(A, low, high)
QUICKSORT(A, low, pivotIndex - 1)
QUICKSORT(A, pivotIndex + 1, high)
Algorithm_PARTITION(A, low, high)
pivot = A[high]
i = low - 1
for j = low to high - 1
if A[j] < pivot
i=i+1
SWAP(A[i], A[j])
SWAP(A[i + 1], A[high])
return i + 1
Algorithm_SWAP(x, y)
temp = x
x=y
y = temp
3. Write a C program to implement Quick Sort ?
Answer:
#include <stdio.h>
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
int partition(int arr[], int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; 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);
}
}
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
int main() {
int arr[] = {3, 6, 8, 10, 1, 2, 1};
int n = sizeof(arr) / sizeof(arr[0]);
quickSort(arr, 0, n - 1);
printf("Sorted array: ");
printArray(arr, n);
return 0;
}
4. Explain Merge Sort with an example ?
Answer:
Initial Array: [38, 27, 43, 3, 9, 82, 10]
Steps:
1. Divide the Array:
- Split into [38, 27, 43] and [3, 9, 82, 10].
- Keep splitting recursively until we reach individual elements:
- [38, 27, 43] → [38] and [27, 43] → [27] and [43]
- [3, 9, 82, 10] → [3, 9] and [82, 10] → [3], [9], [82], [10]
2. Merge Step-by-Step:
- Merge [27] and [43] to get [27, 43].
- Merge [38] and [27, 43]: Compare each element, yielding [27, 38, 43].
- Merge [3] and [9] to get [3, 9].
- Merge [82] and [10] to get [10, 82].
- Merge [3, 9] and [10, 82] to get [3, 9, 10, 82].
- Merge [27, 38, 43] and [3, 9, 10, 82]:
- Compare each element: [3, 9, 10, 27, 38, 43, 82].
Sorted Array: [3, 9, 10, 27, 38, 43, 82]
5. Write an algorithm for Merge sort ?
Answer
Algorithm_MERGESORT(A, left, right)
if left < right
mid = (left + right) / 2
MERGESORT(A, left, mid)
MERGESORT(A, mid + 1, right)
MERGE(A, left, mid, right)
Algorithm_MERGE(A, left, mid, right)
n1 = mid - left + 1
n2 = right - mid
create arrays L[1...n1] and R[1...n2]
for i = 1 to n1
L[i] = A[left + i - 1]
for j = 1 to n2
R[j] = A[mid + j]
i = 1, j = 1, k = left
while i <= n1 and j <= n2
if L[i] <= R[j]
A[k] = L[i]
i=i+1
else
A[k] = R[j]
j=j+1
k=k+1
while i <= n1
A[k] = L[i]
i=i+1
k=k+1
while j <= n2
A[k] = R[j]
j=j+1
k=k+1
6. Write a C program to implement Merge Sort ?
Answer
#include <stdio.h>
void merge(int arr[], int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
int L[n1], R[n2];
for (int i = 0; i < n1; i++)
L[i] = arr[left + i];
for (int j = 0; j < n2; j++)
R[j] = arr[mid + 1 + j];
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j])
arr[k++] = L[i++];
else
arr[k++] = R[j++];
}
while (i < n1)
arr[k++] = L[i++];
while (j < n2)
arr[k++] = R[j++];
}
void mergeSort(int arr[], int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
int main() {
int arr[] = {3, 6, 8, 10, 1, 2, 1};
int n = sizeof(arr) / sizeof(arr[0]);
mergeSort(arr, 0, n - 1);
printf("Sorted array: ");
printArray(arr, n);
return 0;
}
7. Explain Heap Sort with an example ?
Answer
Initial Array: [38, 27, 43, 3, 9, 82, 10]
Steps:
1. Build Max Heap:
- Start from the middle of the array, applying heapify from right to left.
- Heapify index 2 (43): No changes needed.
- Heapify index 1 (27): Swap 27 with 82, giving [38, 82, 43, 3, 9, 27, 10].
- Heapify index 0 (38): Swap 38 with 82, resulting in [82, 38, 43, 3, 9, 27, 10].
2. Extract Max Element:
- Swap root (82) with last element (10), reduce heap size by 1.
- Reheapify the root to maintain max heap:
- New heap: [43, 38, 10, 3, 9, 27, 82].
3. Repeat Extraction:
- Swap root (43) with last element (27), reduce heap size.
- Reheapify to maintain max heap:
- New heap: [38, 27, 10, 3, 9, 43, 82].
- Continue until heap is empty.
Sorted Array: [3, 9, 10, 27, 38, 43, 82]
8. Write an algorithm for Heap sort ?
Answer
HEAPSORT(A)
BUILD_MAX_HEAP(A)
for i = length(A) down to 2
SWAP(A[1], A[i])
HEAPIFY(A, 1, i - 1)
BUILD_MAX_HEAP(A)
for i = floor(length(A) / 2) down to 1
HEAPIFY(A, i, length(A))
HEAPIFY(A, i, heapSize)
left = 2 * i
right = 2 * i + 1
largest = i
if left <= heapSize and A[left] > A[largest]
largest = left
if right <= heapSize and A[right] > A[largest]
largest = right
if largest != i
SWAP(A[i], A[largest])
HEAPIFY(A, largest, heapSize)
SWAP(x, y)
temp = x
x=y
y = temp
9. Write a C program to implement Heap Sort ?
Answer
#include <stdio.h>
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
void heapify(int arr[], int n, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest])
largest = left;
if (right < n && arr[right] > arr[largest])
largest = right;
if (largest != i) {
swap(&arr[i], &arr[largest]);
heapify(arr, n, largest);
}
}
void heapSort(int arr[], int n) {
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
for (int i = n - 1; i > 0; i--) {
swap(&arr[0], &arr[i]);
heapify(arr, i, 0);
}
}
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
int main() {
int arr[] = {3, 6, 8, 10, 1, 2, 1};
int n = sizeof(arr) / sizeof(arr[0]);
heapSort(arr, n);
printf("Sorted array: ");
printArray(arr, n);
return 0;
}
