DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING
Experiment No:2.1
Student Name:Aditya UID:23BET10090
Branch:BE IT Section/Group 902A
Semester:5 Date of Performance:11sept
Subject DAA
Code:23ITH301
Aim: Implement Quick Sort and measure the time taken to sort arrays of different sizes using
input from a file or random numbers.
Description: Quick Sort is a divide-and-conquer sorting algorithm. It works by selecting a pivot
element, partitioning the array into two sub-arrays (elements smaller than pivot and elements
greater than pivot), and then recursively sorting these sub-arrays.
Algorithm:
1. Generate or read n elements from a file.
2. Store elements in an array.
3. Record start time and apply Quick Sort.
4. Record end time and calculate time taken.
5. Display sorted array, total elements, and time.
6. Repeat for different values of n.
Code:
A code for random access
import [Link].*;
public class QuickSortRandom {
private static int partition(int[] arr, int low,
int high) {
int pivot = arr[high];
int i = (low - 1);
for (int j = low; j < high; j++) {
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING
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;
}
private static 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);
}
}
public static void main(String[] args) {
Random rand = new Random();
int[] sizes = {1000, 5000, 10000,
50000};
for (int n : sizes) {
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = [Link](100000);
}
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING
long start = [Link]();
quickSort(arr, 0, [Link] - 1);
long end = [Link]();
[Link]("n = " + n + "Time
taken: " + (end - start) + " nanoseconds");
}
}
}
Code for file sort
import [Link].*;
import [Link].*;
public class QuickSortFile {
private static 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;
}
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING
private static 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);
}
}
private static void generateFile(String
filename, int n) throws IOException {
Random rand = new Random();
try (PrintWriter pw = new
PrintWriter(new FileWriter(filename))) {
for (int i = 0; i < n; i++) {
[Link]([Link](100000) + "
");
}
}
}
public static void main(String[] args) {
try {
String filename =
"C:\\Users\\singh\\IdeaProjects\\untitled6\\inp
[Link]";
generateFile(filename, 10000);
Scanner sc = new Scanner(new
File(filename));
List<Integer> list = new
ArrayList<>();
while ([Link]()) {
[Link]([Link]());
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING
}
[Link]();
int[] arr = [Link]().mapToInt(i ->
i).toArray();
long start = [Link]();
quickSort(arr, 0, [Link] - 1);
long end = [Link]();
[Link]("First 50 sorted
elements: " +
[Link]([Link](arr, 50)));
[Link]("Total elements: "
+ [Link]);
[Link]("Time taken: " +
(end - start) + " nanoseconds");
} catch (Exception e) {
[Link]("Error: " +
[Link]());
}
}
}
Outcome
For random access
For file sort
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING
Learning outcomes (What I have learnt):
1. Understand how to implement and
apply the Quick Sort algorithm for
efficient sorting.
2. Learn to generate, read, and process
data from files in Java.
3. Measure and analyze the time
complexity of sorting for large
datasets.