Join Yalantis and get a $1000 sign-in bonus! React.js, React Native, Python, Java, DevOps, BА. Apply now!
×Закрыть

Про метод пузырька

Здравствуйте. Изучал тут просторы Интернета по различным алгоритмам сортировок и нашел по-моему самую легкую: метод пузырька. И там приводится его код:



int main(int argc, char* argv[])
{
    int arr[8] = {35, 698, 74, 81, 67, 11, 184, 89},i, flag;

for (; ;){
       flag = 0;
       for (i = 7; i>0; i--){
          if (arr[i] < arr[i-1]) {
             /* Обмен значениями смежных элементов */
             swap (arr[i],arr[i-1]);
             flag++;
          }
       }
       /* Если массив упорядочен, то обмена не происходит и
       мы выходим из цикла */
       if (flag == 0) break;
       for ( i=0;i<8;i++) {
          cout << arr[i] << ' ';
       }
       cout << '\n';
    }
    getch();
return 0;
}

Вот у меня возник вопрос следующему участку в этом коде:



swap (arr[i],arr[i-1]);

Я понимаю, что эта функция производит обмен смежными значениями элементов массива, но вот она вроде бы не существует в языке С++. А самому написать данную функцию не получилось (почему-то значения не меняются, когда я из функции выхожу).

можете посоветовать похожую функцию или же написать реализацию данной функции?

👍НравитсяПонравилось0
В избранноеВ избранном0
LinkedIn
Допустимые теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter
Допустимые теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter
парни напишите мне блок схемы...по методу пузырька...в 7 ворде:) плизз

maxRICH8238@gmail.com

Радикс — это сортировка только для чисел (или похожих обьектов).

Лексикографический порядок тут тоже прокатит. Это посимвольная сортировка. Но в целом да, радикс для связных списков применим больше, нежели для массивов.

Мне понятна суть, вот только имеет ли смысл рассказывать про сложность алгоритма и тд, человеку у которого «не получилось написать» swap?

Понятна твоя мысль)) Извини.

На самом деле нету stable, in place алгоритма сортировки с O (nlogn) временем

Есть близкий метод: Batcher’s odd-even mergesort. У него сложность O (n * [log n] ^2), он хоть и неадаптивен, но неплохо приспособлен под очень большие базы.

Ну, как мне помнится, поразрядная сортировка (radix sort) требует времени всего лишь O (n).

Радикс — это сортировка только для чисел (или похожих обьектов). А пузырек, heap sort, merge sort, quick sort и прочие могут сортировать любые обьекты которые можно сравнить, или другими словами на множестве которых введено отношение полного порядка.

Я думаю вы обращали внимание что в зависимости от размера таблицы nested loops иногда работают быстрее чем merge/hash join (пример когда больший степень N бьет меньшую по коэф. K)

если нет, то вот вам к примеру статья oracle-online-help.blogspot.com/...sort-merge.html

silverwolf, если тебе непонятен смысл нотации, пропускай ее и не цепляйся зазря там, где это без надобности.

Мне понятна суть, вот только имеет ли смысл рассказывать про сложность алгоритма и тд, человеку у которого «не получилось написать» swap?

2hellip
Она требует k * N и поэтому в зависимости от реализации, она может быть медленее N^2 / 2 (реальная сложность пузырька) к примеру для 4х числел х64 на х64 проце, при реализации 8 бит на 1 бакет, у вас будет 8 * 4 = 32 радикса и 4 * 4 / 2 пузырька = 8

не говоря уже о читабельности и простоте реализации, отладки и поддержки такого кода

silverwolf, если тебе непонятен смысл нотации, пропускай ее и не цепляйся зазря там, где это без надобности.

На самом деле нету stable, in place алгоритма сортировки с O (nlogn) временем

Ну, как мне помнится, поразрядная сортировка (radix sort) требует времени всего лишь O (n).

Вообще-то алгоритм сортировки пузырьком взимает достойную плату за свою простоту

А самому написать данную функцию не получилось

Какая плата, какое О?

P.S. Странно что не отметился Аноним с тушенкой.

На самом деле нету stable, in place алгоритма сортировки с O (nlogn) временем, так что у сортировки пузырьком вполне есть своя ниша, как это ни странно звучит.

Вообще-то алгоритм сортировки пузырьком взимает достойную плату за свою простоту — у него время прогона O (n2). Будь осторожен с размерами массивов.

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


int old = arr[i];
arr[i] = arr[i-1];
arr[i-1] = old;

или если уж очень хочется функцией надо использовать ссылки на значения

void swap(int &a1, int &a2)
{
    int old = a1;
    a1 = a2;
    a2 = old;
}



void swap(int& element1, int& element2)
{
    int temp;

temp=element1;
    element1=element2;
    element2=temp;
}

Подписаться на комментарии