Как реализовать сортировку выбором в C?

Сортировка выбором — это еще один алгоритм, который работает, находя наименьшее целое число в массиве и затем присваивая ему верхнюю позицию. Индекс рядом с позицией наименьшего целого числа будет использоваться для начала следующего массива, который необходимо просмотреть.

Пример сортировки выбором в C

Если мы возьмем массив с числами [10,2,8,4,6], в котором наименьшее число равно 2. Таким образом, мы поместим наименьшее число, равное 2, на первую позицию, после чего массив будет выглядеть как [2,10,8,4,6]. Далее мы возьмем следующее наименьшее число, потому что 2 уже сейчас находится на своем правильном месте. Следующее наименьшее число — 4, которое будет помещено на вторую позицию, после чего массив будет перебираться аналогичным образом, пока не будет окончательно отсортирован.

Сортировка выбором в C сортирует числа в порядке возрастания. Изменив алгоритм, числа можно упорядочить по убыванию. Сортировка выбором также может выполняться на других языках, кроме C, например, сортировка выбором C++ или сортировка выбором Python.

Изучайте онлайн-курсы по разработке программного обеспечения в лучших университетах мира. Участвуйте в программах Executive PG, Advanced Certificate Programs или Master Programs, чтобы ускорить свою карьеру.

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

• Во-первых, мы устанавливаем начальный элемент в сортировке выбором как минимальный и ищем наименьший элемент в массиве для правильной процедуры Алгоритма сортировки выбором .
• Теперь минимальный элемент сравнивается со вторым компонентом. Если второй элемент упадет ниже минимального, мы поменяем их местами, а затем присвоим третьему элементу минимальное значение.
• В противном случае мы перейдем к третьему элементу и сравним его с минимальным. Если второй элемент превышает наш первый элемент, мы поменяем его местами. Повторите этот процесс до последнего компонента.
• После каждой итерации мы будем видеть, что наш минимум находится в начале несортированного списка.
• Мы начнем индексацию с первой записи несортированного списка для каждой итерации. Пока список не будет отсортирован или все компоненты не будут расположены надлежащим образом, мы будем повторять шаги с 1 по 4 несколько раз.

Популярные курсы и статьи по программной инженерии

Следующий пример с каждой итерацией поможет в деталях понять процесс сортировки выбором в C :

Итерация №1

I [ ] = 8,5,2,6,4

Установите минимум – 8

Сравните я 0 и я 1

Поскольку i 0 > i 1 , установите минимум = 5.

• Сравните я 1 и я 2

Так как i 1 > i 2 , установите минимум = 2.

• Сравните я 2 и я 3

Поскольку i 2 < i 3 , установите минимум = 2.

• Сравните я 2 и я 4

Так как i 2 < i 4 , установите минимум =2.

2 — наименьшее число всех элементов, мы должны поменять местами i 0 и i 2

­ Итерация №2

я [ ]= 2,5,8,6,4

Установите минимум 5

• Сравните я 1 и я 2

Так как i 1 < i 2 , установите минимум = 5.

• Сравните я 1 и я 3

Поскольку i 1 < i 3, установить минимум = 5

• Сравните я 1 и я 4

Опять же, i 1 < i 4 , установите минимум = 4.

4 — наименьший элемент в массиве, поэтому мы должны поменять местами i 1 и i 4 .

Итерация №3

я [ ]= 2,4,8,6,5

Установите минимум 8

• Сравните я 2 и я 3

Так как i 2 > i 3 , установите минимум = 6.

• Сравните я 3 и я 4

Поскольку i 3 > i 4 , установите минимум = 5.

5 — наименьший элемент в массиве, вы должны поменять местами i 2 и i 4 .

Итерация №4

I [ ] = 2,4,5,6,8

Установите минимум 6

• Сравните я 3 и я 4

Поскольку i 3 < i 4 , установите минимум = 6.

Минимум размещен в правильном месте; таким образом, подкачки не произойдет.

Пример сортировки выбором в C

// Сортировка выбором в C

#include <stdio.h>

// функция для замены двух элементов местами

недействительный обмен (int * a, int * b) {

интервал темп = * а;

*а = *б;

*б = температура;

}

void selectionSort (целый массив [], размер целого числа) {

for (int step = 0; step < size – 1; step++) {

int min_idx = шаг;

for (int i = step + 1; i < size; i++) {

// Для сортировки по убыванию измените > на < в этой строке.

// Выбираем минимальный элемент в каждом цикле.

если (массив [i] < массив [min_idx])

мин_idx = я;

}

// поместите min в правильную позицию

swap(&массив[min_idx], &массив[шаг]);

}

}

// функция для печати массива

void printArray (целый массив [], целочисленный размер) {

for (int я = 0; я < размер; ++ я) {

printf("%d", массив[i]);

}

printf("\n");

}

// код драйвера

интервал основной () {

целые данные [] = {20, 12, 10, 15, 2};

int size = sizeof (данные) / sizeof (данные [0]);

выборСортировка(данные, размер);

printf("Отсортированный массив в порядке возрастания:\n");

printArray (данные, размер);

}

Анализ сложности сортировки выбором

Вход – дано n входных элементов.

Выходные данные — количество шагов, необходимых для сортировки списка.

Логика . Если нам дано n элементов, будет выполнено n-1 сравнений на первом проходе, n-2 сравнений на втором проходе, n-3 сравнений на третьем проходе и так далее. Следовательно, общее количество сравнений может быть рассчитано с помощью;

Вывод -

(n+1) + (n+2) + (n+3) + (n+4) + …. +1

Сумма = n(n-1)/2, т.е. O(n²)

Поскольку методу сортировки выбором требуется некоторое дополнительное пространство памяти для временных переменных для замены, его временная сложность O(n2) и пространственная сложность O(1).

Анализ сложности времени сортировки выбора

Лучший случай: для ранее отсортированного массива метод сортировки выбором имеет наилучшую временную сложность O (n²).

Средний случай: Алгоритм сортировки выбором имеет среднюю временную сложность O (n²), когда элементы расположены в беспорядке, то есть ни в порядке возрастания, ни в порядке убывания.

Наихудший случай: когда мы меняем убывающий порядок массива на восходящий, временная сложность в наихудшем случае составляет O(n²).

Временная сложность метода сортировки выбором составляет O(n²) в каждом из трех сценариев. Это связано с тем, что мы должны определить минимальный набор элементов для каждого этапа, чтобы правильно их расположить. Проследив весь массив, мы найдем наш минимальный элемент.

Заключение

На этом запись в блоге «Сортировка выбором в C» подходит к концу. Вы должны понимать, что это может быть выполнено и на других языках, таких как сортировка выбором C++ и сортировка выбором Python. Мы надеемся, что эта статья поможет вам понять, как сортировать элементы в C.

Сортировка выбором — не единственный этап на пути становления программистом. Если вы надеетесь получить значительный импульс в своей карьере разработчика программного обеспечения с профессиональной степенью, upGrad здесь! UpGrad для разработки внешнего интерфейса (JavaScript, HTML, CSS), внутреннего интерфейса (NoSQL-MongoDB) и микросервисов, после чего вы можете пройти курс UpGrad Master of Science in Computer Science. Этот курс, предоставленный статусом выпускников IIIT Bangalore и LJMU, поможет вам построить карьеру инженера-программиста / разработчика полного стека в технологических гигантах по всему миру.

Этот курс охватывает базовые знания таких инструментов, как Java, Spring и Hibernate, укрепляя наши навыки разработки с полным стеком, чтобы исследовать рынок труда с замечательными возможностями.

Зарегистрируйтесь, чтобы узнать больше!