Задача 1. Да се дефинира процедура

int split (int a[], int n, int x)

която преподрежда елементите на масива a с n елемента така, че елементите, по-малки или равни на x да предхождат елементите, по-големи или равни на x. Функцията да връща индекса на първия елемент, по-голям от x.

Задачата може да се реши с два индекса i, j в масива, като първоначално единия сочи началото на масива, а другия - края. Индексите се "придвижват", докато i достигне елемент, по-голям от x, а j - елемент, по-малък от x или докато съвпаднат. Ако след поредното такова придвижване i и j все още не съвпадат, то разменяме местата на i-тия и j-тия елемент на масива и продължаваме с придвижването.

Задача 2. Да се дефинира функция

void shiftLeft (int a[], int i, int j)

която премества наляво с една позиция елементите на масива от i-тия до j-тия включително.

Задача 3. Да се реализира функцията

void quicksort (int a[], int n)

която сортира по метода на бързото сортиране масива a с n елемента.

Методът на бързото сортиране се базира на следната идея: Да "извадим" произволен елемент x от масива (за леснота можем да вземем a[0] и да работим с масива a+1). Да разделим масива a на две части, а1 и а2, като всички елементи в а1 са по-малки от x, а всички елементи в а2 са по-големи или равни на x. Да сортираме сега a1 и a2 рекурсивно и да образуваме масива a1xa2, който е сортиран.
На псевдокод алгоритъмът би могъл да изглежда така:

void quicksort (int a[], int n)
{

if (n==1)
    return;
int x = a[0];

//разделяме а+1 (тоест a с "изваден" a[0]) на две части -
//в лявата част са по-малките елементи от a[0], а в
//дясната - по-големите или равни

int div = split (a+1,n-1,x);

//сортираме двете парчета на a+1, като границата между
//тях се определя от div

quicksort (a+1,div);
quicksort (a+1+div,n-div-1);

//преместваме с една позиция наляво елементите на а, за
//да освободим място за x между двете части
shiftLeft(a,1,div);

//"вмъкваме" x между двете части
a[div] = x;
}


Последно модифициране: събота, 12 ноември 2011, 17:38