Scribd
Upload
2 views2 pages

Algo. Lab#8 Quick Sort Algorithm

The document explains the Quick Sort algorithm, which is a sorting method based on the Divide and Conquer principle that uses a pivot to partition an array. It provides pseudocode and Java code for implementing the Quick Sort algorithm, detailing the steps for choosing a pivot and rearranging elements. The worst-case time complexity of Quick Sort is O(n^2).

Uploaded by

solimano699
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

Algo. Lab#8 Quick Sort Algorithm

The document explains the Quick Sort algorithm, which is a sorting method based on the Divide and Conquer principle that uses a pivot to partition an array. It provides pseudocode and Java code for implementing the Quick Sort algorithm, detailing the steps for choosing a pivot and rearranging elements. The worst-case time complexity of Quick Sort is O(n^2).

Uploaded by

solimano699
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

Level 2 | Algorithms | Lab 8

Quick Sort Algorithm


Quick sort is a sorting algorithm based on the Divide and Conquer algorithm that picks an
element as a pivot and partitions the given array around the picked pivot by placing the pivot
in its correct position in the sorted array.

Quick Sort Example

Pseudocode for Quick Sort Algorithm


Step 1 − Choose the highest index value as 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 Code:


package quicksort;
public class QuickSort {
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int pivot = partition(arr, low, high);
quickSort(arr, low, pivot - 1);//Sort left half
quickSort(arr, pivot + 1, high);// Sort right half
}
}

1|Page
Modern Academy - Eng. Noha Ali
Level 2 | Algorithms | Lab 8
public 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;
}
public static void main(String[] args) {
int [] array = {19,17,15,12,18,4,7,11,13};
int n=[Link];
[Link]("Original array:");
for (int i=0 ; i <[Link] ; i++)
{
[Link](array[i] + " ");
}
quickSort(array,0,n-1);
[Link]("\n Sorted array:");
for (int i=0 ; i <[Link] ; i++)
{
[Link](array[i] + " ");
}
}
}

Time Complexity for Quick Sort Algorithm ∈ 𝑶(𝒏𝟐 ) in the worst case.

2|Page
Modern Academy - Eng. Noha Ali

You might also like