Data Structures Practices
Report
（2024-2025-1）
Departmen
Major Software Engineering
Class Data Structure
Student ID 23172503
Name Nawfal Essakhi
Due Date 2024.12.1
Content： Sorting Part 2
1. Write a program to implement the inserting algorithm.
2. Write a routine that implement quicksort, using median-of-three partitioning and a cutoff
of 3 (cutoff part use inserting sort). Besides, construct a permutation of 20 elements that
is as bad as possible.
Attach your source code and testing screenshot in the
report。
====================Write your code & screenshot below============
1.
#include <stdio.h>
// Function to perform Insertion Sort
void insertionSort(int arr[], int n) {
// Iterate through the array starting from the second element
for (int i = 1; i < n; i++) {
int key = arr[i]; // Current element to be placed in the correct position
int j = i - 1; // Start comparing with the element just before the current one
// Move elements of arr[0..i-1] that are greater than `key` to one position
ahead
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j]; // Shift the larger element one position to the right
j--; // Move to the previous element
}
// Place the `key` element in its correct position
arr[j + 1] = key;
}
}
// Function to display the array
void displayArray(int arr[], int n) {
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]); // Print each element followed by a space
}
printf("\n"); // Move to the next line after printing all elements
}
int main() {
// Define an array to be sorted
int arr[] = {12, 11, 13, 5, 6};
// Calculate the number of elements in the array
int n = sizeof(arr) / sizeof(arr[0]);
printf("Original array: ");
// Print the array before sorting
displayArray(arr, n);
// Call the insertionSort function to sort the array
insertionSort(arr, n);
printf("Sorted array: ");
// Print the array after sorting
displayArray(arr, n);
return 0; // Indicate successful program termination
}
Screenshots:
2.
#include <stdio.h>
// Function to perform Insertion Sort
void insertionSort(int arr[], int low, int high) {
for (int i = low + 1; i <= high; i++) {
int key = arr[i];
int j = i - 1;
while (j >= low && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
// Function to find the median of three elements and return the pivot index
int medianOfThree(int arr[], int low, int high) {
int mid = low + (high - low) / 2;
if (arr[low] > arr[mid]) {
int temp = arr[low];
arr[low] = arr[mid];
arr[mid] = temp;
}
if (arr[low] > arr[high]) {
int temp = arr[low];
arr[low] = arr[high];
arr[high] = temp;
}
if (arr[mid] > arr[high]) {
int temp = arr[mid];
arr[mid] = arr[high];
arr[high] = temp;
}
// Now arr[low] <= arr[mid] <= arr[high]
return mid;
}
// Partition function for Quicksort using the median-of-three pivot
int partition(int arr[], int low, int high) {
// Find the median of the three
int pivotIndex = medianOfThree(arr, low, high);
int pivot = arr[pivotIndex];
// Move pivot to the end
int temp = arr[pivotIndex];
arr[pivotIndex] = arr[high];
arr[high] = temp;
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] <= pivot) {
i++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// Move the pivot to its correct position
arr[high] = arr[i + 1];
arr[i + 1] = pivot;
return i + 1;
}
// Function to perform Quicksort with median-of-three partitioning and cutoff for
insertion sort
void quicksort(int arr[], int low, int high) {
if (high - low + 1 <= 3) {
// If the subarray is small, use Insertion Sort
insertionSort(arr, low, high);
} else {
if (low < high) {
int pivotIndex = partition(arr, low, high);
// Recursively sort the left and right parts of the array
quicksort(arr, low, pivotIndex - 1);
quicksort(arr, pivotIndex + 1, high);
}
}
}
// Function to display the array
void displayArray(int arr[], int n) {
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
// Function to generate the worst-case permutation of 20 elements for Quicksort
void generateWorstCasePermutation(int arr[], int n) {
for (int i = 0; i < n; i++) {
arr[i] = i + 1;
}
// Reverse the array to make it the worst-case scenario
for (int i = 0; i < n / 2; i++) {
int temp = arr[i];
arr[i] = arr[n - i - 1];
arr[n - i - 1] = temp;
}
}
int main() {
// Create an array of 20 elements with the worst-case permutation
int arr[20];
generateWorstCasePermutation(arr, 20);
printf("Original (Worst-case) array: ");
displayArray(arr, 20);
// Perform quicksort on the array
quicksort(arr, 0, 19);
printf("Sorted array: ");
displayArray(arr, 20);
return 0;
}
