Сравнение пузырьковой сортировки с сортировкой выбором
Сортировка означает группировку или расположение большого количества объектов в соответствующем порядке. Вы знаете тот момент, когда вы ищете подходящую пару носков? Это сортировка. В этой статье мы обсудим различия между пузырьковой сортировкой и сортировкой выбором.
Предпосылки
- Обозначение большого O
- Javascript для цикла
Пузырьковая сортировка
Основной принцип пузырьковой сортировки заключается в том, что она сравнивает два элемента, и если первый элемент больше второго, мы меняем местами эти два элемента или оставляем их и переходим к следующей итерации. Взгляните на это полезное визуальное представление того, что происходит во время работы алгоритма:
Я подробно объясню пузырьковую сортировку на изображении ниже.
Массив на изображении выше не отсортирован. Он состоит из 8 целых чисел, то есть 6,5,3,1,8,7,2,4.
Шаги, необходимые для сортировки массива, следующие:
ПРОШЕЛ 1
Шаг 1. Сначала мы сравниваем элемент [0] с элементом [1]. a[0] больше, чем a[1], то есть 6>5, поэтому мы меняем местами элементы.
Шаг 2. На этом шаге a[1] будет сравниваться с a[2]. Обратите внимание, что a[1] больше, чем a[2], то есть 6>3, и мы снова меняем местами элементы.
Шаг 3: a[2] будет сравниваться с a[3]. Обратите внимание, что 6>1, т. е. a[2] больше, чем a[3], поэтому мы меняем элементы местами.
Шаг 4. На этом шаге a[3] будет сравниваться с a[4]. Обратите внимание, что a[3] меньше, чем a[4], поэтому мы оставляем их и переходим к следующей итерации, поскольку они расположены в правильном порядке.
Шаг 5. На этом шаге a[4] будет сравниваться с a[5]. Обратите внимание, что a[4] больше, чем a[5], то есть 8×7, поэтому мы меняем местами элементы.
Шаг 6: сравним a[5] с a[6]. Обратите внимание, что a[5] больше, чем a[6], то есть 8×2, поэтому мы меняем местами элементы.
Шаг 7. На этом шаге a[6] будет сравниваться с a[7]. Обратите внимание, что a[6] больше, чем a[7], поэтому мы меняем местами элементы.
В конце прохода 1 мы получили массив ниже.
Проход 2: мы должны начать сравнивать элементы с первой позиции, т. е. a[0] будет сравниваться с a[1]. Мы повторяем процесс, пока массив не будет отсортирован.
Реализация алгоритма пузырьковой сортировки
function bubbleSort(arr){
for(let i=0; i< arr.length-1; i++){
for(let j=0; j<arr.length-1; j++){
if(arr[j]>arr[j+1]){
arr[j],arr[j+1]=arr[j+1], arr[j]
}
}
}
}
Сортировка выбором
Сортировка выбором непрерывно выбирает следующий наименьший элемент и меняет его местами. Предполагая, что у нас есть несортированный массив, чтобы отсортировать этот массив в порядке возрастания, на каждой итерации мы должны выбрать наименьший элемент из несортированного раздела и переместить его в отсортированный раздел. Мы будем отслеживать текущий элемент и текущий минимум с помощью красных и зеленых стрелок.
Шаг 1
Красная стрелка отслеживает текущее минимальное число. Зеленая стрелка представляет наш текущий элемент, когда мы перебираем массив, находим 1, устанавливаем его как текущий минимум и меняем местами 1 и 2. Наш новый массив выглядит так: диаграмма ниже.
Шаг 2
На этом шаге мы устанавливаем 5 в качестве нашего текущего минимума и текущего элемента с помощью зеленой и красной стрелок. мы снова сканируем массив, используя зеленую стрелку, чтобы проверить меньшее число. Теперь мы нашли 2 и меняем местами 5 и 2.
Наш новый массив выглядит так, как показано на диаграмме ниже.
Шаг 3
На этом шаге мы устанавливаем наш текущий минимум равным 3, а текущий элемент — равным 3, когда мы сканируем массив. Обратите внимание, что в правой части массива нет числа меньше 3. Таким образом, здесь не происходит подкачки.
Шаг 4
В этой итерации наш текущий минимум установлен на 4, а текущий элемент на 4, когда мы сканируем массив. Обратите внимание, что в правой части массива нет числа меньше 4. Никакого обмена здесь не происходит.
Шаг 5
На этом шаге мы устанавливаем текущий минимум равным 5, а текущий элемент — 5. В правой части массива нет других элементов. Итак, мы возвращаем 5
Реализация алгоритма сортировки выбором
for(let i=0; i<arr.length; i++){
let min=i;
for(let i+1; j<arr.length; j++){
if(arr[j]<arr[min]){
min=j
}
}
[ arr[i],arr[min]]=arr[min, arr[i]]
}
Различия между сортировкой пузырьком и сортировкой выбором
Заключение
Таким образом, основное различие между пузырьковой сортировкой и сортировкой выбором заключается в том, что пузырьковая сортировка сравнивает два элемента и постоянно меняет местами соседние элементы, если они находятся в неправильном порядке. Напротив, сортировка выбором сортирует массив, многократно находя минимальный элемент из несортированной части и вставляя его в начало массива.
