Geek asks and answers

Quick Sort Algorithm

I used quicksort algorithm to sort

11 8 9 4 2 5 3 12 6 10 7

and I got a list:

4 3 2 5 9 11 8 12 6 10 7.

5 was used as a rod. Now i'm stuck. How to switch to sorting lowersublist and uppersublist?

pivot = 5 11 8 9 4 2 5 3 12 6 10 7

  • Move the hinge to position 0 5 8 9 4 2 11 3 12 6 10 7
  • i (position 1 = 8)
  • j (position 6 = 3) ⇒ replacement of 8 and 3 5 3 9 4 2 11 8 12 6 10 7
  • me (position 2 = 9)
  • j (position 4 = 2) ⇒ replacement 9 and 2 5 3 2 4 9 11 8 12 6 10 7
  • I (position 3 = 4) - no smaller elements than 5 ⇒ swap 5 and 4 4 3 2 5 9 11 8 12 6 10 7 - list after section
+3
source share
2 answers

Quicksort - . , , . , , , , . , , quicksort ( ).

, . - , .

, , .

- . , , . , , , .

+3

, , ( ) 5 :

4 3 2 5 9 11 8 12 6 10 7

. , , , .

, Quicksort, , - , , - , . , :

  • - - , ( ( , , ))

, 5 :

Math.floor(list.length / 2)

. , . ( , ):

concat(qs([4 3 2]), 5,  qs([9 11 8 12 6 10 7])) = 
concat(qs([2]), 3, qs([4]), 5, qs([9, 11, 8, 6, 10, 7]), 12, qs([])) =
concat(2, 3, 4, 5, qs([6, 7]), 8, qs([9, 11, 10]), 12) =
concat(2, 3, 4, 5, qs([6]), 7, qs([]), 8, qs([9, 10]), 11, qs([]), 12) =
concat(2, 3, 4, 5, 6, 7, 8, qs([9]), 10, qs([]), 11, 12) = 
concat(2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)

, , qs, :

qs(<some_left_list>), <the_pivot>, qs(<some_right_list>)

qs ( ( , qs )).

, . , .

0

More articles:


All Articles