Scribd
Upload
2 views2 pages

Shivom 5

The document outlines an experiment in a Computer Science course aimed at understanding the Quick Sort algorithm. It includes the code for implementing Quick Sort in C++, instructions for sorting a set of elements, and observations on its performance across different input sizes. The learning outcomes highlight the partitioning process and the algorithm's time complexity in various cases.

Uploaded by

Lakshay Sanwal
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
2 views2 pages

Shivom 5

The document outlines an experiment in a Computer Science course aimed at understanding the Quick Sort algorithm. It includes the code for implementing Quick Sort in C++, instructions for sorting a set of elements, and observations on its performance across different input sizes. The learning outcomes highlight the partitioning process and the algorithm's time complexity in various cases.

Uploaded by

Lakshay Sanwal
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

DEPARTMENT OF

COMPUTER SCIENCE & ENGINEERING

Experiment No: 2.1

Student Name: Shivom Singh UID: 23BCS12110


Branch: BE-CSE Section/Group: 619-B
Semester: 5th Date of Performance: 3-9-25
Subject Name: DAA

1. Aim: Sort a given set of elements using the Quick sort method and determine the time required to sort the
elements. Repeat the experiment for different values of n, the number of elements in the list to be sorted.
The elements can be read from a file or can be generated using the random number generator.

2. Objective: To understand quick sort.

3. Code for Quick Sort:

#include <iostream>
using namespace std;

int partition(int A[], int p, int r) {


int x = A[r]; // pivot
int i = p - 1;

for (int j = p; j <= r - 1; j++) {


if (A[j] <= x) {
i = i + 1;
swap(A[i], A[j]);
}
}
swap(A[i + 1], A[r]);
return i + 1;
}

void quicksort(int A[], int p, int r) {


if (p < r) {
int q = partition(A, p, r);
quicksort(A, p, q - 1);
quicksort(A, q + 1, r);
}
}

int main() {
int n;
cout << "Enter number of elements: ";
cin >> n;
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING

int A[n];
cout << "Enter " << n << " elements:\n";
for (int i = 0; i < n; i++) {
cin >> A[i];
}

quicksort(A, 0, n - 1);

cout << "Sorted elements:\n";


for (int i = 0; i < n; i++) {
cout << A[i] << " ";
}
cout << endl;

return 0;
}

4. Observations/Outcome for Quick Sort:

5. Learning outcomes (What I have learnt):

1. You learn how the partition step works:


• Select a pivot.
• Rearrange elements so that smaller values go left and larger go right.
2. By running the program on different input sizes, you experience how:
• Best/Average case → O(nlog⁡n)O(n \log n)O(nlogn)
• Worst case → O(n2)O(n^2)O(n2)

3. Implementation of a textbook algorithm in C++.

You might also like