Пузырьковая сортировка

Пузырьковая сортировка основана на методе перестановок. Ее смысл заключается в постоянном сравнении смежных элементов и, при необходимости, их перестановке.

Исходный массив	DCAB
1	ADCB
2	ABDC
3	ABCD

Пример 2. Пузырьковая сортировка (непараметризованная версия)

Обработчик нажатия кнопки Button1 – считывает строку из Edit1 и вызывает функцию пузырьковой сортировки.

void __fastcall TForm1::Button1Click(TObject *Sender)

{

char *str=Edit1->Text.Trim().c_str();

int n=Edit1->Text.Length();

str[n]=’\0’;

bubble(str,(int)strlen(str));

Edit2->Text=AnsiString(str);

}

//---------------------------------------------------------------------------

Функция пузырьковой сортировки для символьной строки

void bubble(char *item,int count)

{

register int i,j;

char t;

for(i=0;i<count;i++)

{

for(j=count-1;j>=i;--j)

{

if(item[j-1]>item[j])

{

t=item[j-1];

item[j-1]=item[j];

item[j]=t;

}

}

}

}

Н а рис.2 представлен вид окна программы, вызывающей функцию пузырьковой сортировки.

Рис.2. Вид окна программы пузырьковой сортировки

Сортировка методом отбора

При сортировке методом отбора алгоритм находит элемент с наименьшим значением и выполняет перестановку, меняя его местами с первым элементом массива. Затем из оставшихся n-1 элементов находится наименьший и осуществляется его перестановка со вторым элементом и так далее. Перестановки будут осуществляться до тех пор, пока не поменяются местами два последних элемента.

Исходный массив	DCAB
1	ACDB
2	ABDC
3	ABCD

Пример 3. Сортировка методом отбора.

void Select(char *item,int count); // Прототип функции

//---------------------------------------------------------------------------

void __fastcall TForm1::bSortClick(TObject *Sender)

{

char *str=Edit1->Text.Trim().c_str();

int n=Edit1->Text.Length();

str[n]=’\0’;

Select(str,(int)strlen(str)); // Вызов функции сортировки

Edit2->Text=AnsiString(str);

}

//---------------------------------------------------------------------------

void Select(char *item,int count) // Сортировка методом отбора

{

register int i,j,k;

int exchange;

char t;

for(i=0;i<count-1;i++)

{

exchange=0;

k=i;

t=item[i];

for(j=i+1;j<count;++j)

{

if(item[j]<t)

{

k=j;

t=item[j];

exchange=1;

}

}

if(exchange==1)

{

item[k]=item[i];

item[i]=t;

}

}

}

Сортировка методом вставки

На первом шаге выполняется сортировка двух первых элементов массива. Далее алгоритм ставит третий элемент в порядковую позицию, соответствующую его положению относительно первых двух элементов. Затем в этот список вставляется четвертый элемент, и т.д. Процесс продолжается до тех пор, пока все элементы массива не будут отсортированы.

Исходный массив	DCAB
1	CDAB
2	ACDB
3	ABCD

Пример 4. Сортировка методом вставки.

void InsertSort(char *str,int count); // Прототип функции сортировки

//---------------------------------------------------------------------------

void __fastcall TForm1::bSortClick(TObject *Sender)

{

char *str=Edit1->Text.Trim().c_str();

int n=Edit1->Text.Length();

str[n]=’\0’;

InsertSort(str,strlen(str)); // Вызов функции сортировки вставкой

Edit2->Text=AnsiString(str);

}

//---------------------------------------------------------------------------

void InsertSort(char *item,int count) // Определение функции сортировки

{

register int i,j;

char t;

for(i=0;i<count;++i)

{

t=item[i];

for(j=i-1;j>=0 && t<item[j];j--)

{

item[j+1]=item[j];

}

item[j+1]=t;

}

}