Сортировки Flashcards
Что такое сортировка обменом?
Это алгоритм сортировки, который проходит по массиву и сравнивает каждую пару соседних элементов. Если они находятся в неправильном порядке, то меняются местами. Этот процесс повторяется до тех пор, пока все элементы не будут отсортированы
Какие существуют сортировки обменом?
Сортировки обменом:
1. Сортировка пузырьком
2. Шейкерная сортировка
3. Гномья сортировка
Что такое сортировка пузырьком?
Самый простой алгоритм обменной сортировки, который работает за время O(n^2).
Алгоритм сортировки пузырьком работает следующим образом:
- Проходим по массиву с начала до конца.
- Сравниваем два соседних элемента.
- Если они находятся в неправильном порядке, то меняем их местами.
- Продолжаем проходить по массиву до тех пор, пока не будет отсортирован весь массив.
Пример кода на C++ для сортировки пузырьком:
void bubbleSort(int arr[], int n) {
for (int i = 0; i < n-1; i++) {
for (int j = 0; j < n-i-1; j++) {
if (arr[j] > arr[j+1]) {
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
Что такое шейкерная сортировка?
Улучшенный вариант сортировки пузырьком.
Алгоритм:
- Проходим по массиву с начала до конца и находим максимальный элемент.
- Проходим по массиву с конца до начала и находим минимальный элемент.
- Меняем местами максимальный элемент и последний элемент в массиве.
- Меняем местами минимальный элемент и первый элемент в массиве.
- Продолжаем проходить по массиву до тех пор, пока не будет отсортирован весь массив.
Пример кода на C++ для шейкерной сортировки:
void cocktailSort(int arr[], int n) {
bool swapped = true;
int start = 0;
int end = n - 1;
while (swapped) {
swapped = false;
for (int i = start; i < end; i++) {
if (arr[i] > arr[i+1]) {
swap(arr[i], arr[i+1]);
swapped = true;
}
}
if (!swapped) break;
swapped = false;
end--;
for (int i = end-1; i >= start; i--) {
if (arr[i] > arr[i+1]) {
swap(arr[i], arr[i+1]);
swapped = true;
}
}
start++; } }
Что такое гномья сортировка?
Алгоритм, который перемещает элементы только на одну позицию за раз, что делает его несколько менее эффективным, чем сортировка пузырьком.
Алгоритм гномьей сортировки работает следующим образом:
- Начинаем с первого элемента в массиве.
- Если следующий элемент меньше или равен текущему, то перемещаемся на следующий элемент.
- Если следующий элемент больше текущего, то меняем их местами и перемещаемся на предыдущий элемент.
- Продолжаем проходить по массиву до тех пор, пока не будет отсортирован весь массив.
Пример кода на C++ для гномьей сортировки:
void gnomeSort(int arr[], int n) {
int i = 0;
while (i < n) {
if (i == 0 || arr[i] >= arr[i-1]) {
i++;
} else {
swap(arr[i], arr[i-1]);
i–;
}
}
}
Что такое сортировка вставками?
Сортировка вставками — алгоритм сортировки, который проходит по массиву и вставляет каждый элемент в правильную позицию относительно уже отсортированных элементов. Этот процесс выполняется до тех пор, пока все элементы не будут отсортированы
Какие основные алгоритмы сортировки вставками?
Алгоритмы:
1) Простая сортировка вставками;
2) Бинарная сортировка вставками;
3) Сортировка Шелла.
Что такое простая сортировка вставками?
Простая сортировка вставками - самый простой алгоритм сортировки вставками, который работает за O(n^2) времени.
Сортировка вставками работает следующим образом:
1. Проходим по массиву и для каждого элемента находим правильную позицию в уже отсортированной части массива.
2. Вставляем элемент на правильную позицию и сдвигаем остальные элементы, если это необходимо.
3. Продолжаем проходить по массиву до тех пор, пока не будет отсортирован весь массив.
Пример кода на C++ для простой сортировки вставками:
void insertionSort(int arr[], int n) {
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j+1] = arr[j];
j--;
}
arr[j+1] = key; } }
Что такое бинарная сортировка вставками?
Улучшенный вариант сортировки вставками, который использует бинарный поиск для поиска правильной позиции для каждого элемента. Это позволяет уменьшить время работы до O (n log n).
Работает так же как простая сортировка вставками, однако вместо линейного поиска используется бинарный.
Пример кода на C++ для бинарной сортировки вставками:
void binaryInsertionSort(int arr[], int n) {
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
int pos = binarySearch(arr, key, 0, j);
while (j >= pos) {
arr[j+1] = arr[j];
j--;
}
arr[pos] = key; } }
int binarySearch(int arr[], int key, int left, int right) {
if (right <= left) return (key > arr[left]) ? (left + 1) : left;
int mid = (left + right) / 2;
if (key == arr[mid]) return mid + 1;
if (key > arr[mid]) return binarySearch(arr, key, mid+1, right);
return binarySearch(arr, key, left, mid-1);
}
Что такое сортировка Шелла?
Алгоритм, который использует различные интервалы для сравнения и вставки элементов, что делает его более эффективным, чем простая сортировка вставками.
Сортировка Шелла работает следующим образом:
1. Выбираем шаг (gap) равный n/2, где n - количество элементов в массиве.
2. Для каждого шага выполняем сортировку вставками для подмассивов, начинающихся с элементов, отстоящих на расстоянии gap друг от друга.
3. Уменьшаем шаг в два раза и повторяем шаги 2-3 до тех пор, пока шаг не станет равным 1.
4. Выполняем сортировку вставками для всего массива.
Сортировка Шелла основана на идее предварительной сортировки подмассивов, что позволяет ускорить сортировку для больших массивов.
Пример кода на C++ для сортировки Шелла:
void shellSort(int arr[], int n) {
for (int gap = n/2; gap > 0; gap /= 2) {
for (int i = gap; i < n; i++) {
int temp = arr[i];
int j;
for (j = i; j >= gap && arr[j-gap] > temp; j -= gap) {
arr[j] = arr[j-gap];
}
arr[j] = temp;
} } }
Что такое сортировка выбором?
Алгоритм сортировки, который проходит по массиву и находит наименьший элемент. Затем он меняет его местами с первым элементом в массиве. Этот процесс повторяется для каждой последующей позиции в массиве.
Какие основные алгоритмы сортировки выбором?
Алгоритмы:
1) Простая сортировка выбором;
2) Сортировка кучей;
3) Сортировка Шелла с выбором.
Что такое простая сортировка выбором?
Самый простой алгоритм сортировки выбором, который работает за O(n^2) времени.
Простая сортировка выбором работает следующим образом:
1. Проходим по массиву и для каждого элемента находим наименьший элемент, находящийся правее текущего элемента.
2. Обмениваем текущий элемент с наименьшим элементом.
3. Продолжаем проходить по массиву до тех пор, пока не будет отсортирован весь массив.
void selectionSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
if (minIndex != i) {
swap(arr[i], arr[minIndex]);
}
}
}
Что такое сортировка кучей?
Улучшенный вариант сортировки выбором, который использует структуру данных куча для быстрого поиска наименьшего элемента. Это позволяет уменьшить время работы до O (n log n).
Сортировка кучей работает следующим образом:
1. Строим кучу из массива.
2. Извлекаем минимальный элемент из кучи и помещаем его в отсортированную часть массива.
3. Повторяем шаг 2 до тех пор, пока в куче не останется элементов.
void heapify(int arr[], int n, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest]) {
largest = left;
}
if (right < n && arr[right] > arr[largest]) {
largest = right;
}
if (largest != i) {
swap(arr[i], arr[largest]);
heapify(arr, n, largest);
}
}
void heapSort(int arr[], int n) {
for (int i = n / 2 - 1; i >= 0; i–) {
heapify(arr, n, i);
}
for (int i = n - 1; i >= 0; i–) {
swap(arr[0], arr[i]);
heapify(arr, i, 0);
}
}
Что такое сортировка Шелла с выбором?
Алгоритм, который использует различные интервалы для поиска наименьшего элемента и перемещения его в правильную позицию. Это делает его более эффективным, чем простая сортировка выбором.
Сортировка Шелла с выбором работает следующим образом:
1. Выбираем шаг (gap) равный n/2, где n - количество элементов в массиве.
2. Для каждого шага выполняем сортировку выбором для подмассивов, начинающихся с элементов, отстоящих на расстоянии gap друг от друга.
3. Уменьшаем шаг в два раза и повторяем шаги 2-3 до тех пор, пока шаг не станет равным 1.
4. Выполняем сортировку выбором для всего массива.
Сортировка Шелла с выбором использует различные интервалы для поиска наименьшего элемента и перемещения его в правильную позицию. Это делает ее более эффективной, чем простая сортировка выбором.
void shellSort(int arr[], int n) {
for (int gap = n / 2; gap > 0; gap /= 2) {
for (int i = gap; i < n; i++) {
int temp = arr[i];
int j;
for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
arr[j] = arr[j - gap];
}
arr[j] = temp;
}
}
}
