[go: up one dir, main page]
Scribd
Upload
25 views7 pages

Qick Sort

Qick sort

Uploaded by

piyushatanmaya23
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
25 views7 pages

Qick Sort

Qick sort

Uploaded by

piyushatanmaya23
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/ 7

Quicksort is a sorting algorithm based on the divide and conquer approach where

1. An array is divided into subarrays by selecting a pivot element (element selected from the
array).
While dividing the array, the pivot element should be positioned in such a way that elements
less than pivot are kept on the left side and elements greater than pivot are on the right side of
the pivot.
2. The left and right subarrays are also divided using the same approach. This process continues
until each subarray contains a single element.

3. At this point, elements are already sorted. Finally, elements are combined to form a sorted
array.

Working of Quicksort Algorithm

1. Select the Pivot Element


There are different variations of quicksort where the pivot element is selected from different
positions. Here, we will be selecting the rightmost element of the array as the pivot element.

Select a pivot element


2. Rearrange the Array
Now the elements of the array are rearranged so that elements that are smaller than the pivot
are put on the left and the elements greater than the pivot are put on the right.

Put all the smaller elements on the left and greater on the right of pivot element
Here's how we rearrange the array:
1. A pointer is fixed at the pivot element. The pivot element is compared with the elements
beginning from the first index.

Comparison of pivot element with element beginning from the first index

2. If the element is greater than the pivot element, a second pointer is set for that element.

If the element is
greater than the pivot element, a second pointer is set for that element.

3. Now, pivot is compared with other elements. If an element smaller than the pivot element is
reached, the smaller element is swapped with the greater element found earlier.

Pivot is compared with


other elements.
4. Again, the process is repeated to set the next greater element as the second pointer. And,
swap it with another smaller element.

The process is repeated to set the next greater element as the second pointer.

5. The process goes on until the second last element is reached.

The process goes on until the second last element is reached.

6. Finally, the pivot element is swapped with the second pointer.

Finally, the pivot


element is swapped with the second pointer.

3. Divide Subarrays
Pivot elements are again chosen for the left and the right sub-parts separately. And, step 2 is
repeated.

Select pivot element of in each half and put at correct place using recursion

// Quick sort in C

#include <stdio.h>

// function to swap elements

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

int t = *a;

*a = *b;

*b = t;

// function to find the partition position

int partition(int array[], int low, int high) {

// select the rightmost element as pivot


int pivot = array[high];

// pointer for greater element

int i = (low - 1);

// traverse each element of the array

// compare them with the pivot

for (int j = low; j < high; j++) {

if (array[j] <= pivot) {

// if element smaller than pivot is found

// swap it with the greater element pointed by i

i++;

// swap element at i with element at j

swap(&array[i], &array[j]);

// swap the pivot element with the greater element at i

swap(&array[i + 1], &array[high]);

// return the partition point

return (i + 1);

void quickSort(int array[], int low, int high) {

if (low < high) {

// find the pivot element such that

// elements smaller than pivot are on left of pivot


// elements greater than pivot are on right of pivot

int pi = partition(array, low, high);

// recursive call on the left of pivot

quickSort(array, low, pi - 1);

// recursive call on the right of pivot

quickSort(array, pi + 1, high);

// function to print array elements

void printArray(int array[], int size) {

for (int i = 0; i < size; ++i) {

printf("%d ", array[i]);

printf("\n");

// main function

int main() {

int data[] = {8, 7, 2, 1, 0, 9, 6};

int n = sizeof(data) / sizeof(data[0]);

printf("Unsorted Array\n");

printArray(data, n);

// perform quicksort on data

quickSort(data, 0, n - 1);
printf("Sorted array in ascending order: \n");

printArray(data, n);

You might also like