1 Востаннє редагувалося Ярослав (12.03.2013 16:21:02)

Тема: Швидке сортування, запропоноване Хоаром в 1962р.

Вітаю всіх!
Намагаюсь зрозуміти принцип швидкого сортування, запропонованого Хоаром в 1962р., проте це виявилось не таким легким завданням. Є зображення і стаття в вікі, які пояснюють суть методу, проте важко зрозуміти все одно.
КіР приводять такий код на пояснення цього методу:

void qsort(int v[], int left, int right){
    int i, last;

    if(left>=right)
        return;

    swap(v, left, (left+right)/2);
    last = left;
    for(i = left+1; i<=right; i++)
        if(v[i] < v[left])
            swap(v, ++last, i);
    swap(v, left, last);
    qsort(v, left, last-1);
    qsort(v, last+1, right);
}

void swap(int v[], int i, int j){
    int temp;

    temp = v[i];
    v[i] = v[j];
    v[j] = temp;
}

Я спробував вирішити по ньому приклад на аркуші паперу, масив магічним способом відсортувався, але самого алгоритму я не зрозумів.
В гуглі є вдосталь англомовного матеріалу, але можливо хтось уже мав справу із такою задачею і зможе мені тут розказати що і до чого, бо на даний момент мені потрібно знати суто як працює цей алгоритм, а конкретно цей приклад.

Post's attachments

Sorting_quicksort_anim.gif 90.84 kb, 438 downloads since 2013-03-12 

2

Re: Швидке сортування, запропоноване Хоаром в 1962р.

Вибираємо елемент масиву, називається опорним. Немає значення як, можна брати останній, можна той що по середині. І сортуємо відносно нього, все що менше кидаємо вліво, все що більше дорівнює вправо. Після цього беремо ліву частину і повторяємо рекурсивно, потім праву.

3

Re: Швидке сортування, запропоноване Хоаром в 1962р.

Краще просто самому пройтись по коду і всі кроки малювати масив. Наприклад, на 5 елементів. Я завжди так робив і роблю коли не дуже розумію алгоритм. :)

Подякували: _-_MAIBA_-_2

4 Востаннє редагувалося muroclav (13.03.2013 16:20:35)

Re: Швидке сортування, запропоноване Хоаром в 1962р.

Мені в універі пояснювали так:
        Сортування починається з якого-небудь елемента, який зазвичай знаходиться посередині діапазону (між left і right, left – ліва, right – права межа діапазону сортування), його ще називають компарандом. Найкращим варіантом початкового елемента буде середньоарифметичне значення, тобто середнє між максимальним і мінімальним, які будуть крайніми в посортованому масиві і які, як правило, заздалегідь невідомі.
         Суть методу полягає в розділенні масиву на дві частини, після чого всі елементи, менші за компаранд, переміщуються (бульбашковим методом) вліво, а більші – вправо. Далі кожна з цих частин ділиться окремо, а елементи переміщуються тим же способом, поки весь масив не стане посортованим.

5

Re: Швидке сортування, запропоноване Хоаром в 1962р.

Vo_Vik написав:

Вибираємо елемент масиву, називається опорним. Немає значення як, можна брати останній, можна той що по середині. І сортуємо відносно нього, все що менше кидаємо вліво, все що більше дорівнює вправо.

Ось тут не радять брати в якості опорного елементу (англ. a pivot) перший елемент масиву, оскільки тоді алгоритм не буде ефективним, якщо на вході маємо попередньовідсортований масив.