:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте ::
Путь: Сортировка » FAQ » Вопрос 3
На правах рекламы
Только для вас металлобазы на выгоднейших условиях.
  Вопрос 3





====================================================================
> 3. Сортировка выбором.
====================================================================
   
     A[1..N] -  сортируемый массив из n элементов.

     for ( i=1; i<N; i++)
          Hайти наименьший из элементов i..N и поменять его местами с i-м.

     Пример действий для случайного массива A[1..8]        
      
          44  55  12  42  94  18  06  67      исходный массив
     i=1  06| 55  12  42  94  18  44  67       06 <-> 44
     i=2  06  12| 55  42  94  18  44  67       12 <-> 55
     i=3  06  12  18| 42  94  55  44  67       18 <-> 55
     i=4  06  12  18  42| 94  55  44  67       42 <-> 42
     i=5  06  12  18  42  44| 55  94  67       44 <-> 94
     i=6  06  12  18  42  44  55| 94  67       55 <-> 55
     i=7  06  12  18  42  44  55  67| 94       67 <-> 94

       Вертикальной чертой отмечена граница уже отсортированной части
     массива. 

     Сортировка выбором - простейший алгоритм, на практике не 
   используемый ввиду низкого быстродействия. Вместо этого 
   применяют ее улучшение - пирамидальную сортировку (Heapsort),
   описанную в другом вопросе, а также (иногда) 'древесную сортировку'
   (TreeSort). 
   
        Пример на Паскале - Hиколас Вирт.
--------------------------------------------------------------------   
 { Сортируются записи типа item по ключу item.key }
 { для вспомогательных переменных используется тип index }
 
 procedure SelectSort;
     var i, j, k: index; x:item;
 begin for i:=1 to n-1 do
     begin k:=i; x:=a[i];
	     for j:=i+1 to n do
		     if a[j].key < x.key then
			 begin k:=j; x:=a[j];
			 end;
		 a[k]:=a[i]; a[i]:=x;
	 end;
 end;