Сортировка выбором.

Сортировка выбором (Selection sort) — Алгоритм сортировки. Может быть как устойчивый, так и неустойчивый. На массиве из n элементов имеет время выполнения в худшем, среднем и лучшем случае Θ$$(n^2)$$, предполагая что сравнения делаются за постоянное время.

Алгоритм:

1) Ищем порядковый номер минимального значения в не отсортированной части массива.

2) Меняем его с крайним не отсортированным значением, если крайнее но отсортированное значение является минимальным ничего не делаем.

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

Посмотрим алгоритм на примере:

Отсортируем массив: 524613 где каждая цифра это элемент массива.

Начало цикла, в массиве 524613 нет отсортированных чисел:

524613

1) Hаходим «1», это самое минимальное значение в массиве, и меняем с 5, это самое крайнее не отсортированное значение в массиве:

524613 -> |124653

2) 2 оказалась самым крайним не отсортированным значением, не меняем его положения

1|24653 -> 1|24653

3) Далее минимальным значением является 3, меняем её с 4.

12|4653-> 12|3654

3) Далее минимальным значением является 4, меняем её с 6.

123|654 -> 123|456

4) 5 оказалась самым крайним не отсортированным значением, не меняем его положения

123456 -> 1234|56

5) 6 оказалась самым крайним не отсортированным значением, не меняем его положения

123456 -> 12345|6

Реализация алгоритма на языке Паскаль:

program SelectionSort;

Const
  N=100;

procedure Swap(var X,Y:Real);
begin
  X:=X+Y;
  Y:=X-Y;
  X:=X-Y;
end;

Procedure Selection_Sort (var a : array of real; LengthArray :Integer);
var i,i2,Min_idx:integer;
begin
 for i:=0 to LengthArray-1 do
  begin
   Min_idx:=i;
   for i2:=i+1 to LengthArray-1 do
     if a[Min_idx]>a[i2] then Min_idx:=i2;

   if i<>Min_idx then Swap(a[i],a[Min_idx]);
  end;
end;

var
a,a1 : array [1..N] of real;
i: integer;

begin
 for i:=1 to N do a[i]:=Random(100);
 a1:=a;

 Selection_Sort(a1,N);


 for i:=1 to N do writeln(a[i]:7:0,'  ',a1[i]:7:0);
end.

program SelectionSort;

Const

N=100;

procedure Swap(var X,Y:Real);

begin

X:=X+Y;

Y:=X-Y;

X:=X-Y;

end;

Procedure Selection_Sort (var a : array of real; LengthArray :Integer);

var i,i2,Min_idx:integer;

begin

for i:=0 to LengthArray-1 do

begin

Min_idx:=i;

for i2:=i+1 to LengthArray-1 do

if a[Min_idx]>a[i2] then Min_idx:=i2;

if i<>Min_idx then Swap(a[i],a[Min_idx]);

end;

var

a,a1 : array [1..N] of real;

i: integer;

begin

for i:=1 to N do a[i]:=Random(100);

a1:=a;

Selection_Sort(a1,N);

for i:=1 to N do writeln(a[i]:7:0,' ',a1[i]:7:0);

end.

Реализация алгоритма на языке C++:

#include "stdafx.h"
#include <iostream>
using std::cout;
using std::cin;
using std::endl;

const int n = 100;

void Swap(int &x,int &y)
{
	x = x + y;
	y = x - y;
	x = x - y;
}

void Selection_Sort(int *a, int LeanghtArray)
{
	int Min_idx;
	for (int i = 1; i < LeanghtArray; ++i){
		Min_idx = i;
		for (int i2 = i + 1; i2 < LeanghtArray; ++i2){
			if (a[Min_idx] > a[i2]){ 
				Min_idx = i2; 
			}
		}
		if (i != Min_idx) { 
			Swap(a[i], a[Min_idx]);}
	}
}


int _tmain(int argc, _TCHAR* argv[])
{
	int a[n], a1[n], i, i2;
	for (int i = 1; i < n; i++){ a[i] = rand(); a1[i] = a[i]; }
	
	Selection_Sort(a, n);
	
	for (int i = 1; i < n; i++){ cout << a[i] <<" "<<a1[i]<<endl; }
	cin >> i;
	return 0;
}

#include "stdafx.h"

#include <iostream>

using std::cout;

using std::cin;

using std::endl;

const int n = 100;

void Swap(int &x,int &y)

{

x = x + y;

y = x - y;

x = x - y;

}

void Selection_Sort(int *a, int LeanghtArray)

{

int Min_idx;

for (int i = 1; i < LeanghtArray; ++i){

Min_idx = i;

for (int i2 = i + 1; i2 < LeanghtArray; ++i2){

if (a[Min_idx] > a[i2]){

Min_idx = i2;

}

if (i != Min_idx) {

Swap(a[i], a[Min_idx]);}

}

int _tmain(int argc, _TCHAR* argv[])

{

int a[n], a1[n], i, i2;

for (int i = 1; i < n; i++){ a[i] = rand(); a1[i] = a[i]; }

Selection_Sort(a, n);

for (int i = 1; i < n; i++){ cout << a[i] <<" "<<a1[i]<<endl; }

cin >> i;

return 0;

}

Сортировка выбором.

Алгоритм:

Посмотрим алгоритм на примере:

Реализация алгоритма на языке Паскаль:

Реализация алгоритма на языке C++:

Комментарии:

Добавить комментарий Отменить ответ