Sort in Descending Order: flowchart, algorithm and program
This program reads n numbers into an array and sorts them from largest to smallest using an exchange sort, then prints the result. For each position i, it compares a[i] with every later element a[j] and swaps them whenever a[i] is smaller.
▶ Watch the dry run step by step →
Algorithm
- Step 1: Start.
- Step 2: Read n.
- Step 3: Set i = 0.
- Step 4: If i < n, go to step 5; otherwise go to step 7.
- Step 5: Read a[i].
- Step 6: Set i = i + 1. Go to step 4.
- Step 7: Set i = 0.
- Step 8: If i < n - 1, go to step 9; otherwise go to step 15.
- Step 9: Set j = i + 1.
- Step 10: If j < n, go to step 11; otherwise go to step 14.
- Step 11: If a[i] < a[j], go to step 12; otherwise go to step 13.
- Step 12: Swap a[i] and a[j] using temp.
- Step 13: Set j = j + 1. Go to step 10.
- Step 14: Set i = i + 1. Go to step 8.
- Step 15: Set i = 0.
- Step 16: If i < n, go to step 17; otherwise go to step 19.
- Step 17: Print a[i].
- Step 18: Set i = i + 1. Go to step 16.
- Step 19: Stop.
Pseudocode
BEGIN
READ n
i ← 0
WHILE i < n DO
READ a[i]
i ← i + 1
END WHILE
i ← 0
WHILE i < n - 1 DO
j ← i + 1
WHILE j < n DO
IF a[i] < a[j] THEN
Swap a[i] and a[j] using temp
END IF
j ← j + 1
END WHILE
i ← i + 1
END WHILE
i ← 0
WHILE i < n DO
PRINT a[i]
i ← i + 1
END WHILE
END
Program in C, Python and Java
Sort in Descending Order program in C
#include <stdio.h>
int main() {
int n, i, j, temp;
int a[100];
printf("Enter n: ");
scanf("%d", &n);
printf("Enter %d numbers: ", n);
for (i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
for (i = 0; i < n - 1; i++) {
for (j = i + 1; j < n; j++) {
if (a[i] < a[j]) {
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
}
printf("Sorted in descending order: ");
for (i = 0; i < n; i++) {
printf("%d ", a[i]);
}
printf("\n");
return 0;
}Sort in Descending Order program in Python
n = int(input("Enter n: "))
a = list(map(int, input("Enter " + str(n) + " numbers: ").split()))
for i in range(n - 1):
for j in range(i + 1, n):
if a[i] < a[j]:
temp = a[i]
a[i] = a[j]
a[j] = temp
print("Sorted in descending order:", end=" ")
for i in range(n):
print(a[i], end=" ")
print()Sort in Descending Order program in Java
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("Enter n: ");
int n = sc.nextInt();
int[] a = new int[n];
System.out.print("Enter " + n + " numbers: ");
for (int i = 0; i < n; i++) {
a[i] = sc.nextInt();
}
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
if (a[i] < a[j]) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
}
System.out.print("Sorted in descending order: ");
for (int i = 0; i < n; i++) {
System.out.print(a[i] + " ");
}
System.out.println();
}
}
Sample input: n = 5, numbers = 4 9 1 7 3
Output: Sorted in descending order: 9 7 4 3 1
How it works
- The numbers are read into the array a[0..n-1] with a loop that runs i from 0 to n-1.
- The outer loop picks a position i from 0 to n-2. After each pass, a[i] holds the largest value among the elements from i to the end.
- The inner loop runs j from i+1 to n-1 and checks if (a[i] < a[j]). If so, the two values are out of order for descending sorting.
- To fix that, the swap uses temp: temp = a[i]; a[i] = a[j]; a[j] = temp. The larger value moves to position i.
- With 4 9 1 7 3: pass i=0 brings 9 to the front, i=1 puts 7 next, i=2 puts 4, and i=3 puts 3, giving 9 7 4 3 1.
- Finally, a last loop prints a[0] to a[n-1], which are now in descending order.
Dry run (trace table)
| Step | Line | Box | n | i | a | j | temp | Output |
|---|---|---|---|---|---|---|---|---|
| 1 | 3 | Start | ||||||
| 2 | 8 | Read n | 5 | |||||
| 3 | 11 | i = 0 | 5 | 0 | ||||
| 4 | 11 | i < n? | 5 | 0 | ||||
| 5 | 12 | Read a[i] | 5 | 0 | [4] | |||
| 6 | 11 | i = i + 1 | 5 | 1 | [4] | |||
| 7 | 11 | i < n? | 5 | 1 | [4] | |||
| 8 | 12 | Read a[i] | 5 | 1 | [4,9] | |||
| 9 | 11 | i = i + 1 | 5 | 2 | [4,9] | |||
| 10 | 11 | i < n? | 5 | 2 | [4,9] | |||
| 11 | 12 | Read a[i] | 5 | 2 | [4,9,1] | |||
| 12 | 11 | i = i + 1 | 5 | 3 | [4,9,1] | |||
| 13 | 11 | i < n? | 5 | 3 | [4,9,1] | |||
| 14 | 12 | Read a[i] | 5 | 3 | [4,9,1,7] | |||
| 15 | 11 | i = i + 1 | 5 | 4 | [4,9,1,7] | |||
| 16 | 11 | i < n? | 5 | 4 | [4,9,1,7] | |||
| 17 | 12 | Read a[i] | 5 | 4 | [4,9,1,7,3] | |||
| 18 | 11 | i = i + 1 | 5 | 5 | [4,9,1,7,3] | |||
| 19 | 11 | i < n? | 5 | 5 | [4,9,1,7,3] | |||
| 20 | 15 | i = 0 | 5 | 0 | [4,9,1,7,3] |
Time and space complexity
Time: O(n²) · Space: O(1). The nested loops compare every pair of elements, about n(n-1)/2 comparisons, and sorting is done in place with only a temp variable.
Common mistakes
- Using a[i] > a[j] in the comparison. That sorts in ascending order, not descending.
- Swapping without temp (a[i] = a[j]; a[j] = a[i];). This overwrites a value, so both positions end up holding the same number.
- Running the outer loop to n instead of n-1, or starting j at i instead of i+1. This compares an element with itself, or reads past the array end.
Viva questions
Q1. What does the condition a[i] < a[j] on line 17 check, and why is it '<' and not '>'?
It checks whether the earlier element is smaller than a later one. If so, we swap so the bigger value moves to position i, which gives descending order. Using '>' would sort in ascending order.
Q2. Why do we need the variable temp in lines 18-20?
To swap two values we must save one before overwriting it. Without temp, a[i] = a[j] would destroy the old a[i] and both positions would hold the same value.
Q3. Why does the outer loop run only up to i < n - 1, and the inner loop start from j = i + 1?
The inner loop compares a[i] with every element after it. When i is the last index there is nothing after it to compare, so the outer loop can stop at n - 2. Starting j at i + 1 avoids comparing an element with itself or with the already-fixed earlier positions.
Q4. After the first pass of the outer loop (i = 0), what is guaranteed about a[0]?
a[0] holds the largest element of the whole array, because it was compared with every other element and swapped whenever a larger one was found. Each later pass fixes the next largest value in a[i].
Q5. What happens if the user enters n = 1, n = 0, or a negative n?
For n = 1 the outer loop condition 0 < 0 is false, so no sorting is done and the single number is printed. For n = 0 or negative, the input and sorting loops don't run and nothing but the message is printed. Also, n > 100 would overflow the array a[100], and the program doesn't check for that.
Q6. What happens if the array has duplicate values, for example 5 3 5?
Equal elements are not swapped because a[i] < a[j] is false when they are equal. The output is 5 5 3, which is correct. Since swaps only occur on strict inequality, no extra swaps are wasted on equal values.
Q7. Which sorting algorithm is this, and what is its time complexity?
It is an exchange sort, which is similar to selection sort. It does n(n-1)/2 comparisons in all cases, so the time complexity is O(n^2), with O(1) extra space. It is not efficient for large inputs.
Q8. What would you change to sort in ascending order, and how could you reduce the number of swaps?
Change the condition to a[i] > a[j] for ascending order. To reduce swaps, you could use real selection sort: find the index of the maximum in the inner loop and do just one swap per outer pass, so there are at most n-1 swaps.
Frequently asked questions
How do you sort an array in descending order in C?
Use two nested loops and swap a[i] and a[j] when a[i] < a[j]. After the loops finish, the array runs from largest to smallest.
What is the difference between ascending and descending sort in this code?
Only the comparison changes. Use a[i] > a[j] for ascending order and a[i] < a[j] for descending order.
What is the time complexity of this exchange sort?
It is O(n^2), because the nested loops make about n(n-1)/2 comparisons. That is fine for small arrays but slow for large ones.