[go: up one dir, main page]
Scribd
Upload
20 views5 pages

Our DSA Lab 12

The document outlines a lab assignment for developing a Quick Sort algorithm as part of a Data Structures and Algorithms course. It includes an introduction to the Quick Sort method, the steps for the algorithm, pseudocode for both the partition function and the Quick Sort process, and a complete C++ code implementation. The assignment aims to help students understand and apply the Quick Sort algorithm effectively.

Uploaded by

talhahaneef4037
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
20 views5 pages

Our DSA Lab 12

The document outlines a lab assignment for developing a Quick Sort algorithm as part of a Data Structures and Algorithms course. It includes an introduction to the Quick Sort method, the steps for the algorithm, pseudocode for both the partition function and the Quick Sort process, and a complete C++ code implementation. The assignment aims to help students understand and apply the Quick Sort algorithm effectively.

Uploaded by

talhahaneef4037
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/ 5

The Islamia University of Bahawalpur

Faculty of Engineering

BS Cyber Security and Digital Forensics 3rd semester


Lab # 12 Quick Start Algorithm
Course: Data Structures and Algorithms lab Date:
Submitted by: Sidra &Aqsa Ghaffar Roll No. 4050 &4065

Objective
To develop a code for Quick-sort Algorithm.

Introduction

Quick sort is a highly efficient sorting algorithm and is based on partitioning of array of data into
smaller arrays. A large array is partitioned into two arrays one of which holds values smaller than the
specified value, say pivot, based on which the partition is made and another array holds values greater
than the pivot value. Quick sort partitions an array and then calls itself recursively twice to sort the two
resulting subarrays. This algorithm is quite efficient for large-sized data sets as its average and worst
case complexity are of Ο(n2), where n is the number of items.

Quick Sort Pivot Algorithm:

Based on our understanding of partitioning in quick sort, we will now try to write an algorithm
for it, which is as follows.

Step 1 − Choose the highest index value has pivot

Step 2 − Take two variables to point left and right of the list excluding pivot

Step 3 − left points to the low index

Step 4 − right points to the high

Step 5 − while value at left is less than pivot move right

Step 6 − while value at right is greater than pivot move left

Step 7 − if both step 5 and step 6 does not match swap left and right

Step 8 − if left ≥ right, the point where they met is new pivot
Quick Sort Pivot Pseudocode:

The pseudocode for the above algorithm can be derived as :

function partitionFunc(left, right, pivot)

leftPointer = left - 1

rightPointer = right

while True do

while A[++leftPointer] < pivot do

//do-nothing

end while

while rightPointer > 0 && A[--rightPointer] > pivot do

//do-nothing

end while

if leftPointer >= rightPointer

break

else

swap leftPointer,rightPointer

end if

end while

swap leftPointer,right

return leftPointer

end function

Quick Sort Algorithm:


Using pivot algorithm recursively, we end up with smaller possible partitions. Each partition is
then processed for quick sort. We define recursive algorithm for quicksort as follows:

Step 1 − Make the right-most index value pivot

Step 2 − partition the array using pivot value

Step 3 − quicksort left partition recursively

Step 4 − quicksort right partition recursively

Quick Sort Pseudocode:

To get more into it, let’s see the pseudocode for quick sort algorithm:

procedure quickSort(left, right)

if right-left <= 0

return

else

pivot = A[right]

partition = partitionFunc(left, right, pivot)

quickSort(left,partition-1)

quickSort(partition+1,right)

end if
end procedure

Tasks:

1. Develop the codes using the provided quick-sort algorithms and print the outputs.

Code:

#include <iostream>
using namespace std;
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 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;
cout << "Enter the number of elements: ";
cin >> n;

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

cout << "Original Array: ";


printArray(arr, n);

quickSort(arr, 0, n - 1);

cout << "Sorted Array: ";


printArray(arr, n);

return 0;
}

Output:

You might also like