Гарвард. CS50 на русском. 1. Короткие видео. 7. Быстрая сортировка

Помочь каналу Online Univer:
Приватбанк MasterCard 5168 7423 4807 4000
Webmoney - WMR - R308763080665
Webmoney - WMU - U515924821859
Webmoney - WMZ - Z426274290636

Быстрая сортировка
CS50x – вводный курс по обучению компьютерным наукам и программированию, разработанный Гарвардским колледжом. Данный курс подходит как для средних и продвинутых пользователей, так и для новичков в данной сфере.

Оригинальное видео на официальном канале CS50:

[zimperch]

я посмотрел это видео и теперь нахожусь
справа
от
стены

[EridanSilver]

Цифры в этом видео очень удобно подстроены, каждый раз выходит так, что число, которое ниже пивота - идет по порядку за стеной. Автор просто выстроил числа так, как ему удобно. Если слушать его обьяснение, то, в сценарии, где, например 4 и 3 поменяны местами, у нас в итоге выйдет 1 2 4 3 5 6 7 8 9. Суть в том, что если число ниже пивота, то его сразу ставят в начало. Но если порядок не соблюден, и есть числа меньше, чем это число? Короче видео по факту постраивает цифры.

[РезеновВалентинСергійовичАКІТ]

5:02 меняем 5 и 8. 8 становится последним елементом и сразу же показывают отсортированый масив. Как это произошло?

[pustunt]

О от N в квадрате а не О умноженное на N в квадрате

[vladakymov]

А как на 5:02 8-ка идёт в конец за 9-кой, а потом резко после раскадровки 9-ка оказывается за 8-кой и стена начинает перемещаться по изначальному алгоритму?

[abuzarov]

"О умноженное на n в квадрате" :) :) :)

[largusofdeath]

3-й раз пытаюсь понять быструю сортировку и никак(

[Victor-vxbr]

Почему из-за выбора опорного элемента алгоритм считается нестабильным? Ведь можно взять за правило всегда использовать средний элемент как опорный.

[ashkart]

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

[Оппозиция-чз]

Это не сортировка Хоара, это сортировка Ломуто

[superivan]

не факто что это быстрая сортировка, но работает
#include <iostream>
using namespace std;

void print(int arr[], int n) {
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
}

void swap(int *a, int *b) {
int t = *a;
*a = *b;
*b = t;
}

void quicksort(int arr[], int n) {
if (n == 1)
return;

int wall = 0;
int pivot = arr[n - 1];
for (int i = 0; i < n - 1; i++) {
if (arr[i] <= pivot) {
swap(arr[i], arr[wall]);
wall++;
}
}
swap(arr[n-1], arr[wall]);

quicksort(arr, wall);
quicksort(arr + wall, n - wall);
}

int main()
{
const int SIZE = 50;
int array[SIZE];
for (int i = 0; i < SIZE; i++)
array[i] = rand()%100;

print(array, SIZE);

quicksort(array, SIZE);

print(array, SIZE);

return 0;
}

[РэйЧехов]

На кой хер я это всë учу, я же гуманитарий

[neodva]

Что если скажу есть способ получить О(п) производителность?

[曾玮-dz]

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

[KopoLPedov]

че за бред, сортировке не важно, из какого типа элементов состоит массив, главное - чтоб был определен ключ сортировки

[Negative]

надо спросить у немцев. у них большой опыт в строительстве стен

[ХаткиЧиль]

Ну и в чем эффективность этого алгоритма? Не явно!

[sainthentai]

У меня глупый вопрос здесь когда я меня местами текущий элемент с элементом у которого наименьший индекс. Я меня местами сами значения а индексы оставляю как есть. Или же я меняю индексы местами ?