Sorting Solution Code Example

Quick Sort - Quick Sort works by selecting a #include <stdio.h>

"pivot" element from the array and partitioning the
other elements into two sub-arrays, according to // Function to swap two numbers
whether they are less than or greater than the void swap(int *a, int *b) {
int temp = *a;
pivot. The sub-arrays are then sorted recursively.
*a = *b;
*b = temp;
}
Problem to Solve: 94925
// Partition function
1. Initial Array: [9, 4, 9, 2, 5] int partition(int arr[], int low, int high) {
2. Choose Pivot: Let's choose the last element int pivot = arr[high]; // pivot
as the pivot (5). int i = (low - 1); // Index of smaller element
3. Partitioning:
o Elements less than 5: [4, 2]
for (int j = low; j < high; j++) {
o Elements greater than 5: [9, 9]
// If current element is smaller than the pivot
o Pivot remains in its sorted position.
if (arr[j] < pivot) {
4. Recursive Steps: i++; // Increment index of smaller element
o Sort [4, 2] → Pivot: 2 → [2] + 4
swap(&arr[i], &arr[j]);
o Sort [9, 9] → Already sorted.
}
5. Combine: [2, 4] + [5] + [9, 9] = [2, 4, 5, 9, 9] }
swap(&arr[i + 1], &arr[high]);
Program output: return (i + 1);
}

// Quick Sort function

void quickSort(int arr[], int low, int high) {
if (low < high) {
// Partitioning index
int pi = partition(arr, low, high);

// Separately sort elements before

// partition and after partition
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}

// Function to print an array

void printArray(int arr[], int size) {
for (int i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}

int main() {
int n;

printf("Enter the number of elements: ");

scanf("%d", &n);

int arr[n];
printf("Enter the elements of the array:\n");
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}

printf("Original array: ");

printArray(arr, n);

quickSort(arr, 0, n - 1);

printf("Sorted array: ");

printArray(arr, n);

return 0;
}
 #include <stdio.h>
Bubble Sort repeatedly steps through the list,
compares adjacent elements, and swaps them if // Function to perform Bubble Sort
they are in the wrong order. The process continues void bubbleSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
until the array is sorted.
// Last i elements are already sorted
for (int j = 0; j < n - i - 1; j++) {
Steps for 94925
if (arr[j] > arr[j + 1]) {
// Swap arr[j] and arr[j + 1]
1. Initial Array: [9, 4, 9, 2, 5]
int temp = arr[j];
2. Pass 1:
arr[j] = arr[j + 1];
arr[j + 1] = temp;
• Compare 9 and 4 → Swap → [4, 9, 9, 2, 5] }
• Compare 9 and 9 → No swap → [4, 9, 9, 2, 5] }
• Compare 9 and 2 → Swap → [4, 9, 2, 9, 5] }
• Compare 9 and 5 → Swap → [4, 9, 2, 5, 9] }

3. Pass 2: // Function to print an array

void printArray(int arr[], int size) {
• Compare 4 and 9 → No swap → [4, 9, 2, 5, 9] for (int i = 0; i < size; i++)
• Compare 9 and 2 → Swap → [4, 2, 9, 5, 9] printf("%d ", arr[i]);
• Compare 9 and 5 → Swap → [4, 2, 5, 9, 9] printf("\n");
• Compare 9 and 9 → No swap → [4, 2, 5, 9, 9] }

4. Pass 3: int main() {

int n;
• Compare 4 and 2 → Swap → [2, 4, 5, 9, 9]
• Compare 4 and 5 → No swap → [2, 4, 5, 9, 9] printf("Enter the number of elements: ");
• Compare 5 and 9 → No swap → [2, 4, 5, 9, 9] scanf("%d", &n);

int arr[n];
5. Pass 4:
printf("Enter the elements of the array:\n");
for (int i = 0; i < n; i++) {
• No swaps needed; the array is sorted.
scanf("%d", &arr[i]);
}
Program output:
printf("Original array: ");
printArray(arr, n);

bubbleSort(arr, n);

printf("Sorted array: ");

printArray(arr, n);

return 0;
}
 #include <stdio.h>
Selection Sort divides the array into two parts: the
sorted part and the unsorted part. It repeatedly // Function to perform Selection Sort
selects the smallest (or largest) element from the void selectionSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
unsorted part and moves it to the sorted part.
// Find the minimum element in the unsorted part
int minIndex = i;
Steps for 94925 for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
1. Initial Array: [9, 4, 9, 2, 5] minIndex = j;
2. Pass 1: }
o Find the smallest element (2). }
o Swap 2 with the first element → [2, 4, 9, // Swap the found minimum element with the first
9, 5]. element of the unsorted part
3. Pass 2: int temp = arr[minIndex];
o Find the smallest element in the arr[minIndex] = arr[i];
remaining array (4). arr[i] = temp;
o No swap needed → [2, 4, 9, 9, 5]. }
4. Pass 3: }
o Find the smallest element in the
remaining array (5). // Function to print an array
o Swap 5 with the first unsorted element void printArray(int arr[], int size) {
(9) → [2, 4, 5, 9, 9]. for (int i = 0; i < size; i++)
5. Pass 4: printf("%d ", arr[i]);
o Remaining elements (9 and 9) are printf("\n");
already sorted. }

Program output: int main() {

int n;

printf("Enter the number of elements: ");

scanf("%d", &n);

int arr[n];
printf("Enter the elements of the array:\n");
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}

printf("Original array: ");

printArray(arr, n);

selectionSort(arr, n);

printf("Sorted array: ");

printArray(arr, n);

return 0;
}
 #include <stdio.h>
Merge Sort is a divide-and-conquer algorithm. It
systematically splits the array into smaller // Function to merge two subarrays
subarrays, sorts those subarrays, and merges void merge(int arr[], int left, int mid, int right) {
int n1 = mid - left + 1;
them back together to form a sorted array.
int n2 = right - mid;
How It Works // Create temporary arrays
int L[n1], R[n2];
1. Divide the Array:
o Split the array into two halves // Copy data to temporary arrays
repeatedly until each subarray has for (int i = 0; i < n1; i++)
only one element (a single element L[i] = arr[left + i];
is always sorted). for (int j = 0; j < n2; j++)
2. Conquer (Sort and Merge): R[j] = arr[mid + 1 + j];
o Combine (merge) two sorted
subarrays into a single sorted array. // Merge the temporary arrays back into arr[left...right]
int i = 0, j = 0, k = left;
During the merging process:
while (i < n1 && j < n2) {
▪ Compare the elements of
if (L[i] <= R[j]) {
both subarrays. arr[k] = L[i];
▪ Place the smaller element i++;
into the resulting array. } else {
▪ Continue until all elements arr[k] = R[j];
from both subarrays are j++;
added to the result. }
3. Combine Results: k++;
o The merging process continues }
recursively, resulting in the fully
// Copy the remaining elements of L[], if any
sorted array.
while (i < n1) {
arr[k] = L[i];
Steps for Example Array: [9, 4, 9, 2, 5] i++;
k++;
1. Initial Array: [9, 4, 9, 2, 5] }

• Split into two halves: [9, 4, 9] and [2, 5]. // Copy the remaining elements of R[], if any
while (j < n2) {
arr[k] = R[j];
2. Divide Further: j++;
k++;
• Split [9, 4, 9] into [9] and [4, 9]. }
}
• Split [4, 9] into [4] and [9].
// Function to perform Merge Sort
• Split [2, 5] into [2] and [5].
void mergeSort(int arr[], int left, int right) {
if (left < right) {
3. Start Merging: int mid = left + (right - left) / 2;

// Recursively sort the two halves

• Merge [4] and [9] → [4, 9]. mergeSort(arr, left, mid);
• Merge [9] and [4, 9] → [4, 9, 9]. mergeSort(arr, mid + 1, right);

• Merge [2] and [5] → [2, 5]. // Merge the sorted halves
merge(arr, left, mid, right);
4. Final Merge: }
}

• Merge [4, 9, 9] and [2, 5] → [2, 4, 5, 9, 9]. // Function to print an array

void printArray(int arr[], int size) {
for (int i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
int main() {
int n;

printf("Enter the number of elements: ");

scanf("%d", &n);

int arr[n];
printf("Enter the elements of the array:\n");
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}

printf("Original array: ");

printArray(arr, n);

mergeSort(arr, 0, n - 1);

printf("Sorted array: ");

printArray(arr, n);

return 0;
}