Write about Quick Sort.
Fast Sort or Quick Sort:
It is among the most widely used sorting methods. The average-case behavior of Quicksort is the best of all the sorting techniques. C.A.R. Hoare developed this.
The array that needs to be sorted is divided to implement the Quick sort algorithm. Recursively sorting is also done for each partition in turn. One array element from the partition is selected as the key value. The first element of an array might be this key value. In other words, if an is an array, then the keys key=a[0] and reset of the array element are divided into two partitions as shown.
An element smaller than the key value is present in one partition.
Elements in another partition that are larger than the key value are present.
Figure depicts the key and division of an array element.
Consider the following array as an illustration:
The key value chosen in this instance is 45. The element (key+1) and the last element are then denoted by two indices, low and high. Beginning on the left, the low index chooses an element whose value is higher than the key value. then these components are switched. Until every element to the left of the key is smaller than the key value, this process is repeated. Additionally, every element to the key's right is bigger than the key value.
The procedures for inserting the key value 45 in the appropriate location in the array are listed below. On each line, the element that is being compared is surrounded.
.jpg)
Two subarrays have been created from the given Array. 142639 is the first subarray, and 686197779990 is the second subarray. Until the entire array is sorted, we can repeat this process on each of these subarrays. Due to the partitioning of the array elements. This method is known as a "partition-exchange technique" because the array elements are divided and swapped.
Each time the given array is divided into two smaller subarrays for the quick sort technique, each of these subarrays can be processed either iteratively or recursively. The following describes the recursive quick sort algorithm:
Algorithm of Quick sort:
Where,
a → Represents the list of elements.
l → Represents the position of the first element in the list( only at starting point, it's value change during the execution of the function).
h → Represents the position of the last element in the list(only at starting point, its value change during the execution of the function).
low = l
high = h
key =a[(l+h)/2] [middle element of the element of the list]
key =a[(l+h)/2] [middle element of the element of the list]
step 2: Repeat through step 7 while (low <=key)
step 3: Repeat step 4 while (a[low] <key))
step 4: low = low+1
step 5: Repeat step 6 while 9a[high] <key))
step 6: high = high-1
step 7: if(low<=high)
(a) temp = a[low]
(b) a[low] = a[high]
(c) a[high] = temp
(d) low = low+1
(e) high = high-1
step 8: if (l<high)Quick_sort (a, l, high)
step 9: if(low <high) Quick_sort (a low, h)
step 10: Exit
Example : program to sort the element of an array using quick sort technique.
#include<stdio.h>
#define max 100
int a[max],n,i,l,h;
void main()
{
void input (void);
input();
getch();
}
void input(void)
{
void quick_sort (int a[],int l, int h);
void output (int a[], int n);
printf("How many element in the array :");
scanf("%d",&n);
printf("\n");
printf("Enetr the element :\n"");
for(i=0;i<=n-1;i++)
{
scanf("%d",&a[i]);
}
l=0;
h =n-1;
quick_sort(a, l, h);
printf("sorted array :\n: ");
output( a, n);
}
void quick_sort(int a[],int l, int h)
{
int temp , key ,low, high;
low =l;
high= h;
key =a[(low+high)/2];
do
{
while (key > a [low])
{
low ++;
}
while (key < a [high])
{
high --;
}
if(low <=high)
{
temp=a[low];
a[low] =a[high];
a[high] =temp;
}}
while (low <=high);
if(l <high)
quick_sort (a, l ,high);
if(low<h)
quick_sort (a, low, h)
}
void output (int a[], int n)
{
for(i=0;i<=n-1;i++)
{
printf("%d\n", a[i]);
}}
Output:
How many element in the array : 10
Enter the elements:
8
2
3
6
5
1
9
4
56
78
Sorted Array
1
2
3
4
5
6
8
9
56
78
Write about Quick Sort.
Reviewed by For Learnig
on
March 16, 2023
Rating:
Reviewed by For Learnig
on
March 16, 2023
Rating:
.png)
No comments:
If you have any doubts, please tell me know