Cортировка массива

Вопросам сортировки массива посвящено немало статей в Интернете. Пожалуй, никакая другая проблема не породила такого количества разнообразнейших решений, как задача сортировки. Существует ли некий "универсальный", наилучший алгоритм ? Вообщем-то говоря, нет. Однако, имея приблизительные характеристики входных данных, можно подобрать метод, работающий оптимальным образом.

Алгоритмы сортировки

Квадратичные и субквадратичные алгоритмы :

Логарифмические и линейные алгоритмы :

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

Мы не будем останавливаться на сравнительном анализе различных алгоритмов. Желающие могут познакомиться более детально с первоисточниками по адресу http://algolist.manual.ru. На нашей странице мы представим реализации двух широко используемых алгоритмов : быстрая сортировка и сортировка пузырьком.

Алгоритм быстрой сортировки

Алгоритм быстрой сортировки является одним их самых эффективных алгоритмов. Метод основан на подходе "разделяй-и-властвуй". Общая схема такова: В конце получится полностью отсортированная последовательность.

Листинг примера реализации быстрой сортировки на Java
       
  import java.util.Random;
 
  public class QuickSort {
   public static int ARRAY_LENGTH = 50;
   private static int [] array = new int [ARRAY_LENGTH];
   private static Random generator = new Random ();
 
  public static void init () {
   for (int i=0; i<ARRAY_LENGTH; i++) {
    array [i] = generator.nextInt (1000);
   }
  }
  public static void printArray () {
   for ( int i=0; i<ARRAY_LENGTH-1; i++ ) {
    System.out.print ( array [i] + “, ”);
   }
   System.out.println ( array [ARRAY_LENGTH-1] );
  }
  public static void Sort () {
   int first = 0;
   int last = ARRAY_LENGTH - 1;
   QuickSorting ( first, last );
  }
  private static void Swap ( int i, int j ) {
   int temp = array[i];
   array[i] = array[j];
   array[j] = temp;
  }
  private static void QuickSorting ( int start, int end ) {
   if (start >= end)
    return;
   int i = start, j = end;
   int mid = (i + j) / 2;
   while (i < j) {
    while (( i < mid ) && ( array [i] <= array [mid] )) i++;
    while (( j > mid ) && ( array [mid] <= array [j] )) j--;
    if ( i < j ) {
     Swap ( i, j );
     if ( i == mid )
      mid = j;
     else if ( j == mid )
      mid = i;
    }
   }
   QuickSorting ( start, mid );
   QuickSorting ( mid+1, end );
  }
  public static void main ( String [] args ) {
   init ();
   printArray ();
   Sort ();
   printArray ();
  }
   
 

Алгоритм сортировки пузырьком

Алгоритм сортировки пузырьком заключается в том, что выполняется несколько проходов снизу вверх ( от последнего элемента к первому ). По пути просматриваются пары соседних элементов. Если элементы некоторой пары находятся в неправильном порядке, то они меняются местами. После первого прохода по массиву "вверху" оказывается самый "легкий" элемент - отсюда аналогия с пузырьком. Следующий проход выполняется до второго сверху элемента. Таким образом второй по величине элемент поднимается на правильную позицию.

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

Среднее число сравнений и обменов имеют квадратичный порядок роста. Отсюда можно заключить, что алгоритм пузырька очень медленен и малоэффективен. Тем не менее, у него есть громадный плюс: он прост и его можно по-всякому улучшать. Один из способов улучшения алгоритма сортировки пузырьком состоит в том, направление следующих один за другим проходов меняется. Получившийся алгоритм иногда называют "шейкер-сортировкой". В следующем листинге представлен алгоритм двунаправленной пузырьковой сортировки массива.

Листинг алгоритма сортировки пузырьком на Java
       
  private static Boolean compareElements (int idx)
  {
   if ( array [idx] > array [idx + 1] )
   {
    Swap ( idx, idx + 1 );
    return true;
   } else
    return false;
  }
  private static void BubbleSort ( int start, int end )
  {
   int j;
   int last = end + 1;
   int first = start - 1;
   while ( first < last )
   {
    first++;
    last--;
    boolean swapped = false;
    for ( j = first; j < last; j++ )
    {
     if ( compareElements ( j ))
      swapped = true;
    }
    if ( !swapped ) return;
    for ( j = last; --j >= first; )
    {
     if ( compareElements ( j ))
      swapped = true;
    }
    if ( !swapped ) return;
   }
  }
 

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

Rambler's Top100 Рейтинг@Mail.ru