Junaid (quick Sort)

By the Name of “Allah” . the most merciful & mighty .Presentation No 1 Junaid Khan C.No 33 (Morning Shift)

Topic :QUICK SORT – Quick sort is very Popular sorting method. C.A.R Hoare introduced it in 1962. It is very important method of internal sorting. According to this algorithm it is faster and easier to sort two small arrays instead of one larger array. The quick sort is an algorithm of Divide-and-conquer. It is also called Partition exchange sort.

Explaining this mechanism with an Example 1

T

40

2

30

3

4

5

6

7

60

20

10

70

50

i j Let T be array with 7 elements we will start the comparison form right to left .we use two pointing variables I and j. i= Points to 1st location & j = To last location

Compare T[j] with T[I] , if T[j] is greater than T[I] then decrement the j pointer by 1 until T[j]>T[i].

T

40

30

60

20

10

70

50

j j j i If at any point T[j]
i

30

60

20

40

j

70

50

And

start comparison from left to right, if T[i]
T

10

30

60

i

i

i

20

40

70

50

j

If at any point T[i]>T[j] and j>I then swap T[i] and T[j]. And start from right to left comparison, if T[j]T[i]).

10

30

60

i

i

i

10

30

40

i

20

40

70

50

j

20

60

j

j

70

50

T

10

30

20

i

40

60

70

50

i j

At some point I and j will become equal this shows that the element of left side of that are less than the middle element and elements at right side are greater than the element position I or j. So this is the our dividing point the elements of left side are left sub array and the elements on right side are right sub array.

• Now we will use a stack to postpone the larger sub problem (sub array) by pushing it on the top of the stack and continue with the smaller array and use the same procedure as used above ,after that we will pop the stack top and start the same procedure with that sub array and so on. • In this example we have both arrays equal so we will push right array on the stack top and proceed with left sub array.

T

10

30

20

i

j

j

T

10

i

T

10

i

ij

30

20

j

j

20

30

j

The left sub array become sorted now we will sort the right sub array as follow

5

60

T

6

7

70

50

j

i

T

5

6

7

50

70

60

i

i

5

T

50

i j

j 6

7

60

70

j

Now the right sub array become also sorted so we have following sorted array

T

10

20

30

40

50

60

70

Any Question

?

You are not Kids Lilo

MESSAGE Success is not always permanent and Failure is not Always Final, So don't loss effort until and unless your .Victory make History (HITLER)

Thanks a lot for your sincere Attention

!Have a nice day