[go: up one dir, main page]
Scribd
Upload
7 views4 pages

DAA Lab Assignment 2

The document presents a lab assignment by Manas Patil on the analysis of the Quick Sort algorithm. It includes pseudocode, Java code implementation, and a table showing execution times for different input sizes. Additionally, it mentions the analysis of time complexity but does not provide complete details in the provided text.

Uploaded by

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

DAA Lab Assignment 2

The document presents a lab assignment by Manas Patil on the analysis of the Quick Sort algorithm. It includes pseudocode, Java code implementation, and a table showing execution times for different input sizes. Additionally, it mentions the analysis of time complexity but does not provide complete details in the provided text.

Uploaded by

manasdp271
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 4

NAME: Manas Patil

ROLL NO: 10
CLASS: IT-C
PRN NO: 12211772
BATCH: 2

LAB ASSIGNMENT 2

AIM: Analysis of Quick Sort Algorithm.

STEP1: Pseudocode
QUICKSORT(arr, si, ei):
IF si >= ei:
RETURN // Base case: Stop when there's one or no element

pidx = PARTITION(arr, si, ei) // Get partition index

QUICKSORT(arr, si, pidx - 1) // Sort left part


QUICKSORT(arr, pidx + 1, ei) // Sort right part

PARTITION(arr, si, ei):


pivot = arr[ei] // Choose last element as pivot
i = si - 1 // Pointer for smaller elements

FOR j = si TO ei - 1:
IF arr[j] <= pivot:
i = i + 1 // Move pointer
SWAP(arr[i], arr[j]) // Swap elements
i++
SWAP(arr[i ], arr[ei]) // Place pivot in correct position
RETURN i // Return pivot index

STEP 2: Code
import java.util.Arrays;
public class Main {
// QuickSort function
public static void quicksort(int arr[], int si, int ei) {
if (si >= ei) return; // Base case

// Partition the array and get the pivot index


int pidx = partition(arr, si, ei);

// Recursively sort left and right parts


quicksort(arr, si, pidx - 1); // Left part
quicksort(arr, pidx + 1, ei); // Right part
}
// Partition function
public static int partition(int arr[], int si, int ei) {
int pivot = arr[ei]; // Choose the last element as pivot
int i = si - 1; // Pointer for elements smaller than pivot

for (int j = si; j < ei; j++) { // Iterate through the array
if (arr[j] <= pivot) { // If element is smaller or equal to pivot
i++; // Move the pointer forward
// Swap arr[i] and arr[j]
int temp = arr[j];
arr[j] = arr[i];
arr[i] = temp;
}
}
i++;
// Swap pivot to correct position
int temp = arr[ei];
arr[ei] = arr[i];
arr[i] = temp;

return i ; // Return the pivot index


}

// Main method to test QuickSort


public static void main(String[] args) {
int arr[] = {10, 7, 8, 9, 1, 5};
int n = arr.length;

quicksort(arr, 0, n - 1); // Call QuickSort

// Print sorted array


System.out.println("Sorted array:");
for (int num : arr) {
System.out.print(num + " ");
}
}
}
STEP 3: Equations for number of arithmetic operations
needed in Quick sort.

Input size (n) Execution time (ms)


40k 10
50k 13
60k 15

70k 20
80k 23

STEP 4: ANALYSIS OF TIME COMPLEXITY (using


recurrence relation substitution, Master theorem or
recurrence tree)
 f

Output :

You might also like