Isih Pantas

Algoritma Isih Pantas

Isihan pantas ialah salah satu algoritma pengisihan yang paling terkenal, kerana ia dilaksanakan dalam beberapa bahasa pengaturcaraan di dalam perpustakaan standard. Mengapa algoritma ini sangat digunakan??
Oleh kerana kelajuannya, algoritma pengisihan pantas ialah salah satu algoritma pengisihan terpantas yang mempunyai kerumitan masa O(n * log n) di mana n ialah saiz tatasusunan dan log ialah asas logaritma 2.

Bagaimana ia berfungsi?

Konsep utama yang diperlukan untuk memahami algoritma isihan pantas, ialah strategi bahagi dan takluk.
Strategi pecah dan takluk ialah istilah ketenteraan yang terkenal, yang dahulunya bermaksud bahawa untuk menakluk sebuah negara besar anda harus menjadikan negara itu dahulu, berpecah, selalunya oleh konflik dalaman atau perang saudara, dan kemudian anda pergi dan meleret seluruh negara semasa mereka sibuk.
Ok, tetapi bagaimana konsep ini diterjemahkan kepada sains komputer? Bahagi dan takluk, dalam algoritma, bermakna dia menyelesaikan masalah dengan menyelesaikan masalah yang lebih kecil, ini agak serupa dengan konsep aruhan matematik, di mana, kita menubuhkan f(1), kemudian kita menubuhkan f(n) dan kemudian, kami menunjukkan bahawa f(n - 1) berfungsi, dengan melakukan ini, kami boleh membuktikan sesuatu konsep.
Bahagikan dan takluk masalah berfungsi dengan cara yang sama, mula-mula kita selesaikan masalah paling mudah, sering dipanggil kes asas, kemudian, kita rumuskan kes rekursif, dan, akhirnya, kita jadikan masalah itu, dipecahkan kepada masalah paling mudah, kerana mereka yang kita tahu bagaimana untuk menyelesaikannya.

Algoritma

Saya akan menunjukkan pelaksanaan dalam C, dan kemudian saya akan menerangkan baris demi baris cara ini berfungsi, kerana ia merupakan idea yang agak rumit.

#include <stdlib.h>
#include <stdio.h>
#include <stdint.h>

void _quick_sort(uint32_t *arr, size_t low, size_t high);
void quick_sort(uint32_t *arr, size_t size);

int32_t main(void)
{
    uint32_t list[] = {1, 4, 5, 10, 2, 9, 17, 100, 4, 2, 1000};

    // 11 is the number of elements list has
    // this is really usefull, because whenever we pass an array to a function, it decays as a pointer
    // due to this, if the function is in another translation layer it won't be able to know, so it can do the 
    // sizeof(list) / sizeof(list[1]) trick
    quick_sort(list, 11);

    for (size_t i = 0; i < 11; ++i)
    {
        printf("%u ", list[i]);
    }

    return EXIT_SUCCESS;
}

// Just a helper to have a cleaner interface
void quick_sort(uint32_t *arr, size_t size)
{
    // Note: here we are passing the high bound as the size - 1,
    // so in here we are having an inclusive range
    // this is important because it makes the algorithm slightly simpler
    // and it requires less -1's which usually causes a lot of off-by one mistakes
    _quick_sort(arr, 0, size - 1);
}

size_t partition(uint32_t *arr, size_t low, size_t high)
{
    // Partition is the operation that puts all the elements smaller than the pivot
    // We are picking the last element as the pivot always,
    // I guess we could be more clever and pick a random element
    // or the median of the first, middle and last elements
    // but this is just a simple example
    size_t pivot_index = high;
    uint32_t pivot = arr[pivot_index];

    // This is going to be the index of the pivot at the end
    // of the loop
    size_t i = low;
    for (size_t j = low; j <= high; ++j)
    {
        // If the current element is less than the pivot,
        // we swap it with the element at index i
        // and increment i,
        // doing this we will know exacyly where the pivot
        // should be placed after the iteration is done
        // because all the elements of index < i are less than the pivot
        // and all the elements of index > i are greater than the pivot
        // so we just need to swap the pivot with the element at index i
        if (arr[j] < pivot)
        {
            uint32_t temp = arr[j];
            arr[j] = arr[i];
            arr[i] = temp;

            ++i;
        }
    }

    // putting the pivot at the right spot, remember, it could've been anywhere
    arr[pivot_index] = arr[i];
    arr[i] = pivot;

    return i;
}

void _quick_sort(uint32_t *arr, size_t low, size_t high)
{
    // The main idea of this function, is to use a window, that has the bounds
    // [low, high] inclusive, so if the window has length 0, low = high
    // it means we reached our base case, and the list is already sorted
    // since an array without elements is always going to be sorted
    // I guess
    if (low >= high)
    {
        return;
    }

    // The pivot index is the index of the pivot element after partitioning,
    // so it means that the list is weakly sorted around the pivot,
    // (i.e. all elements to the left of the pivot are less than the pivot)
    // and all elements to the right are greater then
    size_t pivot_index = partition(arr, low, high);

    // Here we have a cool implementation detail
    // since pivot_index is a size_t, it is unsigned
    // and if we subtract 1 from an unsigned 0,
    // we get undefined behavior
    // This would happen, if the last element should be the first
    // in this case, no sorting is necessary, since there is nothing
    // before it
    if (pivot_index > 0)
    {
        // Sorting the left hand window
        // they have the bounds, [low, pivot_index - 1]
        // the -1 is so it is inclusive
        // because we now know the pivot is in the right spot
        _quick_sort(arr, low, pivot_index - 1);
    }

    // Same thing with before, now, we are sorting the right side of the window
    _quick_sort(arr, pivot_index + 1, high);
}

Jadi idea utama algoritma agak mudah, pecahkan pembahagian tatasusunan senarai kepada dua bahagian, satu di mana semua elemen lebih kecil daripada pangsi dan satu di mana semua elemen lebih besar daripada pangsi.
Kemudian, gunakan algoritma ini secara rekursif pada bahagian itu sendiri, sehingga bahagian itu tidak mempunyai unsur, dalam kes ini, kami boleh memastikan ia disusun dengan betul.

Terdapat nuansa penting dalam memilih pangsi dalam algoritma isihan pantas, jika kita memilih pangsi yang buruk, kita akan mengalami kerumitan yang teruk, kerana setiap kali kita membahagikan tatasusunan kepada dua tatasusunan, kita akan mendapat yang kecil tatasusunan, dalam kes ini, kita akan mempunyai n panggilan rekursif dan kita perlu berjalan n elemen, oleh itu jenis cepat mempunyai senario kes terburuk O(n*n), yang amat teruk, jadi kita perlu berhati-hati apabila memilih pangsi, satu pendekatan yang baik ialah memilih nombor rawak, dengan berbuat demikian, kami pasti akan mendapat kes tengah, iaitu O(n * log n), log n kerana dalam kes purata, kami akan berpecah tatasusunan menjadi dua tatasusunan yang mempunyai separuh elemen tatasusunan awal, dan memandangkan kita perlu melalui semua elemen, terdapat faktor n.

Atas ialah kandungan terperinci Isih Pantas. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!