Сортировка, пирамидальная сортировка. Параметры задачи: размер последовательности, длина строки. Мера сравнения: число обменов, число сравнений, Время выполнения.

Упорядочивание строковой (char*) последовательности. Алгоритмы: шейкерная

Сортировка, пирамидальная сортировка. Параметры задачи: размер

последовательности, длина строки. Мера сравнения: число обменов, число сравнений,

Время выполнения.

Пирамидальная сортировка

Пирамидальная сортировка (англ. Heapsort, «Сортировка кучей»[1]) — алгоритм сортировки, работающий в худшем, в среднем и в лучшем случае (то есть… Может рассматриваться как усовершенствованная сортировка пузырьком, в которой… Сортировка пирамидой использует сортирующее дерево. Сортирующее дерево — это такое дерево, у которого выполнены…

Пример

def heapsort(s):

sl = len(s)

def swap(pi, ci):

if s[pi] < s[ci]:

s[pi], s[ci] = s[ci], s[pi]

def sift(pi, unsorted):

I_gt = lambda a, b: a if s[a] > s[b] else b

while pi*2+1 < unsorted:

Gtci = i_gt(pi*2+1, pi*2+2) if pi*2+2 < unsorted else pi*2+1

swap(pi, gtci)

Pi = gtci

Heapify

for i in range((sl/2)-1, -1, -1):

sift(i, sl)

Sort

for i in range(sl-1, 0, -1):

swap(i, 0)

sift(0, i)

static void HeapSort(int[] a)

{

int i;

int temp;

for (i = (a.Length / 2) - 1; i >= 0; i--)

{

siftDown(a, i, a.Length);

}

for (i = a.Length - 1; i >= 1; i--)

{

temp = a[0];

a[0] = a[i];

a[i] = temp;

siftDown(a, 0, i - 1);

}

}

static void siftDown(int[] a, int i, int j)

{

bool done = false;

int maxChild;

int temp;

while ((i * 2 < j) && (!done))

{

if (i * 2 == j)

maxChild = i * 2;

else if (a[i * 2] > a[i * 2 + 1])

maxChild = i * 2;

Else

maxChild = i * 2 + 1;

if (a[i] < a[maxChild])

{

temp = a[i];

a[i] = a[maxChild];

a[maxChild] = temp;

i = maxChild;

}

Else

{

done = true;

}

}

}

Идея ал­го­рит­ма

Для то­го, что­бы про­яс­нить всё даль­ней­шее из­ло­же­ние, в двух сло­вах опи­шу идею ал­го­рит­ма.

Пи­ра­ми­да — дво­ич­ное де­ре­во, в ко­то­ром зна­че­ние каж­до­го эле­мен­та боль­ше ли­бо рав­но зна­че­ний до­чер­них эле­мен­тов.

За­пол­нив де­ре­во эле­мен­та­ми в про­из­воль­ном по­ряд­ке, мож­но лег­ко его от­сор­ти­ро­вать (лег­че, чем ис­ход­ный спи­сок эле­мен­тов), пре­вра­тив в пи­ра­ми­ду.

Са­мый боль­шой эле­мент пи­ра­ми­ды на­хо­дит­ся в её вер­ши­не.

От­де­ля­ем вер­шин­ный эле­мент, и за­пи­сы­ва­ем его в ко­нец ре­зуль­ти­рую­ще­го мас­си­ва.

На ме­сто вер­шин­но­го эле­мен­та за­пи­сы­ва­ем эле­мент из са­мо­го ниж­не­го уров­ня де­ре­ва.

Вос­ста­нав­ли­ва­ем (пе­ре­сор­ти­ро­вы­ва­ем) пи­ра­ми­ду.

Са­мый боль­шой эле­мент из остав­ших­ся сно­ва в вер­ши­не. Сно­ва от­де­ля­ем его и за­пи­сы­ва­ем его в ка­че­стве пред­по­след­не­го эле­мен­та ре­зуль­та­та, и так да­лее...

Весь фо­кус ал­го­рит­ма в том, что пи­ра­ми­да без до­пол­ни­тель­ных за­трат хра­нит­ся пря­мо в ис­ход­ном мас­си­ве. По ме­ре то­го, как раз­мер пи­ра­ми­ды умень­ша­ет­ся, она за­ни­ма­ет всё мень­шую часть мас­си­ва, а ре­зуль­тат сор­ти­ров­ки за­пи­сы­ва­ет­ся на­чи­ная с кон­ца мас­си­ва на осво­бо­див­шие­ся от пи­ра­ми­ды ме­ста.

Ещё од­но объ­яс­не­ние идеи ал­го­рит­ма мо­же­те посмот­реть в этом ком­мен­та­рии.

Дво­ич­ное де­ре­во

Дво­ич­ное де­ре­во — ст­рук­ту­ра дан­ных, в ко­то­рой каж­дый эле­мент име­ет ле­во­го и/или пра­во­го по­том­ка, ли­бо во­об­ще не име­ет по­том­ков. В по­след­нем слу­чае эле­мент на­зы­ва­ет­ся ли­сто­вым.

Ес­ли эле­мент A име­ет по­том­ка B, то эле­мент A на­зы­ва­ет­ся ро­ди­те­лем эле­мен­та B. В дво­ич­ном де­ре­ве су­ще­ству­ет един­ствен­ный эле­мент, ко­то­рый не име­ет ро­ди­те­лей; та­кой эле­мент на­зы­ва­ет­ся кор­не­вым.

Шейкерная сортировка

{ int first = 0; int last = n;

Pragma hdrstop

Pragma argsused

Шейкер-сортировка

int main(int argc, TCHAR* argv[])

{

const int Count = 10;

int TestArr[Count] = {3, 1, 5, 8, 1, 0, 6, 4, 6, 7};

ShakerSort(TestArr,1,Count);

ArrayOutput(TestArr,0,Count);

return 0;

}

Поменять местами i-й и i-1-й элементы массива Arr

void Swap(int Arr[], int i)

{

Int temp; //буфер

temp = Arr[i];

Arr[i] = Arr[i - 1];

Arr[i - 1] = temp;

}

void ShakerSort(int Arr[], int Start, int N)

{

Int Left, Right; //границы сортировки

Left = Start;

Right = N - 1;

Do

{

//Сдвигаем к началу массива "легкие элементы"

for (int i = Right; i >= Left; i--)

{

if (Arr[i - 1]>Arr[i])

{

Swap(Arr, i);

}

}

Left = Left + 1;

//Сдвигаем к концу массива "тяжелые элементы"

for (int i = Left; i <= Right; i++)

{

if (Arr[i - 1] > Arr[i])

{

Swap(Arr, i);

}

}

Right = Right - 1;

}

while (Left <= Right);

}

Вывод элементов массива на консоль

{ for (int i = Start; i < N; i++) {