C Program to Sort an Array in Descending Order
In this article, we will discuss the array sorting in descending order in C with its different sorting methods.
Array:
A collection of elements with the same data type stored in a line of memory is known as an array. As a result, it is easier to figure out where each element is by adding an offset to a base value, the location of the array's first element in memory (typically denoted by the array's name), or both.
Sorting an Array:
The process of placing an array's members in a particular order, usually from smallest to largest or largest to smallest, is called sorting an array. Sorting is done to make searching for, accessing, and working with array elements simpler.
- An array can be sorted using various techniques, each of which has benefits and drawbacks in terms of time and space complexity.
- Different ways to perform Sorting in descending order:
1.Bubble sort:
- Bubble Sort is an algorithm that iteratively traverses the list, compares nearby members, and swaps out any that are out of order.
- Until no swaps are required, the trip through the list is repeated, signifying that the list is sorted.
- Think about the following array of numbers that we wish to use Bubble Sort to sort in descending order:
Array: [7, 2, 9, 1, 5]
Step 1:
- The first two elements, 7 and 2, are compared. Since 2 > 7, we switch them.
- Swapped array: [7, 2, 9, 1, 5]
Step 2:
- Now, compare elements 2 and 3, which are 7 and 9. There is no need to swap.
- [7, 2, 9, 1, 5] are still in the array.
Step 3:
- Now, compare elements 9 and 1 in the third and fourth groups. 9 > 1; thus, we switch them.
- Swapped array: [7, 2, 1, 9, 5]
Step 4:
- Compare elements 9 and 5, the fourth and fifth. 5 > 9; therefore, we switch them.
- Swapped array: [7, 2, 1, 5, 9]
- The largest element (9), initially positioned at the end of the array, has now "bubbled up" to take its place.
Now, starting at the beginning of the array, we repeat the procedure:
Step 5:
- The first two elements, 7 and 2, are compared. Since 2 > 7, we switch them.
- Swapped array: [7, 2, 1, 5, 9]
Step 6:
- Compare elements 2 and 3, which are 7 and 1. Since 1 > 7, we switch them.
- Swapped array: [7, 1, 2, 5, 9]
Step 7:
- Compare elements 2 and 5 in the third and fourth places. No switch is required because of 2 and 5.
- [7, 1, 2, 5, 9] are still in the array.
Step 8:
- Compare elements 5 and 9, the fourth and fifth. No switch is required because 5 = 9.
- [7, 1, 2, 5, 9] are still in the array.
- The second-largest member (element 7) has "bubbled up" to the second-to-last place at this point, following the second run through the array.
Until there are no more swaps required, we carry on in this manner for the remaining passes. The largest unsorted element "bubbles up" to the proper position in each pass.
Step 9:
- The array is already sorted; therefore, swaps are not required.
Final array after sorting: [9, 7, 5, 2, 1]
- Until the entire array is sorted, the Bubble Sort algorithm frequently compares and swaps nearby elements.
- The largest parts "bubble up" to their correct placements in the decreasing order version.
- Bubble Sort has an O(n^2) time complexity, where n is the array's element count.
- Although not the most effective sorting technique for large arrays, it is straightforward to comprehend and use.
Program:
Let's take a program to understand the use of the bubble sort sorting algorithm in C.
#include <stdio.h>
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
void bubbleSortDescending(int arr[], int size) {
for (int i = 0; i < size - 1; i++) {
for (int j = 0; j < size - i - 1; j++) {
if (arr[j] < arr[j + 1]) {
swap(&arr[j], &arr[j + 1]);
}
}
}
}
int main() {
int size;
printf("Enter size of an array: ");
scanf("%d", &size);
int arr[size];
printf("Enter the elements of the array:\n");
for (int i = 0; i < size; i++) {
scanf("%d", &arr[i]);
}
bubbleSortDescending(arr, size);
printf("Array sorted in descending order:\n");
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
return 0;
}
Output:
![C Program to Sort an Array in Descending Order](https://static.tutorialandexample.com/c/c-program-to-sort-an-array-in-descending-order1.png)
2.Selection Sort:
- The sublist of things that have already been sorted and the sublist of items that still need to be sorted are separated from the input list.
- It repeatedly chooses the smallest member from the unsorted sublist (or the largest, depending on the order) and inserts it at the end of the sorted sublist.
Array: [64, 25, 12, 22, 11]
Step 1:
- Search the entire array for the element with the highest value. After that, swap it with the element in the first place.
- Exchange with the element at position 0 for a maximum of 64 elements (at index 0).
- After the swap, the array is [64, 25, 12, 22, 11].
Step 2:
- Locate the subarray's maximum element starting with the second element, and then swap it with the element in the second place.
- Elements may be swapped with those at index 1 up to a maximum of 25 (at index 1).
- After the swap, the array is [64, 25, 12, 22, 11].
Step 3:
- Starting with the third element, locate the subarray's largest element, and then swap it with the element in the third place.
- Maximum number of elements: 22 (at index 3); element at index 2 may be substituted.
- After the swap, the array is [64, 25, 22, 12, 11].
Step 4:
- Starting with the fourth element, locate the greatest element in the subarray and replace it with the element in the fourth position.
- A maximum number of elements: 12 (at index 2); an element at index 3 may be substituted.
- After the swap, the array is [64, 25, 22, 12, 11].
- The largest element (64) has been correctly positioned after the array's initial iteration.
Now, starting with the second component, we repeat the procedure until the array is sorted.
- The largest element is chosen from the unsorted segment and positioned correctly in each pass of the selection sort for decreasing order.
- Until the full array is sorted, this procedure is repeated. Selection Sort has an O(n^2) time complexity, where n is the array's element count.
Program:
Let's take a program to understand the use of the Selection sort algorithm in C.
#include <stdio.h>
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
void selectionSort(int arr[], int size) {
for (int i = 0; i < size - 1; i++) {
int maxIndex = i;
for (int j = i + 1; j < size; j++) {
if (arr[j] > arr[maxIndex]) {
maxIndex = j;
}
}
if (maxIndex != i) {
swap(&arr[i], &arr[maxIndex]);
}
}
}
int main() {
int size;
printf("Enter the size of the array: ");
scanf("%d", &size);
int arr[size];
printf("Enter the elements of the array:\n");
for (int i = 0; i < size; i++) {
scanf("%d", &arr[i]);
}
selectionSort(arr, size);
printf("Array sorted in descending order:\n");
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
return 0;
}
Output:
![C Program to Sort an Array in Descending Order](https://static.tutorialandexample.com/c/c-program-to-sort-an-array-in-descending-order2.png)
3. Insertion Sort:
- Using insertion sort, the final array of items is sorted one at a time.
- It takes each item from the input list and places it in the appropriate spot within the array's sorted section.
Think about the following array of numbers that we wish to use Insertion Sort to sort in descending order:
Array: [7, 2, 9, 1, 5]
Step 1:
- First, take the second component (2). After that, swap them since 7 > 2 when compared to the first element.
- Swapped array: [7, 2, 9, 1, 5]
Step 2:
- Think about element number three (9). Since 9 > 7, compare it to the second element (7) and swap the two.
- Swapped array: [9, 2, 7, 1, 5]
- Swap the first and third elements if the third element (9 is greater than element 7) and vice versa.
- Swapped array: [9, 7, 2, 1, 5]
Step 3:
- Think about the fourth component (1). Swap them since 9 > 1 by comparing them to the third element (9).
- Swapped array: [9, 7, 2, 9, 5]
- Swap the fourth element (9), which is compared to the second element (7), because (9 > 7).
- Swapped array: [9, 9, 2, 7, 5]
- Stop comparing the fourth element (9) because they are equal to the first element (9).
Step 4:
- Think about element number five (5). Since 9 > 5, compare it to the fourth element (9), and then swap the two.
- Swapped array: [9, 9, 2, 7, 9]
- Since 9 > 2, compare the third element (2) with the fifth element (9), and exchange them.
- Swapped array: [9, 9, 9, 7, 2]
- Swap the fifth element (9), which is compared to the second element (7), because (9 > 7).
- Swapped array: [9, 9, 7, 9, 2]
- The fifth element (9) should be swapped with the first element (9), so 9 > 9.
- Swapped array: [9, 9, 7, 2, 9]
Step 5:
- After making all necessary comparisons, element 9 is put in the proper place.
- Last array after sorting: [9, 9, 7, 2, 1]
C program:
Let's take a program to understand the use of the insertion sort algorithm in C.
#include <stdio.h>
void insertionSortDescending(int arr[], int size) {
for (int i = 1; i < size; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] < key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
int main() {
int size;
printf("Enter the size of the array: ");
scanf("%d", &size);
int arr[size];
printf("Enter the elements of the array:\n");
for (int i = 0; i < size; i++) {
scanf("%d", &arr[i]);
}
insertionSortDescending(arr, size);
printf("Array sorted in descending order:\n");
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
return 0;
}
Output:
![C Program to Sort an Array in Descending Order](https://static.tutorialandexample.com/c/c-program-to-sort-an-array-in-descending-order3.png)
4. Quick Sort:
- A sorting algorithm called Quick Sort uses the divide-and-conquer strategy to sort an array or a list quickly.
- It divides the remaining components into two sub-arrays, elements less than the pivot and elements more than the pivot, by choosing one of the array's "pivot" elements.
- The sub-arrays are next sorted recursively.
A detailed explanation of the Quick Sort algorithm is provided below:
Pick a Pivot:
First, pick a pivot element from the array. The pivotal element can be any of the following: first, last, middle, etc. The pivot selection will affect how well Quick Sort works.
Partitioning:
Rearrange the array's elements so that all those that are smaller than the pivot are to the left of it and all those that are larger than the pivot are to the right. The pivot is guaranteed to be in the proper sorted position due to this partitioning phase.
Recursive Sorting:
Apply the Quick Sort algorithm iteratively to the sub-arrays to the left and right of the pivot. The Quick Sort algorithm is applied individually to each sub-array.
Combine:
Combining the sub-arrays requires no further work after they have all been sorted because they are already in the right positions relative to the pivot.
Think about the following array of numbers that we wish to use Quick Sort to sort in descending order:
Array: [7, 2, 9, 1, 5]
Step 1:
- Pick a fulcrum point. Let's select element number five, the final component, as the pivot.
- Elements fewer than the pivot should be on the left, and elements greater than the pivot should be on the right as you divide the array around the pivot.
- Partitioning results: [2, 1, 5, 7, 9]
- The pivot (5) is positioned correctly in the sorted state.
Step 2:
- Apply Quick Sort in a recursive fashion to the sub-arrays to the left and right of the pivot.
- [2, 1] Left Sub-Array:
- Pick a pivot. As the pivot, let's use the last element, which is 1.
- Elements fewer than the pivot should be on the left, and elements greater than the pivot should be on the right as you divide the sub-array around the pivot.
- Following partitioning, the pivot (1) is in the proper sorted position: [1, 2].
- [7, 9] Right Sub-Array
- Pick a pivot. Let's select element nine, the final component, as the pivot.
- Elements fewer than the pivot should be on the left, and elements greater than the pivot should be on the right as you divide the sub-array around the pivot.
- Following partitioning, the pivot (9) is in the proper sorted position: [7, 9].
Step 3:
- The final sorted array is created by combining the sorted sub-arrays.
- Final array after sorting: [9, 7, 5, 2, 1]
- Here is an explanation of the stages involved in using Quick Sort to sort the array [7, 2, 9, 1, 5] in descending order:
- Choose partition [2, 1, 5, 7, 9] for pivot 5.
- Recursively sort the [2, 1] left sub-array: Select the first pivot. Partition: [1, 2].
- Right sub-array is recursively sorted [7, 9]. Select partition [7, 9] for pivot 9.
- Sorted subarrays are combined as follows: [1, 2] + [5] + [7, 9] = [9, 7, 5, 2, 1].
C Program:
Let's take a program to understand the use of the quick sort algorithm in C.
#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 - 1; j++) {
if (arr[j] >= pivot) { // Note: Greater than or equal to for descending order
i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return i + 1;
}
void quickSortDescending(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSortDescending(arr, low, pi - 1);
quickSortDescending(arr, pi + 1, high);
}
}
int main() {
int size;
printf("Enter the size of the array: ");
scanf("%d", &size);
int arr[size];
printf("Enter the elements of the array:\n");
for (int i = 0; i < size; i++) {
scanf("%d", &arr[i]);
}
quickSortDescending(arr, 0, size - 1);
printf("Array sorted in descending order using Quick Sort:\n");
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
return 0;
}
Output:
![C Program to Sort an Array in Descending Order](https://static.tutorialandexample.com/c/c-program-to-sort-an-array-in-descending-order4.png)