Lecture: Quick Sort

Quick Sort is a divide and conquer sorting algorithm.

It works by selecting a pivot element, partitioning the array into two sub-arrays:

 Left sub-array: Elements less than or equal to pivot

 Right sub-array: Elements greater than pivot

Then, it recursively sorts the sub-arrays.

Algorithm:

1. QuickSort(A, lb, ub)

if (lb < ub)

{
loc = Partition(A, lb, ub);
QuickSort(A, lb, loc - 1);
QuickSort(A, loc + 1, ub);
}

2. Partition(A, lb, ub)

pivot = A[lb];
start = lb;
end = ub;

while (start < end)

{
while (A[start] <= pivot)
start++;

while (A[end] > pivot)

end--;

if (start < end)

swap(A[start], A[end]);
}

swap(A[lb], A[end]);
return end;

Explanation of Steps:
 1. Select Pivot:
The first element of the array is chosen as the pivot (here, pivot = A[lb]).
2. Partitioning Process:
o Use two pointers: start (beginning) and end (end of the array).
o Move start forward until an element greater than pivot is found.
o Move end backward until an element smaller than or equal to pivot is
found.
o Swap A[start] and A[end] if start < end.
3. Final Swap:
After the loop, swap pivot (A[lb]) with A[end].
This places the pivot in its correct sorted position.
4. Recursive Calls:
Apply the same logic to the left and right sub-arrays.

Example:

Input Array:

7 6 10 5 9 2 1 15 7

Step 1:

 Pivot = 7
 After partitioning, the pivot 7 will be placed at its correct position in the
array.

Step 2:

 Apply Quick Sort recursively to left part [6, 5, 2, 1]

 Apply Quick Sort recursively to right part [10, 9, 15, 7]

C Program:

#include <stdio.h>

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

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

int partition(int A[], int lb, int ub) {

int pivot = A[lb];
 int start = lb;
int end = ub;

while (start < end) {

while (A[start] <= pivot)
start++;
while (A[end] > pivot)
end--;
if (start < end)
swap(&A[start], &A[end]);
}
swap(&A[lb], &A[end]);
return end;
}

void quickSort(int A[], int lb, int ub) {

if (lb < ub) {
int loc = partition(A, lb, ub);
quickSort(A, lb, loc - 1);
quickSort(A, loc + 1, ub);
}
}

int main() {
int A[] = {7, 6, 10, 5, 9, 2, 1, 15, 7};
int n = sizeof(A)/sizeof(A[0]);

quickSort(A, 0, n - 1);

printf("Sorted array: ");

for (int i = 0; i < n; i++)
printf("%d ", A[i]);
return 0;
}

Output:

Sorted array: 1 2 5 6 7 7 9 10 15

Time Complexity:
 Case Complexity
Best Case O(n log n)
Average Case O(n log n)
Worst Case O(n²)

Space Complexity:

O(log n) — due to recursive stack.

Result:

The Quick Sort algorithm was successfully implemented and tested.

It efficiently sorts elements using the Divide and Conquer approach.

Would you like me to make this into a formatted PDF handout for DAA lab
submission (with proper title, margins, and formatting)?