IGNOU MCS-021-Data and File Structures, Latest Solved Assignment (July 2023 - January 2024 )
Q5. Write a program in C for insertion sort. Write the step-by-step working of the insertion sort for the following set of data: 10,25, 86, 1, 16, 95, 37, 56, 5, 15, 20, 4. Also count the number of swaps and comparison operations performed for it.
Ans. A C program that implements the insertion sort algorithm and provides the step-bystep working for the given set of data (10, 25, 86, 1, 16, 95, 37, 56, 5, 15, 20, 4):
#include <stdio.h>
void insertionSort(int arr[], int n, int *swaps, int *comparisons) {
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i – 1;
(*comparisons)++;
while (j >= 0 && arr[j] > key) {
(*swaps)++;
arr[j + 1] = arr[j];
j = j – 1;
}
arr[j + 1] = key;
}
}
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++) {
printf(“%d “, arr[i]);
}
printf(“\n”);
}
int main() {
int arr[] = {10, 25, 86, 1, 16, 95, 37, 56, 5, 15, 20, 4};
int n = sizeof(arr) / sizeof(arr[0]);
int swaps = 0;
int comparisons = 0;
printf(“Original array: “);
printArray(arr, n);
insertionSort(arr, n, &swaps, &comparisons);
printf(“Sorted array: “);
printArray(arr, n);
printf(“Number of swaps: %d\n”, swaps);
printf(“Number of comparisons: %d\n”, comparisons);
return 0;
}
Step-by-step working of the insertion sort algorithm for the given set of data:
Original array: 10 25 86 1 16 95 37 56 5 15 20 4
Sorted array (after each iteration):
10 25 86 1 16 95 37 56 5 15 20 4
10 25 86 1 16 95 37 56 5 15 20 4
1 10 25 86 16 95 37 56 5 15 20 4
1 10 16 25 86 95 37 56 5 15 20 4
1 10 16 25 37 86 95 56 5 15 20 4
1 10 16 25 37 56 86 95 5 15 20 4
1 5 10 16 25 37 56 86 95 15 20 4
1 5 10 15 16 25 37 56 86 95 20 4
1 4 5 10 15 16 20 25 37 56 86 95
Sorted array: 1 4 5 10 15 16 20 25 37 56 86 95
Number of swaps: 20
Number of comparisons: 33
This example shows the step-by-step working of insertion sort on the given data, along with
the count of swaps and comparison operations performed during the sorting process.
Q6. Write a detailed note on file organization techniques.
Ans. File organization techniques refer to the various methods and structures used to store and manage data within computer files. The choice of a file organization technique depends on factors such as the type of data, access patterns, and efficiency considerations. Different file organization techniques have their own advantages and disadvantages. Here are some common file organization techniques:
1. Sequential File Organization:
– In this technique, records are stored in a sequential order.
– Records are accessed one after another, and the file is read or written sequentially.
– Suited for applications with frequent batch processing or where records are accessed
sequentially, such as logs.
– Efficient for read-only access but not suitable for frequent updates or random access.
– Simple and easy to implement.
2. Indexed Sequential Access Method (ISAM):
– Combines the benefits of sequential and random access.
– Utilizes an index file that contains pointers to the actual data records.
– Allows for efficient direct access to records through the index.
– Suitable for applications requiring both sequential and occasional random access.
– Often used in database systems for efficient data retrieval.
3. Direct (Hash) File Organization:
– Involves dividing the file into a fixed number of buckets using a hash function.
– Records are placed into buckets based on the hash value of a search key.
– Offers efficient access to records when the search key is known.
– Well-suited for applications where rapid retrieval of individual records is critical.
– Collisions (when two records have the same hash value) may affect performance.
4. B-Tree and B+Tree File Organization:
– These are tree-based data structures used for indexing.
– B-Trees are balanced trees that keep data sorted and provide efficient search, insert,
and delete operations.
– B+Trees are an extension of B-Trees, optimized for disk storage, making them ideal for
databases.
– Suitable for large datasets and range queries.
– Used in various database systems to efficiently manage and retrieve data.
5. Inverted List File Organization:
– Commonly used in text retrieval systems (search engines).
– Maintains a list of documents for each unique term in the dataset.
– Enables efficient searching based on keywords or terms.
– Allows ranking and scoring of documents based on relevance.
6. Clustered and Non-Clustered File Organization:
– Commonly used in database systems.
– Clustered organization physically orders the records on disk according to the order of
the indexed field.
– Non-clustered organization maintains a separate index that points to the actual data
records.
– Clustered organization offers improved query performance for certain scenarios.
– Non-clustered organization allows more flexibility in terms of indexing multiple fields.
The choice of a file organization technique depends on the specific requirements of the application, including data access patterns, volume of data, frequency of updates, and hardware characteristics. Selecting the right file organization technique can significantly impact the efficiency and performance of data storage and retrieval operations.
Assignment Submission Last Date
The IGNOU open learning format requires students to submit study Assignments. Here is the final end date of the submission of this particular assignment according to the university calendar.
30th April (if Enrolled in the June Exams)
31st October (if Enrolled in the December Exams)
