Quick
sort
} Quick
sort is a sorting technique designed based on the divide-and-conquer method. In
this sorting technique, array elements are divided into two sub arrays
depending on a specialized element called “Pivot” element.
} Quick
sort is also known as partition exchange sort.
Procedure:
Step 1: Initialize
the first element as pivot element.
Step 2: Initialize
a variable i at the first index and another variable j at the last index + 1.
Step 3: Increment
i value by 1 until a[i]>pivot element.
Step 4: Decrement
j value by 1 until a[i]<pivot element
if i<j then
interchange a[i] & a[j] elements
end
if
Step 5: Repeat
step 3 and Step 4 until i>=j.
Step 6: Interchange
the values of a[j] and pivot element.
} If
the above procedure executed one time, then we say one iteration has completed.
After one iteration pivot value will be sorted order at ‘j’ index.
} Repeat
the same procedure again from starting index to j-1 index.
} Repeat
the same procedure again from j+1 index to last index.
} When
all the passes are completed, then list of array elements is available in
sorted order.
Example:
Before sorting the given array is a={27,10,36,18,
25, 45}
Given no.of
elements n=6
Arrange
these group of elements into array.
27
|
10
|
36
|
18
|
25
|
45
|
1 2 3 4 5 6
Pivot
= 27
i=1,
j=6
27
|
10
|
36
|
18
|
25
|
45
|
pivot, i j
(27>=27)
True, move i=2
(27>=10)True
, move i=3
(27>=36)False
27
|
10
|
36
|
18
|
25
|
45
|
pivot i j
(27<=45)
True , move j=5
(27<=25)
False
27
|
10
|
36
|
18
|
25
|
45
|
pivot i j
i=3 ,
j=5
(3<5)
True
Interchange
the values in 3rd and 5th index values
27
|
10
|
25
|
18
|
36
|
45
|
pivot i j
i>=j (3>=5) false
Repeat
steps 3 and 4
(27>=25) True, move i=4
(27>=18)True
, move i=5
(27>=36)False
27
|
10
|
25
|
18
|
36
|
45
|
pivot i, j
(27<=36) True, move j=4
(27<=18)
False
27
|
10
|
25
|
18
|
36
|
45
|
pivot j i
j=4,
i=5
i<j (5<4)
False
i>=j
(5>=4) True
Interchange
the value in j index and pivot (i.e, 18 and 27)
18
|
10
|
25
|
27
|
36
|
45
|
pivot j i
Apply the same algorithm for
18,10,25 values
18
|
10
|
25
|
pivot, i j
(18>=18) True, move i=2
(18>=10)True
, move i=3
(18>=25)False
18
|
10
|
25
|
pivot i, j
(18<=25)
True, move j=2
(18<=10)False
18
|
10
|
25
|
pivot j i
i=3, j=2
3<2
(False)
3>=2
(True)
Interchange
the values in j index and pivot
10
|
18
|
25
|
pivot j i
-> The sorted order is 10, 18, 25, 27, 36, 45
0 comments:
Post a Comment