Scribd
Upload
20 views113 pages

Quicksort Data Structures

Quick Sort is an efficient sorting algorithm that divides an array into smaller and larger sections based on a pivot element, achieving an average time complexity of O(n log n). The algorithm does not require equal-sized partitions but focuses on placing smaller elements before the pivot and larger elements after it. This method is significantly faster compared to other sorting algorithms like Bubble Sort.

Uploaded by

You Me
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
20 views113 pages

Quicksort Data Structures

Quick Sort is an efficient sorting algorithm that divides an array into smaller and larger sections based on a pivot element, achieving an average time complexity of O(n log n). The algorithm does not require equal-sized partitions but focuses on placing smaller elements before the pivot and larger elements after it. This method is significantly faster compared to other sorting algorithms like Bubble Sort.

Uploaded by

You Me
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

What is Quick

Sort ??

Division here is to divide the list into two smaller and


larger where there is a so-called (pivot) and it is
determined smaller or larger is not required to be a
number of elements in both sections of equal or
arranged in ascending or descending order, but what
is important in the partitioning phase is to make the
smallest of the axis division in the department and the
largest in the last section.
What is Quick
Sort ??
This algorithm is the order of the array at a rate of
( n*log n), where n is the step number of the elements of
the array ..
Meaning:
If we have a array of the element 128, this will
Khurazem Petrtaha in step 896 ..
And this number is very appropriate when compared
to other ranking algorithms
For example, in Bubble sort algorithm will need to step
What is Quick
Sort ??

numbers p numbers greater than


less than p or equal to p
Q uick

S
ort

4 6 1 8 3 9 5 2 7
1 2 3 4 5 6 7 8 9
Q uick

S
ort Pivot =
41
4 6 1 8 3 9 5 2 7
1 2 3 4 5 6 7 8 9
Q uick

S ort

4 6 1 8 3 9 5 2 7
1 2 3 4 5 6 7 8 9
i

Pivot =
Q uick

S ort

4 6 1 8 3 9 5 2 7
1 2 3 4 5 6 7 8 9
i j

Pivot =
Q uick

S ort
41>79 ?
?
41 62 8 3 9 5 2 7
13 4 5 6 7 8 9
j
i

Pivot =
Q uick

S ort
41>79 ?
? Fal
41 62 8 3 9 5 2 7
13 4 5 6 7 8 9
j
i

Pivot =
Q uick

S ort

4 6 1 8 3 9 5 2 7
1 2 3 4 5 6 7 8 9

j-
i j

Pivot =
Q uick

S ort
41>28 ?
?
41 62 8 3 9 5 2 7
13 4 5 6 7 8 9
j
i

Pivot =
Q uick

S ort
41>28 ?
?
41 62 8 3 9 5 2 7
13 4 5 6 7 8 9
j
i

Pivot =
Tru
Q uick

S ort

4 6 1 8 3 9 5 2 7
1 2 3 4 5 6 7 8 9

i j

Pivot =
Q uick

S ort
Pivot =
j
2 6 1 8 3 9 5 4 7
8 2 3 4 5 6 7 1 9

i j

Pivot =
Q uick

S ort
i+
2
8
6
2
1
3 +
8
4
3
5
9
6
5
7
4
1
7
9

i j

Pivot =
Q uick

S ort
62>41 ?
?
28 62 3 9 5 4 7
84 13 5 6 7 1 9

i j

Pivot =
Q uick

S ort
62>41 ?
?
28 62 3 9 5 4 7
84 13 5 6 7 1 9

Tru
i j

Pivot =
Q uick

S ort

2 6 1 8 3 9 5 4 7
8 2 3 4 5 6 7 1 9

i j

Pivot =
Q uick

S ort Pivot =
i
2 4 1 8 3 9 5 6 7
8 1 3 4 5 6 7 2 9

i j

Pivot =
Q uick

S ort

2 4 1 8 35 9 5 6 7
8 1 3 4 6 7 2 9

i
j- j

Pivot =
Q uick

S ort
41>57 ?
?
2 4 13 84 3 6 7
8 1 96 57 5 2 9

i j

Pivot =
Q uick

S ort
41>57 ?
?Fal
2 4 13 84 3 6 7
8 1 96 57 5 2 9

i j

Pivot =
Q uick

S ort

2 4 1 8 35 9 5 6 7
8 1 3 4 6 7 2 9

i
j- j

Pivot =
Q uick

S ort

2 4 1 8 3 9 5 6 7
8 1 3 4 5 6 7 2 9

i j

Pivot =
Q uick

S ort
41>96 ?
?
2 4 13 84 3 6 7
8 1 96 57 5 2 9

i j

Pivot =
Q uick

S ort
41>96 ?
?
2 4 13 84 3 6 7
8 1 96 57 5 2 9

i
Fal j

Pivot =
Q uick

S ort

2 4 1 8 3 9 5 6 7
8 1 3 4 5 6 7 2 9

i j

Pivot = j-
Q uick

S ort

2 4 1 8 3 9 5 6 7
8 1 3 4 5 6 7 2 9

i j

Pivot =
Q uick

S ort
41>35 ?
?
2 4 13 84 3 6 7
8 1 96 57 5 2 9

i j

Pivot =
Q uick

S ort
41>35 ?
?
2 4 13 84 3 6 7
8 1 96 57 5 2 9
i j

Pivot = Tr
Q uick

S ort

2 4 1 8 3 9 5 6 7
8 1 3 4 5 6 7 2 9
i j

Pivot =
Q uick

S ort
Pivot =
j
2 3 1 8 4 9 5 6 7
8 5 3 4 1 6 7 2 9
i j

Pivot =
Q uick

S ort
i+
2
8
3
5
1
3
i
+ j
9
6
5
7
6
2
7
9

84 41

Pivot =
Q uick

S ort
13>41 ?
?
2 3 13 5 6 7
84 41
8 5 7 2 9
96

i j

Pivot =
Q uick

S ort
13>41 ?
?
2 3 13 5 6 7
84 41
8 5 7 2 9

Fal
96
i j

Pivot =
Q uick

S ort
i+
2
8
3
5
1
3 + 9
6
5
7
6
2
7
9

84
41
Pivot =
Q uick

S ort
84>41 ?
?
2 3 13 5 6 7
84 41
8 5 7 2 9
96

i j
Pivot =
Q uick

S ort

2 3 1 8 4 9 5 6 7
8 5 3 4 1 6 7 2 9
i j

Pivot =
Q uick

S ort

2 3 1 4 8 9 5 6 7
8 5 3 1 4 6 7 2 9
i j

Pivot =
Q uick

S ort

2 3 1 4 8 9 5 6 7
8 5 3 1 4 6 7 2 9
i

Pivot = j+
j
Q uick

S ort i
2
8
3
5
1
3 = 8
4
9
6
5
7
6
2
7
9

j
i
j

Pivot =
Q uick

S ort
a[0
]
a[1
]
a[2
]
a[3
]
a[4
]
a[5
]
a[6
]
a[7
]
a[8
]2 3 1 4 8 9 5 6 7
8 5 3 1 4 6 7 2 9

Pivot =
Q uick

S ort
a[0
]
a[1
]
a[2
]
2 3 1 4 8 9 5 6 7
8 5 3 1 4 6 7 2 9

Pivot =
Q uick

S ]
ort a[1
a[0
]
a[2
]
a[0
]
a[1
]
a[2
]
a[3
]
a[4
]2 3 1 4 8 9 5 6 7
8 5 3 1 4 6 7 2 9

Pivot =
Q uick

S
]
ort a[1
a[0
]
a[2
]
a[0
]
a[0
]
a[1
]
a[2
]
a[3
]
a[4
]2 3 1 4 8 9 5 6 7
8 5 3 1 4 6 7 2 9

numbers less than numbers greater than or equal to


p
p
Q uick

S
ort Now we sort numbers less than
p 35
2
8 13

4 8 9 5 6 7
Q uick

S
ort Pivot =
28
2 3 1
8 5 3

4 8 9 5 6 7
Q uick

S
ort Pivot =
28
2 3 1
8 5 3

4 8 9 5 6 7
Q uick

S ort
2 3 1
8 5 3
j
i

Pivot = 4 8 9 5 6 7
Q uick

S ort 28>13 ?
?2
8

i
35
13
j

Pivot = 4 8 9 5 6 7
Q uick

S ort 28>13 ?
?2
8
i
35
13
j

Tru
Pivot = 4 8 9 5 6 7
Q uick

S ort
2 3 1
8 5 3
j
i

Pivot = 4 8 9 5 6 7
Q uick

S ort Pivot =
j
1 3 2
3 5 8
j
i

Pivot = 4 8 9 5 6 7
Q uick

S ort i+
+
1 2
3 8
i j
35

Pivot = 4 8 9 5 6 7
Q uick

S ort 35>28 ?
? i j

Tru
13 35 28

Pivot = 4 8 9 5 6 7
Q uick

S ort
1 3 2
3 5 8
i j

Pivot = 4 8 9 5 6 7
Q uick

S ort
1 2 3
3 8 5
i
j

Pivot = 4 8 9 5 6 7
Q uick

S
ort
a[0
]
a[0
a[0
]

]1 2 3
3 8 5

4 8 9 5 6 7
Q uick

S ort
Now we sort numbers greater than or
equal to p
84 5 62
96 7 79

1 2 3 4
Q uick

S ort a[0
]
a[4
a[1
]
a[2
]
a[3
]

]8 9 5 6 7
4 6 7 2 9

1 2 3 4
Q uick

S ort Pivot =
84
8 9 5 6 7
4 6 7 2 9

1 2 3 4
Q uick

S ort i=8
4
j=7
9
8 9 5 6 7
4 6 7 2 9
i
j

1 2 3 4
Q uick

S ort 84>79 ?
? 84
96

i
5
7
6
2
7
9

1 2 3 4
Q uick

S ort 84>79 ?
? 84
96
i
5
7
6
2
7
9

Tru
j

1 2 3 4
Q uick

S ort
8 9 5 6 7
4 6 7 2 9
i
j

1 2 3 4
Q uick

S ort
7 9 5 6 8
9 6 7 2 4
i j

1 2 3 4
Q uick

S ort
7 9 5 6 8
9 6 7 2 4
i j

1 2 3 4
Q uick

S ort i=9
6
7 9 5 6 8
9 6 7 2 4
i j

1 2 3 4
Q uick

S ort 96>84 ?
?
79 57 6
96 2
84
i j

1 2 3 4
Q uick

S ort 96>84 ?
?
79 57 6
96 2
84
i j

1 2 3 4
Tru
Q uick

S ort
7 9 5 6 8
9 6 7 2 4
i j

1 2 3 4
Q uick

S ort
7 8 5 6 9
9 4 7 2 6
i
j

1 2 3 4
Q uick

S ort j-
7
9
8
4
i
- 6
2
j
9
6

57

1 2 3 4
Q uick

S ort 84>62 ?
?
79 5 62
84 7 96
i
j

1 2 3 4
Q uick

S ort 84>62 ?
?
79 5 62
84 7 96
i
j

1 2 3 4
Tru
Q uick

S ort
7 8 5 6 9
9 4 7 2 6
i j

1 2 3 4
Q uick

S ort
7 6 5 8 9
9 2 7 4 6
i j

1 2 3 4
Q uick

S ort i+
+
7 6 5 8 9
9 2 7 4 6
i j

1 2 3 4
Q uick

S ort 57>84 ?
?
79 5 84
62 7 96
i
j

1 2 3 4
Q uick

S ort 57>84 ?
?
79 5 84
62 7 96

F i
j

1 2 3 4
als
Q uick

S ort
7 6 5 8 9
9 2 7 4 6
i j

1 2 3 4
Q uick

S ort i+
+
7 6 5 8 9
9 2 7 4 6
i
j

1 2 3 4
Q uick

S ort i
7
9
=
6
2
5
7
8
4
i
9
6

1 2 3 4
j j
Q uick

S ort a[0
]
a[1
]
a[2
]
a[0
]
a[0
]

7 6 5 8 9
9 2 7 4 6
i j

1 2 3 4
Q uick

S ort a[0
]
a[1
]
a[2
]
a[0
]
a[0
]

7 6 5 8 9
9 2 7 4 6
numbers
numbers less than greater than or
p equal to p

1 2 3 4
Q uick

S ort
7 6 5 9
9 2 7 6

1 2 3 4 8
Q uick

S ortNow we sort numbers greater than or equal to


p

96

1 2 3 4 7 6 5 8
Q uick

S ort
i=j=
96 i
j
96

1 2 3 4 7 6 5 8
Q uick

S ort Now we sort numbers less than


p
7 6 5
9 2 7

1 2 3 4 8 9
Q uick

S ort
Pivot =
79
79 5
62 7
j
i

1 2 3 4 8 9
Q uick

S ort 79>57 ?
? 79
62
5
7
j
i

1 2 3 4 8 9
Q uick

S ort 79>57 ?
? 79
62
i
5
7
j

1 2 3 4
Tru 8 9
Q uick

S ort

7 6 5
9 2 7
i j

1 2 3 4 8 9
Q uick

S ort

5 6 7
7 2 9
i j

1 2 3 4 8 9
Q uick

S ort i+
5
7 +i
7
9
j
62

1 2 3 4 8 9
Q uick

S ort 62>79 ?
?
57 62 79

1 2 3 4 i j 8 9
Q uick

S ort 62>79 ?
? 57
79
62

1 2 3 4
Fa ls
e i j
8 9
Q uick

S ort i+
5
7 + 7
9

i
62 j

1 2 3 4 8 9
Q uick

S ort i
5
7 = 7
9

1 2 3 4
j j

8 9
Q uick

S ort
a[0
]
a[0
a[1
]

]
5 6 7
7 2 9

1 2 3 4 8 9
Q uick

S ort
a[0
]
a[0
a[1
]

]
5 6 7
7 2 9

numbers less than


p

1 2 3 4 8 9
Q uick

S ort

5 6
7 2

1 2 3 4 7 8 9
Q uick

S ort Now we sort numbers less than


p

5 6
7 2

1 2 3 4 7 8 9
Q uick

S ort Pivot =
84
i=57 j=62

57 62

i j

1 2 3 4 7 8 9
Q uick

S ort 57>62 ?
? i j

Fals
57 62

1 2 3 4 7 8 9
Q uick

S ort j-
- 6
2

57

1 2 3 4 ij 7 8 9
Q uick

S ort i=
j
57
62
1 2 3 4 7 8 9
Q uick

S ort

5 6
7 2

numbers greater
than or equal to
p
1 2 3 4 7 8 9
Q uick

S ort Now we sort numbers greater than or equal to


p

62

1 2 3 4 5 7 8 9
Q uick

S ort Pivot =
79
i=79 j=79

62

i j

1 2 3 4 5 7 8 9
Q uick

S ort i
=
1 2 3 4 5
j 7 8 9
Q uick

S ort

6
2

1 2 3 4 5 7 8 9
Q uick

S
ort
a[0 a[1 a[2 a[3 a[4 a[5 a[6 a[7
] ] ] ] ] ] ] ]
a[8
]1 2 3 4 5 6 7 8 9
3 8 5 1 7 2 9 4 6

You might also like