[go: up one dir, main page]
Scribd
Upload
70 views11 pages

Quick Sort New

Quicksort is a divide and conquer sorting algorithm that works by partitioning an array around a pivot value and recursively sorting the sub-arrays. It first selects a pivot element and partitions the array by placing all elements less than the pivot to the left and greater elements to the right. The pivot element is placed in its final sorted position. It then calls itself recursively to sort the left and right sub-arrays. This continues until the entire array is sorted.

Uploaded by

Bhupesh Dhapola
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
70 views11 pages

Quick Sort New

Quicksort is a divide and conquer sorting algorithm that works by partitioning an array around a pivot value and recursively sorting the sub-arrays. It first selects a pivot element and partitions the array by placing all elements less than the pivot to the left and greater elements to the right. The pivot element is placed in its final sorted position. It then calls itself recursively to sort the left and right sub-arrays. This continues until the entire array is sorted.

Uploaded by

Bhupesh Dhapola
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
You are on page 1/ 11

Quick sort

Quick sort
• Quick Sort is one of the different Sorting Technique which is based on the concept
of Divide and Conquer, just like merge sort. But in quick sort all the heavy
lifting(major work) is done while dividing the array into subarrays, while in case of
merge sort, all the real work happens during merging the subarrays. In case of quick
sort, the combine step does absolutely nothing.
• It is also called partition-exchange sort. This algorithm divides the list into three
main parts:
• Elements less than the Pivot element
• Pivot element(Central element)
• Elements greater than the pivot element
• Pivot element can be any element from the array, it can be the first element, the
last element or any random element. In this tutorial, we will take the rightmost
element or the last element as pivot.
• For example: If in this array {52, 37, 63, 14, 17, 8, 6, 25}, we take 25 as
pivot. So after the first pass, the list will be changed like this.

• {6 8 17 14 25 63 37 52}
• Hence after the first pass, pivot will be set at its position, with all the
elements smaller to it on its left and all the elements larger than to its
right. Now 6 8 17 14 and 63 37 52 are considered as two separate
sunarrays, and same recursive logic will be applied on them, and we
will keep doing this until the complete array is sorted.
How Quick Sorting Works?
1. After selecting an element as pivot, which is the last index of the array in our
case, we divide the array for the first time.
2. In quick sort, we call this partitioning. It is not simple breaking down of array
into 2 subarrays, but in case of partitioning, the array elements are so positioned
that all the elements smaller than the pivot will be on the left side of the pivot
and all the elements greater than the pivot will be on the right side of it.
3. And the pivot element will be at its final sorted position.
4. The elements to the left and right, may not be sorted.
5. Then we pick subarrays, elements on the left of pivot and elements on the right
of pivot, and we perform partitioning on them by choosing a pivot in the
subarrays.
Let's consider an array
with values {9, 7, 5, 11,
12, 2, 14, 3, 10, 6}

• In step 1, we select the last element as the


pivot, which is 6 in this case, and call for
partitioning, hence re-arranging the array in
such a way that 6 will be placed in its final
position and to its left will be all the elements
less than it and to its right, we will have all
the elements greater than it.

• Then we pick the subarray on the left and the


subarray on the right and select a pivot for
them, in the above diagram, we chose 3 as
pivot for the left subarray and 11 as pivot for
the right subarray.
Quicksort Algorithm A[p…q] ≤ A[q+1…r]

• Sort an array A[p…r]


• Divide
• Partition the array A into 2 subarrays A[p..q] and A[q+1..r], such that each element of
A[p..q] is smaller than or equal to each element in A[q+1..r]
• Need to find index q to partition the array

6
quickSort(int arr[], int low, int high)
{ if (low < high)
{
r = partition(arr, low, high);
quickSort(arr, low, r - 1);
quickSort(arr, r + 1, high);
}
}
partition (int arr[], int low, int high) Partition program taking first element as
pivot
{
x= arr[low];
p=low;
for(j = low+1; j<= high; j++)
{
if (arr[j] <= x) //smaller value than key
{
p++; //increment p and swap the value
swap(&arr[p], &arr[j]);
} }
swap(arr[p], arr[low]); //swap the value
return (p + 1);
}
Execution
5 3 12 6 1 7 2 5 3 12 6 1 7 2

p j If(3<=5) p j
Increment p
swap

5 3 12 6 1 7 2 5 3 12 6 1 7 2

p j
p j
If(12<=5)
Increment p
Swap
Else j++
5 3 12 6 1 7 2 5 3 1 6 12 7 2

If(1<=5) p j p j
Increment p
swap

5 3 1 6 12 7 2 5 3 1 6 12 7 2

If(7<=5) p j j
Increment p p
Swap
Else j++
5 3 1 6 12 7 2 5 3 1 2 12 7 6

If(2<=5) p
p j j
Increment p
swap

5 3 1 2 12 7 6 2 3 1 5 12 7 6

pivot p

Swap(a[p], a[low])

You might also like