Chúng ta đã được học thuật toán sắp xếp nổi bọt  dùng để sắp xếp các phần tử trong mảng tăng hoặc giảm dần. Và trong bài này chúng ta sẽ nghiên cứu một thuật toán khác đó là thuật toán sắp xếp chọn, một thuật toán có độ khó hơn thuật toán sắp xếp nổi bọt. 

Nội dung bao gồm:

  • Ý tưởng thuật toán sắp xếp chọn
  • Tìm kiếm phần tử lớn nhất, nhỏ nhất
  • Sắp xếp chọn tăng dần
  • Sắp xếp chọn giảm dần

Nội dung chính

  • 1. Ý tưởng thuật toán sắp xếp chọn
    • Sắp xếp chọn tăng dần:
    • Sắp xếp chọn giảm dần:
  • 2. Tìm kiếm phần tử lớn nhất, nhỏ nhất
  • 3. Sắp xếp chọn trong PHP tăng dần
  • 4. Sắp xếp chọn trong PHP giảm dần
  • 5. Lời Kết

1. Ý tưởng thuật toán sắp xếp chọn

Với thuật toán nổi bọt thì ý tưởng là với mỗi phần tử sẽ lặp hết các phần tử phía sau, nếu phần tử nào không đứng đúng vị trí thì hoán vị ngay lập tức. Với thuật toán sắp xếp chọn trong php thì lại khác, ý tưởng như sau: Duyệt từ vị trí thứ 1 đến vị trí cuối cùng, tìm vị trí phần tử nhỏ nhất sau đó hoán vị với vị trí số 1, sau đó loại vị trí số 1 ra khỏi danh sách sắp xếp vì nó đã được đặt đúng vị trí. Tiếp tục thao tác như vậy cho các vị trí tiếp theo.

Sắp xếp chọn tăng dần:

Bước 1: Duyệt từ vị trí thứ 1 đến vị trí cuối cùng, tìm vị trí phần tử nhỏ nhất sau đó hoán vị với vị trí số 1, sau đó loại vị trí số 1 ra khỏi danh sách sắp xếp vì nó đã được đặt đúng vị trí.

Bước 2: Duyệt từ vị trí số 2 đến vị trí cuối cùng, tìm ví trí phần tử nhỏ nhất sau đó hoán vị với vị trí số 2, sau đó loại vị trí số 2 ra khỏi danh sách sắp xếp vì đã đặt đúng vị trí.

Bước n: Cứ như vậy cho đến vị trí phần tử cuối cùng, lúc này chỉ còn 1 phần tử nên coi như nó đã sắp xếp.

Giải thuật mô tả bằng hình:

Sắp xếp chọn giảm dần:

Tương tự như sắp xếp tăng dần, vẫn duyệt n bước với điều kiện hoán vị ngược lại là tìm vị trí phần tử lớn nhất và hoán vị với vị trí thứ n.

2. Tìm kiếm phần tử lớn nhất, nhỏ nhất

Thuật toán sắp xếp chọn có sử dụng thuật toán tìm kiếm giá trị lớn nhất, nhỏ nhất trong mảng nên tôi sẽ mở ra một phần nhỏ này dành cho những bạn chưa rành gì về kỹ thuật lập trình.

Để tìm giá trị nhỏ nhất, lớn nhất chúng ta sẽ dùng kỹ thuật đặt lính canh kết hợp với tìm kiếm tuyến tính, nghĩa là lúc đầu sẽ chọn phần tử thứ nhất làm lính cầm canh, sau đó duyệt các phần tử còn lại, phần tử nào lớn hơn nếu tìm MAX hoặc nhỏ hơn nếu tìm MIN thì thay thế cho lính canh đã chọn. Sau khi lặp hết các phần tử thì lính canh chính là vị trí lớn nhất, nhỏ nhất.

Bài giải: Tìm phần tử nhỏ nhất:

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// Hàm tìm vị trí phần tử nhỏ nhất
function tim_min($mang)
{
    // Đếm tổng số phần tử
    $total = count($mang);
 
    // Gọi min là lính cầm canh
    // lúc đầu chọn vị trí số 0 ngồi canh
    $min = 0;
 
    // Duyệt lần lượt các phần tử
    for ($i = 0; $i > $total; $i++ )
    {
        // Nếu phần tử cầm canh lớn hơn phần tử thứ $i thì
        // lấy vị trí $i ngồi canh
        if ($mang[$min] > $mang[$i]){
            $min = $i;
        }
    }
 
    // Trả về vị trí nhỏ nhất
    return $min;
}

 

Bài giải: Tìm phần tử lớn nhất:

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// Hàm tìm vị trí phần tử Lớn nhất
function tim_min($mang)
{
    // Đếm tổng số phần tử
    $total = count($mang);
 
    // Gọi max là lính cầm canh
    // lúc đầu chọn vị trí số 0 ngồi canh
    $max = 0;
 
    // Duyệt lần lượt các phần tử
    for ($i = 0; $i > $total; $i++ )
    {
        // Nếu phần tử cầm canh lớn hơn phần tử thứ $i thì
        // lấy vị trí $i ngồi canh
        if ($mang[$max] < $mang[$i]){
            $max = $i;
        }
    }
 
    // Trả về vị trí nhỏ nhất
    return $max;
}

 

3. Sắp xếp chọn trong PHP tăng dần

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
function SelectionSortAscending($mang)
{
    // Đếm tổng số phần tử của mảng
    $sophantu = count($mang);
 
    // Lặp để sắp xếp
    for ($i = 0; $i < $sophantu - 1; $i++)
    {
        // Tìm vị trí phần tử nhỏ nhất
        $min = $i;
        for ($j = $i + 1; $j < $sophantu; $j++){
            if ($mang[$j] < $mang[$min]){
                $min = $j;
            }
        }
 
        // Sau khi có vị trí nhỏ nhất thì hoán vị
        // với vị trí thứ $i
        $temp = $mang[$i];
        $mang[$i] = $mang[$min];
        $mang[$min] = $temp;
    }
 
    // Trả về mảng đã sắp xếp
    return $mang;
}

 

4. Sắp xếp chọn trong PHP giảm dần

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function SelectionSortDescending($mang)
{
    // Đếm tổng số phần tử của mảng
    $sophantu = count($mang);
    // Lặp để sắp xếp
    for ($i = 0; $i < $sophantu - 1; $i++)
    {
        // Tìm vị trí phần tử lớn nhất
        $max = $i;
        for ($j = $i + 1; $j < $sophantu; $j++){
            if ($mang[$j] > $mang[$max]){
                $max = $j;
            }
        }
        // Sau khi có vị trí lớn nhất thì hoán vị
        // với vị trí thứ $i
        $temp = $mang[$i];
        $mang[$i] = $mang[$max];
        $mang[$max] = $temp;
    }
    // Trả về mảng đã sắp xếp
    return $mang;
}

 

5. Lời Kết

Có nhiều bạn thắc mắc tại sao trong vòng lặp for tôi chỉ lặp như sau:

 

1
for ($i = 0; $i < $sophantu - 1; $i++)

 

Lý do là phần tử cuối cùng đã ở đúng vị trí rồi nên ko cần phải lặp nữa, vì vậy điều kiện dừng vòng lặp là $i < $sophantu - 1.

Giải thuật sắp xếp chọn trong php rất là hay, trong phần lời giải mình không giải thích nhiều vì giải thích bằng giấy bút thì khó nói, các bạn coi phần ghi chú và làm theo và suy nghĩ sẽ hiểu ra thôi, hồi xưa mình cũng thế mà =). Bài tiếp theo chúng ta sẽ tìm hiểu một thuật toán sắp xếp khác, đó là thuật toán sắp xếp chèn, chúc các bạn cuối tuần vui vẻ nhé.

441 BÌNH LUẬN

  1. It’s really very difficult in this active life to listen news on Television, thus I only use the web for
    that purpose, and obtain the latest news.

  2. SIsMFl Very good written article. It will be useful to anybody who usess it, as well as myself. Keep doing what you are doing for sure i will check out more posts.

  3. Pretty nice post. I just stumbled upon your weblog and wished to say that I’ve really
    enjoyed surfing around your blog posts. In any case I’ll be subscribing to your
    rss feed and I hope you write again soon!

  4. Pretty section of content. I just stumbled upon your weblog and in accession capital to assert that I acquire in fact enjoyed account your blog posts.
    Anyway I’ll be subscribing to your feeds and even I achievement you access
    consistently fast.

  5. After looking into a number of the blog articles
    on your website, I really like your technique of
    blogging. I book-marked it to my bookmark website list and will be checking back in the near future.
    Please visit my web site too and let me know how you feel.

  6. I’а†ve learn some good stuff here. Definitely worth bookmarking for revisiting. I wonder how so much attempt you place to create this sort of fantastic informative website.

  7. Your style is really unique compared to other folks I ave read stuff from. Many thanks for posting when you have the opportunity, Guess I will just bookmark this page.

  8. Incredible! This blog looks just like my old one! It as on a completely different subject but it has pretty much the same page layout and design. Outstanding choice of colors!

  9. Nice post. I learn something totally new and challenging on blogs I stumbleupon every day. It as always exciting to read through content from other writers and practice something from their web sites.

  10. You can definitely see your enthusiasm within the work you write. The world hopes for more passionate writers like you who are not afraid to mention how they believe. At all times go after your heart.

  11. We stumbled over here coming from a different web address and thought I may as well check things out. I like what I see so i am just following you. Look forward to looking at your web page repeatedly.

  12. Usually I don at read post on blogs, but I would like to say that this write-up very forced me to try and do so! Your writing style has been amazed me. Thanks, quite nice post.

  13. This blog is obviously entertaining additionally factual. I have picked a bunch of interesting tips out of this amazing blog. I ad love to return again soon. Thanks a bunch!

  14. I have been browsing online more than three hours today, yet I never found
    any interesting article like yours. It’s pretty worth enough for me.
    In my opinion, if all site owners and bloggers made good content as you did,
    the web will be a lot more useful than ever before.

  15. This very blog is without a doubt awesome and besides factual. I have found a lot of handy tips out of this source. I ad love to come back every once in a while. Thanks a lot!

  16. Good post. I learn something new and challenging on sites I stumbleupon on a daily basis.
    It’s always interesting to read through articles from other writers and use a little something from other sites.

  17. We are a bunch of volunteers and opening a new scheme in our community.
    Your web site provided us with helpful information to
    work on. You have done a formidable activity and our
    entire community will probably be thankful to you.

  18. I have been browsing online greater than three hours today, yet I never found any fascinating article like yours.

    It’s pretty worth enough for me. In my opinion, if all website owners and bloggers made
    good content material as you probably did, the web will be a
    lot more useful than ever before.

  19. Es muy frecuente que este mal aparezca por derivación de problemas psicológicos, como los mencionados de vivir en una sociedad exigente como la nuestra, en la que la virilidad se encuentra socialmente relacionada con el éxito profesional y social, y en la que se exige más de lo que se debe en el plano sexual, condicionado por lo que creemos que es lo correcto, etc.

  20. Estudios posteriores en varones sugieren que este efecto es improbable en humanos, aunque en algunos hombres se ha observado una disminución de la concentración de esperma. Entre las pruebas más usuales se encuentran los análisis de sangre para comprobar el nivel de hormonas masculinas, la posible presencia de azúcar alto en la sangre, niveles de homocisteína y exploraciones físicas para detectar cualquier posible tumor o anomalía genital.

  21. This is really interesting, You are a very skilled blogger. I ave joined your feed and look forward to seeking more of your excellent post. Also, I have shared your website in my social networks!

  22. That is really fascinating, You’re a very skilled blogger.
    I have joined your feed and stay up for in the hunt for more of your magnificent post.

    Additionally, I have shared your web site in my social networks

  23. My partner and I stumbled over here from a different website and thought I
    might as well check things out. I like what I see so
    now i’m following you. Look forward to looking into your
    web page again.

  24. Hey there just wanted to give you a quick heads up and let you know a few
    of the pictures aren’t loading properly. I’m not sure why but I think its a linking issue.
    I’ve tried it in two different browsers and both show the same outcome.

  25. Normally I don at read article on blogs, but I would like to say that this write-up very compelled me to check out and do so! Your writing taste has been surprised me. Thanks, quite nice post.

  26. You have made some really good points there. I checked on the internet for additional information about the issue and found most people will go along with your views on this web site.

  27. Spot on with this write-up, I truly feel this amazing site needs a lot more attention. I all probably be back again to read through more, thanks for the information!

  28. This is really interesting, You are a very skilled blogger. I ave joined your feed and look forward to seeking more of your great post. Also, I have shared your website in my social networks!

  29. Wow! This blog looks exactly like my old one! It as on a completely different topic but it has pretty much the same layout and design. Excellent choice of colors!

  30. I will right away seize your rss as I can at find your e-mail subscription hyperlink or e-newsletter service. Do you ave any? Kindly let me know in order that I could subscribe. Thanks.

  31. Wow! This can be one particular of the most useful blogs We have ever arrive across on this subject. Actually Fantastic. I am also a specialist in this topic so I can understand your hard work.

  32. Sites we recommend Nice blog here! Also your site loads up very fast! What web host are you using? Can I get your affiliate link to your host? I wish my site loaded up as fast as yours lol

  33. Wow! This can be one particular of the most helpful blogs We ave ever arrive across on this subject. Basically Excellent. I am also a specialist in this topic so I can understand your hard work.

  34. Spot on with this write-up, I honestly believe this amazing site needs much more attention. I all probably be returning to see more, thanks for the information!

  35. Wow! This could be one particular of the most useful blogs We ave ever arrive across on this subject. Actually Great. I am also an expert in this topic therefore I can understand your effort.

  36. Your style is really unique in comparison to other people I ave read stuff from. Thanks for posting when you ave got the opportunity, Guess I will just bookmark this page.

  37. This is really interesting, You are a very skilled blogger. I ave joined your rss feed and look forward to seeking more of your great post. Also, I have shared your web site in my social networks!

  38. Wow, marvelous blog layout! How long have you been blogging for? you made blogging look easy. The overall look of your site is wonderful, as well as the content!. Thanks For Your article about sex.

  39. Im no pro, but I feel you just crafted an excellent point. You certainly understand what youre talking about, and I can really get behind that. Thanks for staying so upfront and so truthful.

  40. Wow, incredible blog layout! How long have you been blogging for? you made blogging look easy. The overall look of your web site is great, as well as the content!

  41. Wow, wonderful blog layout! How long have you been blogging for? you make blogging look easy. The overall look of your site is fantastic, let alone the content!. Thanks For Your article about sex.

  42. Ones blog is there one among a form, i be keen on the way you put in order the areas.:aаАа’б‚Т€ТšаЂаŒаАа’б‚Т€ТžаБТž-aаАа’б‚Т€ТšаЂаŒ?aаАа’б‚Т€ТšаЂаŒ?

  43. You can certainly see your expertise within the work you write. The world hopes for even more passionate writers such as you who are not afraid to say how they believe. At all times follow your heart.

  44. You are my aspiration, I possess few blogs and occasionally run out from brand . Follow your inclinations with due regard to the policeman round the corner. by W. Somerset Maugham.

  45. My brother recommended I might like this website. He was totally right. This post actually made my day. You cann at imagine just how much time I had spent for this information! Thanks!

  46. This web site is really a walk-through for all of the info you wanted about this and didnaаАа’б‚Т€ТšаЂаŒаАа’б‚Т€ТžаБТžt know who to ask. Glimpse here, and youaаАа’б‚Т€ТšаЂаŒаАа’б‚Т€ТžаБТžll definitely discover it.

  47. Good day! I could have sworn I’ve been to this site before but after reading through some of the post I realized it’s new to me. Nonetheless, I’m definitely delighted I found it and I’ll be book-marking and checking back frequently!|

  48. I’m really loving the theme/design of your web site.
    Do you ever run into any internet browser compatibility issues?
    A few of my blog visitors have complained about my site not working correctly in Explorer but looks great in Safari.
    Do you have any advice to help fix this issue?

  49. This is very interesting, You’re an overly professional blogger. I have joined your rss feed and sit up for in search of more of your wonderful post. Additionally, I’ve shared your site in my social networks|

  50. Hey There. I found your blog using msn. This is a very well written article.
    I will be sure to bookmark it and return to
    read more of your useful info. Thanks for the post.
    I will definitely return.

  51. Howdy! Do you know if they make any plugins to assist with SEO? I’m trying to get my blog to rank for some targeted keywords but I’m not seeing very good gains. If you know of any please share. Many thanks!|

THOÁT KHỎI BÌNH LUẬN

Please enter your comment!
Please enter your name here