Рубрики

Сравнение между Bubble Sort, Selection Sort и Inorttion Sort

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

Пузырьковая сортировка многократно сравнивает и меняет (при необходимости) смежные элементы на каждом проходе. На i-м проходе Bubble Sort (в порядке возрастания) последние (i-1) элементы уже отсортированы , и i-й по величине элемент помещается в (Ni) -ю позицию, то есть i-ю последнюю позицию.

Алгоритм:

BubbleSort (Arr, N) // Arr is an array of size N.
{
    For ( I:= 1 to (N-1) ) // N elements => (N-1) pass
    {
    // Swap adjacent elements of Arr[1:(N-I)]such that
    // largest among { Arr[1], Arr[2], ..., Arr[N-I] } reaches to Arr[N-I]
        For ( J:= 1 to  (N-I) ) // Execute the pass
        {
            If ( Arr [J] > Arr[J+1] ) 
                Swap( Arr[j], Arr[J+1] );
        }
    }
}

Оптимизация алгоритма : проверьте, произошла ли какая-либо операция обмена во внутреннем цикле (проходной цикл выполнения) или нет. Если в любом проходе нет перестановки, это означает, что массив теперь полностью отсортирован, поэтому нет необходимости продолжать, останавливать операцию сортировки. Таким образом, мы можем оптимизировать количество проходов, когда массив сортируется до завершения всех проходов. И он также может определить, отсортирован ли данный / входной массив или нет, на первом проходе.

BubbleSort (Arr, N) // Arr is an array of size N.
{
    For ( I:= 1 to (N-1) ) // N elements => (N-1) pass
    {
    // Swap adjacent elements of Arr[1:(N-I)]such that
    // largest among { Arr[1], Arr[2], ..., Arr[N-I] } reaches to Arr[N-I]
        noSwap = true; // Check occurrence of swapping in inner loop
        For ( J:= 1 to  (N-I) ) // Execute the pass
        {
            If ( Arr [J] > Arr[J+1] )
            { 
                Swap( Arr[j], Arr[J+1] );
                noSwap = false;
            }
        }
        If (noSwap) // exit the loop
            break;
    }
}

Сложность времени :

  • Лучший случай Сортированный массив в качестве входных данных. Или почти все элементы находятся на своем месте. [ O (N) ]. O (1) свопы.
  • В худшем случае : обратная сортировка / очень мало элементов в нужном месте. [ O (N 2 ) ]. O (N 2 ) свопы.
  • Средний случай : [ O (N 2 ) ]. O (N 2 ) свопы.

Сложность пространства : временная переменная используется в обмене [вспомогательный, O (1) ]. Следовательно, это сортировка по месту.

Преимущество :

  1. Это самый простой подход к сортировке.
  2. Наилучшая сложность — O (N) [для оптимизированного подхода], в то время как массив сортируется.
  3. Используя оптимизированный подход , он может обнаружить уже отсортированный массив при первом проходе с временной сложностью O (1) .
  4. Стабильная сортировка: не меняет относительный порядок элементов с равными ключами.
  5. Сортировка по месту.

Недостаток :

  1. Пузырьковая сортировка — сравнительно медленный алгоритм.

2. Выбор сортировки

Сортировка выбора выделяет i-й наименьший элемент и помещает его в i-ю позицию. Этот алгоритм делит массив на две части: отсортированный (слева) и несортированный (справа) подмассив. Он выбирает наименьший элемент из несортированного подмассива и помещает в первую позицию этого подмассива (в порядке возрастания). Он многократно выбирает следующий наименьший элемент.

Алгоритм :

SelectionSort (Arr, N) // Arr is an array of size N.
{
    For ( I:= 1 to (N-1) ) // N elements => (N-1) pass
    {
    // I=N is ignored, Arr[N] is already at proper place.
    // Arr[1:(I-1)] is sorted subarray, Arr[I:N] is undorted subarray
    // smallest among { Arr[I], Arr[I+1], Arr[I+2], ..., Arr[N] } is at place min_index
        
        min_index = I;
        For ( J:= I+1 to N ) // Search Unsorted Subarray (Right lalf)
        {
            If ( Arr [J] < Arr[min_index] ) 
                min_index = J; // Current minimum
        }
        Swap ( Arr[I], Arr[min_index] ); 
        // Swap I-th smallest element with current I-th place element
    }
}

Сложность времени :

  • Лучший случай [ O (N 2 ) ]. Также O (N) свопы.
  • В худшем случае : обратная сортировка, и когда внутренний цикл делает максимальное сравнение. [ O (N 2 ) ]. Также O (N) свопы.
  • Средний случай : [ O (N 2 ) ]. Также O (N) свопы.

Сложность пространства : [вспомогательный, O (1) ]. Сортировка по месту.

Преимущество :

  1. Его также можно использовать в структурах списков, которые делают добавление и удаление эффективными, таких как связанный список. Просто удалите наименьший элемент несортированной части и конец в конце отсортированной части.
  2. Наилучшая сложность — O (N), а массив уже отсортирован.
  3. Количество свопов уменьшено. O (N) поменяется во всех случаях.
  4. Сортировка по месту.

Недостаток :

  1. Временная сложность во всех случаях составляет O (N 2 ) , не лучший вариант развития событий.

3. Вставка сортировки

Вставка сортировки — это простой алгоритм сортировки, основанный на сравнении. Он вставляет каждый элемент массива в правильную позицию. В i-й итерации предыдущие (i-1) элементы (т.е. подмассив Arr [1: (i-1)]) уже отсортированы, и i-й элемент (Arr [i]) вставляется на свое место в ранее отсортированный подмассив.
Найти более подробную информацию в этой ссылке GFG .

Алгоритм :

InsertionSort (Arr, N) // Arr is an array of size N.
{
    For ( I:= 2 to N ) // N elements => (N-1) pass
    {
    // Pass 1 is trivially sorted, hence not considered
    // Subarray { Arr[1], Arr[2], ..., Arr[I-I] } is already sorted
        
        insert_at = I; // Find suitable position insert_at, for Arr[I]
        // Move subarray Arr [ insert_at: I-1 ] to one position right

        item = Arr[I]; J=I-1;
        While ( J ≥ 1 && item < Arr[J] ) 
        {
                Arr[J+1] = Arr[J]; // Move to right   
                // insert_at = J;
                J--;
            }
            insert_at = J+1; // Insert at proper position
            Arr[insert_at] = item; // Arr[J+1] = item;
        }
    }
}

Сложность времени :

  • В качестве входного значения отсортирован массив, [ O (N) ]. И O (1) поменяется.
  • В худшем случае : обратная сортировка, и когда внутренний цикл делает максимальное сравнение, [ O (N 2 ) ]. И O (N 2 ) поменяется.
  • Средний случай : [ O (N 2 ) ]. И O (N 2 ) поменяется.

Сложность пространства : [вспомогательный, O (1) ]. Сортировка по месту.

Преимущество :

  1. Это может быть легко вычислено.
  2. Наилучшая сложность — O (N), а массив уже отсортирован.
  3. Количество свопов меньше, чем у пузырьковых.
  4. Для меньших значений N сортировка вставкой работает эффективно, как и другие алгоритмы квадратичной сортировки.
  5. Стабильный сорт.
  6. Адаптивный: общее количество шагов уменьшается для частично отсортированного массива.
  7. Сортировка по месту.

Недостаток :

  1. Обычно используется, когда значение N мало. Для больших значений N это неэффективно .

Пространственно-временная сложность:

Sorting AlgorithmTime ComplexitySpace Complexity
Best CaseAverage CaseWorst CaseWorst Case
Bubble SortO(N)O(N2)O(N2)O(1)
Selection SortO(N2)O(N2)O(N2)O(1)
Insertion SortO(N)O(N2)O(N2)O(1)

Рекомендуемые посты:

Сравнение между Bubble Sort, Selection Sort и Inorttion Sort

0.00 (0%) 0 votes