LPU_Colab

admin.lpucolab438.examly.io/course

DSA_Unit 4_Lecture 24 Coding

Test Summary

No. of Sections: 1
No. of Questions: 12
Total Duration: 90 min

Section 1 - Coding
Section Summary

No. of Questions: 12
Duration: 90 min

Additional Instructions:

None
Q1.
Problem Statement

Imagine you are a software developer working for a logistics company. Your task is to
create a program that can efficiently sort a list of packages based on their weights using
the Quick-Sort algorithm. Each package has a weight value associated with it.

The program should take an array of package objects as input, where each object
contains the weight of a package. The program should then sort the array in ascending
order based on the weights of the packages.

Input Format
The first line of input consists of an integer N, representing the number of packages.

The second line consists of N integers, representing the weight of the packages,
separated by space.

Output Format
The output displays N integers representing the weights of the packages after they have
been sorted in ascending order.

Constraints
N>0

1/56
weight > 0

Sample Input Sample Output

4
15 25 35 10

10 15 25 35

Sample Input Sample Output

3
120 60 80

60 80 120

Time Limit: - ms Memory Limit: - kb Code Size: - kb

Q2.
Problem Statement

Imagine you are a computer programmer tasked with creating a program to organize a
collection of years in ascending order. This program will take a list of years as input and
efficiently sort them using the Quick-Sort algorithm, ensuring that the years are arranged
chronologically.

Input Format
The first line of input consists of an integer N, representing the number of years.

The second line consists of N space-separated integers, representing the years.

Output Format
The output prints the sorted dates in chronological order.

Constraints
N>0

Each year is a 4-digit positive integer.

Sample Input Sample Output

5
2014 2009 2000 1997 1865

1865 1997 2000 2009 2014

Sample Input Sample Output

3
1496 3015 2056

1496 2056 3015

2/56
Time Limit: - ms Memory Limit: - kb Code Size: - kb
Q3.
Problem Statement

Imagine you are a teacher preparing the final grades for your class. You have a list of
your students' GPAs, and you want to see who performed the best in the class. You
decide to use this program to quickly sort and display the GPAs in descending order to
identify the top students based on their GPAs.

Your task is to implement a recursive function using the Quick-Sort algorithm. The
program should prompt the user for the number of students, input the GPA, and sort the
same in descending order.

Input Format
The first line of input consists of an integer N, representing the number of students.

The second line consists of N floating point numbers, representing the GPA of the
students.

Output Format
The output prints the sorted GPAs in descending order, from the highest GPA to the
lowest, rounded off to one decimal place.

Constraints
N>0

Sample Input Sample Output

3
3.6 4.4 2.9

4.4 3.6 2.9

Sample Input Sample Output

6
1.2 4.9 3.5 2.7 5.0 3.1

5.0 4.9 3.5 3.1 2.7 1.2

Time Limit: - ms Memory Limit: - kb Code Size: - kb

Q4.
Problem Statement

3/56
You are working on a project to implement a feature that displays the list of users in
alphabetical order based on their names.

To achieve this, you decide to use the Quick-Sort algorithm to efficiently sort the names.
The user inputs the number of users and then the name of each user. Once the names
are collected, the program must apply the Quick Sort algorithm to sort and display the
names in alphabetical order.

Note: This kind of question will be helpful in clearing Capgemini recruitment.

Input Format
The first line of input consists of an integer N, representing the number of users.

The following N lines consist of the names of the users (starting with uppercase letters).

Output Format
The output prints the sorted list of names in alphabetical order.

Constraints
N>0

Sample Input Sample Output

5
Alice
Denver
Aadhil
Charlie
Zen

Aadhil
Alice
Charlie
Denver
Zen

Sample Input Sample Output

6
Chandler
Monica
Ross
Joey
Rachel
Phoebe

4/56
Chandler
Joey
Monica
Phoebe
Rachel
Ross

Time Limit: - ms Memory Limit: - kb Code Size: - kb

Q5.
Problem Statement

You are working as a software engineer at a technology company, and your team is
developing a utility tool for sorting binary numbers efficiently. The utility is designed to sort
an array of integers based on the number of 1s in their binary representation. In case of
two or more integers having the same number of 1s, you need to sort them in ascending
order.

Write a program that takes an array of integers as input and uses the Quick-Sort
algorithm to sort the integers in ascending order based on the number of 1s in their binary
representation.

Example 1

Input:

arr = [0,1,2,3,4,5,6,7,8]

Output:

[0,1,2,4,8,3,5,6,7]

Explanation:

[0] is the only integer with 0 bits.

[1,2,4,8] all have 1 bit.

[3,5,6] have 2 bits.

5/56
[7] has 3 bits.

The sorted array by bits is [0,1,2,4,8,3,5,6,7]

Example 2

Input:

arr = [1024,512,256,128,64,32,16,8,4,2,1]

Output:

[1,2,4,8,16,32,64,128,256,512,1024]

Explanation:

All integers have 1 bit in the binary representation, you should just sort them in ascending
order.

Input Format
The first line of input consists of an integer N, representing the number of elements.

The second line consists of N array elements, separated by space.

Output Format
The output prints the sorted integers in ascending order based on the number of 1s in
their binary representation.

Constraints
N>0

Sample Input Sample Output

9
0 1 2 3 4 5 6 7 8

0 1 2 4 8 3 5 6 7

Sample Input Sample Output

11
1024 512 256 128 64 32 16 8 4 2 1

1 2 4 8 16 32 64 128 256 512 1024

6/56
Time Limit: - ms Memory Limit: - kb Code Size: - kb
Q6.
Problem Statement

You've received a secret message encoded as an array of characters. Unfortunately, the

characters are all jumbled up.

Your mission is to write a program that can unscramble the message by sorting the
characters in ascending order using the Quick-Sort algorithm.

Input Format
The first line of input consists of an integer N, representing the number of characters.

The second line consists of N space-separated characters.

Output Format
The output prints the sorted characters in ascending order.

Constraints
N>0

Sample Input Sample Output

5
b n h u j

b h j n u

Sample Input Sample Output

6
w e r h j k

e h j k r w

Time Limit: - ms Memory Limit: - kb Code Size: - kb

Q7.
Problem Statement

You are working as a software developer at a language processing company. As part of

the company's text processing system, you need to sort a collection of words in reverse
lexicographical (dictionary) order using the Quick-Sort algorithm.

7/56
Write a program that takes an array of words as input and uses the QuickSort algorithm to
sort the words in reverse lexicographical order.

Input Format
The first line of input consists of an integer N, representing the number of strings.

The second line consists of N strings, separated by space.

Output Format
The output displays the words sorted in reverse lexicographical order.

Constraints
N>0

Sample Input Sample Output

2
Cap Cat

Cat Cap

Sample Input Sample Output

5
Chair Door Mouse Keyboard Table

Table Mouse Keyboard Door Chair

Time Limit: - ms Memory Limit: - kb Code Size: - kb

Q8.
Problem Statement

You are given an array of integers containing both negative and positive numbers. Your
task is to rearrange the elements in such a way that all negative numbers come before
the positive numbers. After rearranging, you need to sort the numbers in ascending order
using the Quick-Sort algorithm.

Implement the following functions:

1. rearrangeNegativesBeforePositives(int arr[], int n): This function takes an array

of integers arr and its size n as input. It should rearrange the elements so that all
negative numbers appear before the positive numbers while maintaining the relative
order of negative and positive numbers.

8/56
 2. quickSort(int arr[], int low, int high): This is the standard QuickSort function that
takes an array of integers arr, the starting index low, and the ending index high. It
sorts the numbers in ascending order.

Input Format
The first line of input consists of an integer N, representing the number of elements in the
array.

The second line consists of N array elements, separated by space.

Output Format
The output prints the sorted array, such that the negative elements come before the
positive elements, separated by space.

Constraints
N>0

Sample Input Sample Output

5
6 5 -7 4 -1

-7 -1 4 5 6

Sample Input Sample Output

8
1 4 5 9 -9 6 3 2

-9 1 2 3 4 5 6 9

Time Limit: - ms Memory Limit: - kb Code Size: - kb

Q9.
Problem Statement

As a diligent teacher, you have conducted a challenging exam for your students. Now that
the papers have been graded, you are eager to find out which students performed the
best and identify those who might need extra support.

To efficiently rank your students based on their marks, you decide to create a computer
program that sorts their exam marks in descending order using the Quick-Sort algorithm.

Input Format
The first line of input consists of an integer N, representing the number of students.

The second line consists of N floating-point numbers, representing the marks of the
students.

9/56
Output Format
The output prints the marks in descending order, placing the highest mark first and the
lowest mark last.

Constraints
N>0

Marks > 0.0

Sample Input Sample Output

5
78.3 54.7 96.4 32.7 53.1

96.4 78.3 54.7 53.1 32.7

Sample Input Sample Output

4
50.6 65.1 84.3 36.4

84.3 65.1 50.6 36.4

Time Limit: - ms Memory Limit: - kb Code Size: - kb

Q10.
Problem Statement

You are working as a program developer at a renowned sports academy. As part of the
academy's performance evaluation system, you are tasked with sorting the athletes
based on their heights in descending order.

Write a program that takes an array of athlete names and their corresponding heights as
input. Your program should use the Quick-Sort algorithm to sort the athletes' names in
descending order based on their heights.

Input Format
The first line of input consists of an integer N, representing the number of athletes.

The following N lines consist of the athlete's name and height, separated by space.

Output Format
The output prints the athletes' names sorted in descending order based on their heights.

Constraints
N == names.length == heights.length

N>0

10/56
names[i] consists of lower and upper case English letters.

All the values of heights are distinct.

Sample Input Sample Output

6
Mary 180
John 165
Emma 170
Joey 157
Tom 169
Cruise 175

Mary Cruise Emma Tom John Joey

Sample Input Sample Output

3
Alice 155
Bob 185
Bob 150

Bob Alice Bob

Time Limit: - ms Memory Limit: - kb Code Size: - kb

Q11.
Problem Statement

You are given a sequence of characters, and your task is to sort them in descending
order using the Quick-Sort algorithm.

Write a program that takes an integer N as input, representing the number of characters
in the sequence. Then, read N characters as input. Implement the quick sort algorithm to
sort the characters and print the sorted sequence.

Input Format
The first line of input consists of an integer N, representing the number of characters.

The second line consists of N space-separated characters.

Output Format
The output prints the sorted characters in descending order.

Constraints
N>0

Sample Input Sample Output

11/56
5
q w e r t

w t r q e

Sample Input Sample Output

5
m a n g o

o n m g a

Time Limit: - ms Memory Limit: - kb Code Size: - kb

Q12.
Problem Statement

You are working as a programmer at a sports academy, and the academy holds various
sports competitions regularly. As part of the academy's system, you need to sort the
scores of the participants in descending order using the Quick-Sort algorithm.

Write a program that takes the scores of N participants as input and uses the
QuickSortalgorithm to sort and display the scores in descending order.

Input Format
The first line of input consists of an integer N, representing the number of participants.

The second line consists of N space-separated integers, representing the scores of the
participants.

Output Format
The output prints the scores sorted in descending order.

Constraints
N>0

1 <= scores <= 100

Sample Input Sample Output

5
78 54 96 32 53

96 78 54 53 32

Sample Input Sample Output

4
53 65 84 36

12/56
84 65 53 36

Time Limit: - ms Memory Limit: - kb Code Size: - kb

Answer Key & Solution

Section 1 - Coding
Q1 Test Case Input Output

7
245 500 897 612 123 321 100

100 123 245 321 500 612 897

Weightage - 10 Input Output

50
611 452 305 267 559 633 181 23 557 221 394 570 587 112 657 376 638 274 444 238 552
327 467 483 20 251 206 24 501 34 414 435 408 143 566 71 551 189 292 478 406 530 12
297 266 131 239 674 10 298

10 12 20 23 24 34 71 112 131 143 181 189 206 221 238 239 251 266 267 274 292 297
298 305 327 376 394 406 408 414 435 444 452 467 478 483 501 530 551 552 557 559
566 570 587 611 633 638 657 674

Weightage - 25 Input Output

100
429 677 535 150 425 557 289 409 644 680 185 230 435 164 15 225 204 619 161 316 213
258 507 13 654 279 700 663 635 616 17 691 651 529 667 646 627 158 366 267 56 14
211 422 37 82 137 342 11 102 370 485 23 20 199 217 136 696 227 693 54 135 139 179
453 391 321 467 411 174 173 212 465 395 189 575 87 361 631 652 606 489 144 38 587
302 287 541 582 514 315 246 243 171 176 426 285 658 145 216

11 13 14 15 17 20 23 37 38 54 56 82 87 102 135 136 137 139 144 145 150 158 161 164
171 173 174 176 179 185 189 199 204 211 212 213 216 217 225 227 230 243 246 258
267 279 285 287 289 302 315 316 321 342 361 366 370 391 395 409 411 422 425 426
429 435 453 465 467 485 489 507 514 529 535 541 557 575 582 587 606 616 619 627
631 635 644 646 651 652 654 658 663 667 677 680 691 693 696 700

Weightage - 25 Input Output

30
477 194 219 206 222 223 249 695 200 383 552 352 57 423 28 585 126 525 101 422 466
455 656 35 586 37 329 689 524 84

28 35 37 57 84 101 126 194 200 206 219 222 223 249 329 352 383 422 423 455 466 477
524 525 552 585 586 656 689 695

Weightage - 15 Input Output

25
99 62 28 34 77 35 94 99 26 99 55 16 79 32 20 51 92 14 48 24 65 82 22 72 38

14 16 20 22 24 26 28 32 34 35 38 48 51 55 62 65 72 77 79 82 92 94 99 99 99

13/56
Weightage - 15 Input Output

10
99 55 16 79 32 20 51 92 14 48

14 16 20 32 48 51 55 79 92 99

Weightage - 10 Sample Input Sample Output

4
15 25 35 10

10 15 25 35

Sample Input Sample Output

3
120 60 80

60 80 120

Solution

14/56
#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) {
i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}

void quickSort(int arr[], int low, int high) {

if (low < high) {
int pi = partition(arr, low, high);

quickSort(arr, low, pi - 1);

quickSort(arr, pi + 1, high);
}
}

void printArray(int arr[], int size) {

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

int main() {
int n;
scanf("%d", &n);

int arr[n];
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}

quickSort(arr, 0, n - 1);

printArray(arr, n);

return 0;
}

15/56
#include <iostream>
using namespace std;

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)
{
i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}

void quickSort(int arr[], int low, int high) {

if (low < high)
{
int pi = partition(arr, low, high);

quickSort(arr, low, pi - 1);

quickSort(arr, pi + 1, high);
}
}

void printArray(int arr[], int size) {

for (int i = 0; i < size; i++)
cout << arr[i] << " ";
cout << endl;
}

int main()
{
int n;
cin >> n;

int arr[n];
for (int i = 0; i < n; i++) {
cin >> arr[i];
}

quickSort(arr, 0, n - 1);

printArray(arr, n);

16/56
 return 0;
}

Q2 Test Case Input Output

1
2022

2022

Weightage - 10 Input Output

2
2022 2021

2021 2022

Weightage - 10 Input Output

4
2016 2018 3018 2017

2016 2017 2018 3018

Weightage - 15 Input Output

5
1425 3657 8965 4123 1023

1023 1425 3657 4123 8965

Weightage - 15 Input Output

10
2000 2013 2014 2314 4152 3214 1320 2020 2023 1450

1320 1450 2000 2013 2014 2020 2023 2314 3214 4152

Weightage - 25 Input Output

15
2563 2145 2365 7458 8965 5423 2012 2023 2021 2452 3210 4523 3102 3103 1265

1265 2012 2021 2023 2145 2365 2452 2563 3102 3103 3210 4523 5423 7458 8965

Weightage - 25 Sample Input Sample Output

5
2014 2009 2000 1997 1865

1865 1997 2000 2009 2014

Sample Input Sample Output

3
1496 3015 2056

17/56
1496 2056 3015

Solution

#include <iostream>
#include <string>

using namespace std;

int partition(string arr[], int low, int high) {

string pivot = arr[high];
int i = low - 1;

for (int j = low; j < high; j++) {

if (arr[j] < pivot) {
i++;
swap(arr[i], arr[j]);
}
}

swap(arr[i + 1], arr[high]);

return i + 1;
}

void quickSort(string arr[], int low, int high) {

if (low < high) {
int pi = partition(arr, low, high);

quickSort(arr, low, pi - 1);

quickSort(arr, pi + 1, high);
}
}

void recursiveQuickSort(string arr[], int n) {

quickSort(arr, 0, n - 1);
}

int main() {
int n;
cin >> n;

string years[n];

for (int i = 0; i < n; i++) {

cin >> years[i];
}

recursiveQuickSort(years, n);

for (int i = 0; i < n; i++) {

cout << years[i] << " ";
}

return 0;
}

18/56
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int partition(char *arr[], int low, int high) {

char *pivot = arr[high];
int i = low - 1;

for (int j = low; j < high; j++) {

if (strcmp(arr[j], pivot) < 0) {
i++;
char *temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}

char *temp = arr[i + 1];

arr[i + 1] = arr[high];
arr[high] = temp;

return i + 1;
}

void quickSort(char *arr[], int low, int high) {

if (low < high) {
int pi = partition(arr, low, high);

quickSort(arr, low, pi - 1);

quickSort(arr, pi + 1, high);
}
}

void recursiveQuickSort(char *arr[], int low, int high) {

quickSort(arr, low, high);
}

int main() {
int n;
scanf("%d", &n);

char *years[n];

for (int i = 0; i < n; i++) {

years[i] = (char *)malloc(5 * sizeof(char));
scanf("%s", years[i]);
}

recursiveQuickSort(years, 0, n - 1);

for (int i = 0; i < n; i++) {

printf("%s ", years[i]);
free(years[i]);
}

19/56
 return 0;
}

Q3 Test Case Input Output

2
1.5 4.8

4.8 1.5

Weightage - 10 Input Output

3
4.2 1.7 3.5

4.2 3.5 1.7

Weightage - 10 Input Output

6
1.2 3.2 4.1 3.6 1.4 4.6

4.6 4.1 3.6 3.2 1.4 1.2

Weightage - 20 Input Output

7
2.3 5.0 1.4 3.4 3.5 3.6 4.5

5.0 4.5 3.6 3.5 3.4 2.3 1.4

Weightage - 20 Input Output

10
1.2 2.3 3.1 4.5 3.2 4.6 1.8 2.9 3.7 4.1

4.6 4.5 4.1 3.7 3.2 3.1 2.9 2.3 1.8 1.2

Weightage - 40 Sample Input Sample Output

3
3.6 4.4 2.9

4.4 3.6 2.9

Sample Input Sample Output

6
1.2 4.9 3.5 2.7 5.0 3.1

5.0 4.9 3.5 3.1 2.7 1.2

Solution

20/56
#include <iostream>
#include <iomanip>

// Function to swap two float values

void swap(float& a, float& b) {
float temp = a;
a = b;
b = temp;
}

// Partition function for Quick Sort (modified for descending order)

int partition(float arr[], int low, int high) {
float pivot = arr[high];
int i = low - 1;

for (int j = low; j <= high - 1; j++) {

if (arr[j] > pivot) { // Change comparison to sort in descending order
i++;
swap(arr[i], arr[j]);
}
}
swap(arr[i + 1], arr[high]);
return i + 1;
}

// Quick Sort function to sort GPAs in descending order

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

quickSort(arr, low, pi - 1);

quickSort(arr, pi + 1, high);
}
}

int main() {
int numStudents;

std::cin >> numStudents;

float* gpa = new float[numStudents];

for (int i = 0; i < numStudents; i++) {

std::cin >> gpa[i];
}

quickSort(gpa, 0, numStudents - 1);

for (int i = 0; i < numStudents; i++) {

std::cout << std::fixed << std::setprecision(1) << gpa[i] << " ";
}

delete[] gpa; // Deallocate the dynamically allocated array

return 0;
}

21/56
#include <stdio.h>

// Function to swap two float values

void swap(float* a, float* b) {
float temp = *a;
*a = *b;
*b = temp;
}

// Partition function for Quick Sort (modified for descending order)

int partition(float arr[], int low, int high) {
float pivot = arr[high];
int i = low - 1;

for (int j = low; j <= high - 1; j++) {

if (arr[j] > pivot) { // Change comparison to sort in descending order
i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return i + 1;
}

// Quick Sort function to sort GPAs in descending order

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

quickSort(arr, low, pi - 1);

quickSort(arr, pi + 1, high);
}
}

int main() {
int numStudents;

scanf("%d", &numStudents);

float gpa[numStudents];

for (int i = 0; i < numStudents; i++) {

scanf("%f", &gpa[i]);
}

quickSort(gpa, 0, numStudents - 1);

for (int i = 0; i < numStudents; i++) {

printf("%.1f ", gpa[i]);
}

return 0;
}

Q4 Test Case Input Output

22/56
6
Alice
Peter
Olivia
Lucas
Sophia
Daniel

Alice
Daniel
Lucas
Olivia
Peter
Sophia

Weightage - 15 Input Output

10
Liam
Sophia
Noah
Olivia
William
Ava
James
Isabella
Oliver
Emma

Ava
Emma
Isabella
James
Liam
Noah
Oliver
Olivia
Sophia
William

Weightage - 25 Input Output

8
Ethan
Amelia
Henry
Mia
James
Ava
Logan
Emily

23/56
Amelia
Ava
Emily
Ethan
Henry
James
Logan
Mia

Weightage - 25 Input Output

5
John
Emma
Adam
Sophia
Michael

Adam
Emma
John
Michael
Sophia

Weightage - 10 Input Output

7
Michael
Emily
Jacob
Ava
Daniel
Mia
Matthew

Ava
Daniel
Emily
Jacob
Matthew
Mia
Michael

Weightage - 15 Input Output

4
Sophia
Liam
Olivia
Noah

Liam
Noah
Olivia
Sophia

24/56
Weightage - 10 Sample Input Sample Output

5
Alice
Denver
Aadhil
Charlie
Zen

Aadhil
Alice
Charlie
Denver
Zen

Sample Input Sample Output

6
Chandler
Monica
Ross
Joey
Rachel
Phoebe

Chandler
Joey
Monica
Phoebe
Rachel
Ross

Solution

25/56
#include <iostream>
#include <string>

using namespace std;

int partition(string names[], int low, int high);

void quickSort(string names[], int low, int high) {

if (low < high) {
int pi = partition(names, low, high);
quickSort(names, low, pi - 1);
quickSort(names, pi + 1, high);
}
}

int partition(string names[], int low, int high) {

string pivot = names[high];
int i = low - 1;

for (int j = low; j < high; j++) {

if (names[j].compare(pivot) < 0) {
i++;
swap(names[i], names[j]);
}
}

swap(names[i + 1], names[high]);

return i + 1;
}

int main() {
int n;
cin >> n;

string names[n];

for (int i = 0; i < n; i++) {

cin >> names[i];
}

quickSort(names, 0, n - 1);

for (int i = 0; i < n; i++) {

cout << names[i] << endl;
}

return 0;
}

26/56
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int partition(char **names, int low, int high) {

char *pivot = names[high];
int i = low - 1;

for (int j = low; j < high; j++) {

if (strcmp(names[j], pivot) < 0) {
i++;
char *temp = names[i];
names[i] = names[j];
names[j] = temp;
}
}

char *temp = names[i + 1];

names[i + 1] = names[high];
names[high] = temp;
return i + 1;
}

void quickSort(char **names, int low, int high) {

if (low < high) {
int pi = partition(names, low, high);
quickSort(names, low, pi - 1);
quickSort(names, pi + 1, high);
}
}

int main() {
int n;
scanf("%d", &n);

char **names = (char **)malloc(sizeof(char *) * n);

for (int i = 0; i < n; i++) {

names[i] = (char *)malloc(sizeof(char) * 100);
scanf("%s", names[i]);
}

quickSort(names, 0, n - 1);

for (int i = 0; i < n; i++) {

printf("%s\n", names[i]);
}

for (int i = 0; i < n; i++) {

free(names[i]);
}
free(names);

return 0;
}

27/56
Q5 Test Case Input Output

5
1 4 5 9 8

1 4 8 5 9

Weightage - 20 Input Output

9
1 4 7 8 9 6 5 2 3

1 2 4 8 3 5 6 9 7

Weightage - 25 Input Output

15
78 96 54 12 36 94 10 15 16 34 28 92 67 47 31

16 10 12 34 36 96 28 67 15 54 78 92 31 47 94

Weightage - 25 Input Output

30
19 41 37 13 38 35 32 12 47 19 31 11 27 28 16 21 19 45 20 42 1 9 44 8 34 40 46 81
24 49

1 8 16 32 9 12 20 24 34 40 11 13 19 19 19 21 28 35 37 38 41 42 44 49 81 27 45 46
31 47

Weightage - 30 Sample Input Sample Output

9
0 1 2 3 4 5 6 7 8

0 1 2 4 8 3 5 6 7

Sample Input Sample Output

11
1024 512 256 128 64 32 16 8 4 2 1

1 2 4 8 16 32 64 128 256 512 1024

Solution

28/56
#include <stdio.h>
#include <stdlib.h>

int countOnes(int num) {

int count = 0;
while (num) {
count += num & 1;
num >>= 1;
}
return count;
}

void swap(int* a, int* b) {

int temp = *a;
*a = *b;
*b = temp;
}

int partition(int arr[], int low, int high) {

int pivot = countOnes(arr[high]);
int i = low - 1;
for (int j = low; j < high; j++) {
if (countOnes(arr[j]) < pivot || (countOnes(arr[j]) == pivot && arr[j] <
arr[high])) {
i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return i + 1;
}

void quickSort(int arr[], int low, int high) {

if (low < high) {
int pivot = partition(arr, low, high);
quickSort(arr, low, pivot - 1);
quickSort(arr, pivot + 1, high);
}
}

int main() {
int n;
scanf("%d", &n);

int *arr = (int*)malloc(n * sizeof(int));

if (arr == NULL) {
return 1;
}

for (int i = 0; i < n; i++) {

scanf("%d", &arr[i]);
}

quickSort(arr, 0, n - 1);

for (int i = 0; i < n; i++) {

29/56
 printf("%d ", arr[i]);
}

free(arr);
return 0;
}

30/56
#include <iostream>

using namespace std;

int countOnes(int num) {

int count = 0;
while (num) {
count += num & 1;
num >>= 1;
}
return count;
}

int partition(int arr[], int low, int high) {

int pivot = countOnes(arr[high]);
int i = low - 1;
for (int j = low; j < high; j++) {
if (countOnes(arr[j]) < pivot || (countOnes(arr[j]) == pivot && arr[j] <
arr[high])) {
i++;
swap(arr[i], arr[j]);
}
}
swap(arr[i + 1], arr[high]);
return i + 1;
}

void quickSort(int arr[], int low, int high) {

if (low < high) {
int pivot = partition(arr, low, high);
quickSort(arr, low, pivot - 1);
quickSort(arr, pivot + 1, high);
}
}

int main() {
int n;
cin >> n;

int *arr = new int[n];

for (int i = 0; i < n; i++) {
cin >> arr[i];
}

quickSort(arr, 0, n - 1);

for (int i = 0; i < n; i++) {

cout << arr[i] << " ";
}

delete[] arr;
return 0;
}

Q6 Test Case Input Output

31/56
5
z x c v b

b c v x z

Weightage - 10 Input Output

6
p l m n j i

i j l m n p

Weightage - 10 Input Output

7
t f c v g h j

c f g h j t v

Weightage - 20 Input Output

8
q m n w e r i k

e i k m n q r w

Weightage - 20 Input Output

26
m n b v c x z a s d f g h j k l p o i u y t r e w q

a b c d e f g h i j k l m n o p q r s t u v w x y z

Weightage - 40 Sample Input Sample Output

5
b n h u j

b h j n u

Sample Input Sample Output

6
w e r h j k

e h j k r w

Solution

32/56
#include <iostream>

using namespace std;

void printArray(char arr[], int size) {

for (int i = 0; i < size; i++) {
cout << arr[i] << " ";
}
}

int partition(char arr[], int low, int high) {

char pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] <= pivot) { // Change the comparison to sort in ascending
order
i++;
swap(arr[i], arr[j]);
}
}
swap(arr[i + 1], arr[high]);
return i + 1;
}

void quickSort(char arr[], int low, int high) {

if (low < high) {
int pivot = partition(arr, low, high);
quickSort(arr, low, pivot - 1);
quickSort(arr, pivot + 1, high);
}
}

int main() {
int n;
cin >> n;

char *characters = new char[n];

for (int i = 0; i < n; i++) {

cin >> characters[i];
}

quickSort(characters, 0, n - 1);
printArray(characters, n);

delete[] characters;
return 0;
}

33/56
#include <stdio.h>
#include <stdlib.h>

void printArray(char arr[], int size) {

for (int i = 0; i < size; i++) {
printf("%c ", arr[i]);
}
}

int partition(char arr[], int low, int high) {

char pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] <= pivot) {
i++;
// Swap elements arr[i] and arr[j]
char temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// Swap pivot element arr[i+1] and arr[high]
char temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}

void quickSort(char arr[], int low, int high) {

if (low < high) {
int pivot = partition(arr, low, high);
quickSort(arr, low, pivot - 1);
quickSort(arr, pivot + 1, high);
}
}

int main() {
int n;
scanf("%d", &n);

char *characters = (char *)malloc(n * sizeof(char));

if (characters == NULL) {
fprintf(stderr, "Memory allocation failed.\n");
return 1;
}

for (int i = 0; i < n; i++) {

scanf(" %c", &characters[i]); // Note the space before %c to skip
whitespace
}

quickSort(characters, 0, n - 1);
printArray(characters, n);

free(characters);

34/56
 return 0;
}

Q7 Test Case Input Output

5
Apple Carrot Banana Kiwi Mango

Mango Kiwi Carrot Banana Apple

Weightage - 10 Input Output

5
Stefan Damon Elena Bonnie Enzo

Stefan Enzo Elena Damon Bonnie

Weightage - 10 Input Output

8
Ant Bird Snake Camel Kangaroo Dog Elephant Lion

Snake Lion Kangaroo Elephant Dog Camel Bird Ant

Weightage - 15 Input Output

8
Cheetah Hyena Giraffe Bull Cow Buffalo Cat Dog

Hyena Giraffe Dog Cow Cheetah Cat Bull Buffalo

Weightage - 15 Input Output

10
Interstellar Inception Manifest Flight828 Consciousness Galaxy Spectacles
Escalation DSA CPP

Spectacles Manifest Interstellar Inception Galaxy Flight828 Escalation DSA

Consciousness CPP

Weightage - 25 Input Output

10
Compilation Output Maximum Allowed Memory Limit Generate Input Via Code

Via Output Memory Maximum Limit Input Generate Compilation Code Allowed

Weightage - 25 Sample Input Sample Output

2
Cap Cat

Cat Cap

Sample Input Sample Output

35/56
5
Chair Door Mouse Keyboard Table

Table Mouse Keyboard Door Chair

Solution

36/56
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void swap(char **a, char **b) {

char *temp = *a;
*a = *b;
*b = temp;
}

int partition(char *arr[], int low, int high) {

char *pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (strcmp(arr[j], pivot) >= 0) { // Compare strings using strcmp for
descending order
i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return i + 1;
}

void quickSort(char *arr[], int low, int high) {

if (low < high) {
int pivot = partition(arr, low, high);
quickSort(arr, low, pivot - 1);
quickSort(arr, pivot + 1, high);
}
}

int main() {
int n;
scanf("%d", &n);

char **words = (char **)malloc(n * sizeof(char *));

for (int i = 0; i < n; i++) {
words[i] = (char *)malloc(100 * sizeof(char)); // Assuming max word length
is 100
scanf("%s", words[i]);
}

quickSort(words, 0, n - 1);

for (int i = 0; i < n; i++) {

printf("%s ", words[i]);
free(words[i]); // Free allocated memory for each word
}

free(words); // Free the array of pointers

return 0;
}

37/56
#include <iostream>
#include <string>

using namespace std;

int partition(string arr[], int low, int high) {

string pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] >= pivot) { // Change the comparison condition to sort in
descending order
i++;
swap(arr[i], arr[j]);
}
}
swap(arr[i + 1], arr[high]);
return i + 1;
}

void quickSort(string arr[], int low, int high) {

if (low < high) {
int pivot = partition(arr, low, high);
quickSort(arr, low, pivot - 1);
quickSort(arr, pivot + 1, high);
}
}

int main() {
int n;
cin >> n;

string *words = new string[n];

for (int i = 0; i < n; i++) {
cin >> words[i];
}

quickSort(words, 0, n - 1);

for (int i = 0; i < n; i++) {

cout << words[i] << " ";
}

delete[] words;
return 0;
}

Q8 Test Case Input Output

6
1 4 5 -9 6 -2

-9 -2 1 4 5 6

Weightage - 20 Input Output

38/56
10
1 -9 -6 -3 5 84 26 -98 14 -37

-98 -37 -9 -6 -3 1 5 14 26 84

Weightage - 25 Input Output

15
98 74 56 32 14 25 36 96 87 -9 -6 -3 -2 -8 -7

-9 -8 -7 -6 -3 -2 14 25 32 36 56 74 87 96 98

Weightage - 25 Input Output

25
98 74 56 32 14 25 37 95 99 96 -8 -9 -6 -7 -4 -1 -2 -3 -6 -5 23 36 97 85 75

-9 -8 -7 -6 -6 -5 -4 -3 -2 -1 14 23 25 32 36 37 56 74 75 85 95 96 97 98 99

Weightage - 30 Sample Input Sample Output

5
6 5 -7 4 -1

-7 -1 4 5 6

Sample Input Sample Output

8
1 4 5 9 -9 6 3 2

-9 1 2 3 4 5 6 9

Solution

39/56
#include <stdio.h>
#include <stdlib.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; j++) {
if (arr[j] < pivot) {
i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return i + 1;
}

void quickSort(int arr[], int low, int high) {

if (low < high) {
int pivot = partition(arr, low, high);
quickSort(arr, low, pivot - 1);
quickSort(arr, pivot + 1, high);
}
}

void rearrangeNegativesBeforePositives(int arr[], int n) {

int i = -1;
for (int j = 0; j < n; j++) {
if (arr[j] < 0) {
i++;
swap(&arr[i], &arr[j]);
}
}
}

int main() {
int n;
scanf("%d", &n);

int *arr = (int *)malloc(n * sizeof(int));

for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}

rearrangeNegativesBeforePositives(arr, n);
quickSort(arr, 0, n - 1);

for (int i = 0; i < n; i++) {

printf("%d ", arr[i]);
}

40/56
 free(arr);
return 0;
}

41/56
#include <iostream>

using namespace std;

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; j++) {
if (arr[j] < pivot) {
i++;
swap(arr[i], arr[j]);
}
}
swap(arr[i + 1], arr[high]);
return i + 1;
}

void quickSort(int arr[], int low, int high) {

if (low < high) {
int pivot = partition(arr, low, high);
quickSort(arr, low, pivot - 1);
quickSort(arr, pivot + 1, high);
}
}

void rearrangeNegativesBeforePositives(int arr[], int n) {

int i = -1;
for (int j = 0; j < n; j++) {
if (arr[j] < 0) {
i++;
swap(arr[i], arr[j]);
}
}
}

int main() {
int n;
cin >> n;

int* arr = new int[n];

for (int i = 0; i < n; i++) {
cin >> arr[i];
}

rearrangeNegativesBeforePositives(arr, n);
quickSort(arr, 0, n - 1);

for (int i = 0; i < n; i++) {

cout << arr[i] << " ";
}

42/56
 delete[] arr;
return 0;
}

Q9 Test Case Input Output

4
9.4 7.6 8.1 5.7

9.4 8.1 7.6 5.7

Weightage - 10 Input Output

5
7.3 8.1 9.4 6.7 1.5

9.4 8.1 7.3 6.7 1.5

Weightage - 10 Input Output

8
4.7 7.3 2.7 9.9 11.5 3.6 1.2 6.1

11.5 9.9 7.3 6.1 4.7 3.6 2.7 1.2

Weightage - 15 Input Output

7
7.4 3.4 202.7 1.9 4.3 5.4 9.5

202.7 9.5 7.4 5.4 4.3 3.4 1.9

Weightage - 15 Input Output

9
1.9 7.2 6.3 4.1 5.3 8.5 9.1 22.9 15.4

22.9 15.4 9.1 8.5 7.2 6.3 5.3 4.1 1.9

Weightage - 25 Input Output

10
78.2 59.5 45.4 12.3 23.6 26.4 54.4 78.9 95.4 41.4

95.4 78.9 78.2 59.5 54.4 45.4 41.4 26.4 23.6 12.3

Weightage - 25 Sample Input Sample Output

5
78.3 54.7 96.4 32.7 53.1

96.4 78.3 54.7 53.1 32.7

Sample Input Sample Output

43/56
4
50.6 65.1 84.3 36.4

84.3 65.1 50.6 36.4

Solution

#include <iostream>
#include <iomanip> // Required for std::fixed and std::setprecision

using namespace std;

void printArray(float arr[], int size) {

for (int i = 0; i < size; i++) {
cout << fixed << setprecision(1) << arr[i] << " ";
}
}

int partition(float arr[], int low, int high) {

float pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] >= pivot) {
i++;
swap(arr[i], arr[j]);
}
}
swap(arr[i + 1], arr[high]);
return i + 1;
}

void quickSort(float arr[], int low, int high) {

if (low < high) {
int pivot = partition(arr, low, high);
quickSort(arr, low, pivot - 1);
quickSort(arr, pivot + 1, high);
}
}

int main() {
int n;
cin >> n;

float* marks = new float[n];

for (int i = 0; i < n; i++) {
cin >> marks[i];
}

quickSort(marks, 0, n - 1);

printArray(marks, n);

delete[] marks;
return 0;
}

44/56
#include <stdio.h>
#include <stdlib.h>

void swap(float *a, float *b) {

float temp = *a;
*a = *b;
*b = temp;
}

int partition(float arr[], int low, int high) {

float pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] >= pivot) {
i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return i + 1;
}

void quickSort(float arr[], int low, int high) {

if (low < high) {
int pivot = partition(arr, low, high);
quickSort(arr, low, pivot - 1);
quickSort(arr, pivot + 1, high);
}
}

void printArray(float arr[], int size) {

for (int i = 0; i < size; i++) {
printf("%0.1f ", arr[i]);
}
}

int main() {
int n;
scanf("%d", &n);

float *marks = (float *)malloc(n * sizeof(float));

for (int i = 0; i < n; i++) {
scanf("%f", &marks[i]);
}

quickSort(marks, 0, n - 1);

printArray(marks, n);

free(marks);
return 0;
}

Q10 Test Case Input Output

45/56
4
Keerthi 178
Charu 185
Preethi 190
Angel 175

Preethi Charu Keerthi Angel

Weightage - 20 Input Output

5
Alice 178
Bob 198
Charles 165
David 197
Elena 156

Bob David Alice Charles Elena

Weightage - 25 Input Output

6
Stefan 198
Damon 178
Elena 187
Bonnie 184
Alice 165
John 176

Stefan Elena Bonnie Damon John Alice

Weightage - 25 Input Output

10
Milton 170
Sandeep 176
Dharun 180
Udhesh 190
Hari 177
Harry 168
Sharma 188
Patel 189
Dhoni 199

Dhoni Udhesh Patel Sharma Dharun Hari Sandeep Milton Harry

Weightage - 30 Sample Input Sample Output

6
Mary 180
John 165
Emma 170
Joey 157
Tom 169
Cruise 175

46/56
Mary Cruise Emma Tom John Joey

Sample Input Sample Output

3
Alice 155
Bob 185
Bob 150

Bob Alice Bob

Solution

47/56
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void swapStrings(char **a, char **b) {

char *temp = *a;
*a = *b;
*b = temp;
}

void swapInts(int *a, int *b) {

int temp = *a;
*a = *b;
*b = temp;
}

int partition(char *names[], int heights[], int low, int high) {

int pivot = heights[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (heights[j] >= pivot) {
i++;
swapStrings(&names[i], &names[j]);
swapInts(&heights[i], &heights[j]);
}
}
swapStrings(&names[i + 1], &names[high]);
swapInts(&heights[i + 1], &heights[high]);
return i + 1;
}

void quickSort(char *names[], int heights[], int low, int high) {

if (low < high) {
int pivot = partition(names, heights, low, high);
quickSort(names, heights, low, pivot - 1);
quickSort(names, heights, pivot + 1, high);
}
}

int main() {
int n;
scanf("%d", &n);

char **names = (char **)malloc(n * sizeof(char *));

int *heights = (int *)malloc(n * sizeof(int));

for (int i = 0; i < n; i++) {

names[i] = (char *)malloc(100 * sizeof(char)); // Assuming max name length
is 100
scanf("%s %d", names[i], &heights[i]);
}

quickSort(names, heights, 0, n - 1);

for (int i = 0; i < n; i++) {

printf("%s ", names[i]);

48/56
 free(names[i]);
}

free(names);
free(heights);
return 0;
}

49/56
#include <iostream>
#include <string>

using namespace std;

int partition(string names[], int heights[], int low, int high) {

int pivot = heights[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (heights[j] >= pivot) { // Sort in descending order based on heights
i++;
swap(names[i], names[j]);
swap(heights[i], heights[j]);
}
}
swap(names[i + 1], names[high]);
swap(heights[i + 1], heights[high]);
return i + 1;
}

void quickSort(string names[], int heights[], int low, int high) {

if (low < high) {
int pivot = partition(names, heights, low, high);
quickSort(names, heights, low, pivot - 1);
quickSort(names, heights, pivot + 1, high);
}
}

int main() {
int n;
cin >> n;

string *names = new string[n];

int *heights = new int[n];

for (int i = 0; i < n; i++) {

cin >> names[i] >> heights[i];
}

quickSort(names, heights, 0, n - 1);

for (int i = 0; i < n; i++) {

cout << names[i] << " ";
}

delete[] names;
delete[] heights;
return 0;
}

Q11 Test Case Input Output

6
a s d f g h

s h g f d a

50/56
Weightage - 20 Input Output

7
q w e r t y u

y w u t r q e

Weightage - 25 Input Output

8
l k j h g f d s

s l k j h g f d

Weightage - 25 Input Output

26
q w e r t y u i o p l k j h g f d s a z x c v b n m

z y x w v u t s r q p o n m l k j i h g f e d c b a

Weightage - 30 Sample Input Sample Output

5
q w e r t

w t r q e

Sample Input Sample Output

5
m a n g o

o n m g a

Solution

51/56
#include <stdio.h>
#include <stdlib.h>

void printArray(char arr[], int size) {

for (int i = 0; i < size; i++) {
printf("%c ", arr[i]);
}
}

int partition(char arr[], int low, int high) {

char pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] >= pivot) {
i++;
char temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
char temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}

void quickSort(char arr[], int low, int high) {

if (low < high) {
int pivot = partition(arr, low, high);
quickSort(arr, low, pivot - 1);
quickSort(arr, pivot + 1, high);
}
}

int main() {
int n;
scanf("%d", &n);

char *characters = (char *)malloc(n * sizeof(char));

for (int i = 0; i < n; i++) {

scanf(" %c", &characters[i]);
}

quickSort(characters, 0, n - 1);
printArray(characters, n);

free(characters);
return 0;
}

52/56
#include <iostream>

using namespace std;

void printArray(char arr[], int size) {

for (int i = 0; i < size; i++) {
cout << arr[i] << " ";
}
}

int partition(char arr[], int low, int high) {

char pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] >= pivot) {
i++;
swap(arr[i], arr[j]);
}
}
swap(arr[i + 1], arr[high]);
return i + 1;
}

void quickSort(char arr[], int low, int high) {

if (low < high) {
int pivot = partition(arr, low, high);
quickSort(arr, low, pivot - 1);
quickSort(arr, pivot + 1, high);
}
}

int main() {
int n;
cin >> n;

char *characters = new char[n];

for (int i = 0; i < n; i++) {

cin >> characters[i];
}

quickSort(characters, 0, n - 1);
printArray(characters, n);

delete[] characters;
return 0;
}

Q12 Test Case Input Output

4
9 7 8 5

9 8 7 5

Weightage - 10 Input Output

53/56
5
7 8 9 6 1

9 8 7 6 1

Weightage - 10 Input Output

8
4 7 2 9 11 3 1 6

11 9 7 6 4 3 2 1

Weightage - 15 Input Output

7
7 3 2 1 4 5 9

9 7 5 4 3 2 1

Weightage - 15 Input Output

9
1 7 6 4 5 8 9 22 15

22 15 9 8 7 6 5 4 1

Weightage - 25 Input Output

10
78 59 45 12 23 26 54 79 95 41

95 79 78 59 54 45 41 26 23 12

Weightage - 25 Sample Input Sample Output

5
78 54 96 32 53

96 78 54 53 32

Sample Input Sample Output

4
53 65 84 36

84 65 53 36

Solution

54/56
#include <iostream>

using namespace std;

void printArray(int arr[], int size) {

for (int i = 0; i < size; i++) {
cout << arr[i] << " ";
}
}

int partition(int arr[], int low, int high) {

int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] >= pivot) {
i++;
swap(arr[i], arr[j]);
}
}
swap(arr[i + 1], arr[high]);
return i + 1;
}

void quickSort(int arr[], int low, int high) {

if (low < high) {
int pivot = partition(arr, low, high);
quickSort(arr, low, pivot - 1);
quickSort(arr, pivot + 1, high);
}
}

int main() {
int n;
cin >> n;

int *scores = new int[n];

for (int i = 0; i < n; i++) {
cin >> scores[i];
}

quickSort(scores, 0, n - 1);
printArray(scores, n);

delete[] scores;
return 0;
}

55/56
#include <stdio.h>
#include <stdlib.h>

void printArray(int arr[], int size) {

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

int partition(int arr[], int low, int high) {

int pivot = arr[high];
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;
}
}
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}

void quickSort(int arr[], int low, int high) {

if (low < high) {
int pivot = partition(arr, low, high);
quickSort(arr, low, pivot - 1);
quickSort(arr, pivot + 1, high);
}
}

int main() {
int n;
scanf("%d", &n);

int *scores = (int *)malloc(n * sizeof(int));

for (int i = 0; i < n; i++) {
scanf("%d", &scores[i]);
}

quickSort(scores, 0, n - 1);
printArray(scores, n);

free(scores);
return 0;
}

56/56