Comments

  1. Anonymous
    4 months ago
    2024-9-22 23:29:03

    1. When we use quick sort to sort an array. The algorithm will first randomly select a pivot. and all elements lower then pivot will be placed at left side of pivot, any elements larger then pivot will be placed at right side. Then we use reccursion to redo this process to left side and right side, untill lower bound = higher bound.

  2. C3EZ
    4 months ago
    2024-9-22 23:40:34

    3. The choice of pivot in the quick sort algorithm is important. A pivot in a different position changes the number of steps required. By choosing a pivot, it may split the array into two parts of equal length, making the recursion tree more balanced and avoiding too much recursion on one side.

  3. C3EZ
    4 months ago
    2024-9-22 23:49:19

    2. Best case: O(nlogn):
    When we choose the pivot that can divide array into two equal length part everytime, we need logn times recurrsion. Because we devide by 2 each time.

    And for each recurrsion, we need compare all the elements in the array to divide it into lower than pivot part and larger than pivot part. This have the complexity of O(n)

    Hence our best case will be O(n*logn)

    Worst case: O(n^2):
    When we choose the pivot that is the largest or smallest elements in the array, we need n times recurrsion. This makes we can only sort one elements at a time.

    And for each recurrsion, we need compare all the elements in the array to divide it into lower than pivot part and larger than pivot part. This have the complexity of O(n)

    Hence our best case will be O(n*n) = O(n^2)

Send Comment Edit Comment


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
Previous
Next