Не понимаете, как функционирует метод карманной сортировки массивов?
 

Содержание:

Я - репетитор по информатике и программированию

Здравствуйте! Меня зовут Александр Георгиевич. Я - профессиональный дипломированный репетитор, помогающий школьникам получить наивысший балл на официальных экзаменах ОГЭ и ЕГЭ по информатике, а студентам помогаю стать профессиональными программистами и оказываю им фундаментальную поддержку при подготовке к экзаменам по программированию.

Вы – скорее всего, студент технического вуза и у вас возникли огромные проблемы с пониманием алгоритма карманной сортировки массива данных? Это неслучайно, так как данный метод сортировки не является простым, хотя он и не очень сложен по своей сути.

Да, я понимаю, вы занятый человек, но все-таки уделите 2-3 минуты собственного времени и ознакомьтесь с отзывами моих учеников, прошедших со мной индивидуальную подготовку.

В обязательном порядке загляните на веб-страницу, посвященную моих репетиторским расценкам. Своим потенциальным клиентам я предлагаю минимум 144 варианта взаимовыгодного сотрудничества.

Также ознакомьтесь с моим плотным графиком занятий и постарайтесь подобрать для себя наиболее удобное и комфортное время.

Хотите разобраться фундаментально с методом карманной сортировки массивов? Звоните мне прямо сейчас и записывайтесь на первый пробный урок. Не забывайте о том, что своим клиентам я предлагаю различные территориальные форматы проводимых уроков.

В чем сложность карманной сортировки?

Во-первых, давайте сразу договоримся о терминологии: данный способ сортировки часто в технической литературе синонимично заменяется на «блочная сортировка» или «корзинная сортировка». По факту – это всё названия одного и того же метода сортировки данных.

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

На репетиторском уроке мы детализированно рассмотрим все хитросплетения карманной сортировки, изучим ее характеристики. Напомню, что абсолютная каждая сортировка характеризуется следующими параметрами:

  • Устойчивость.

  • Естественность поведения.

  • Использование операций сравнения.

  • Использование дополнительной памяти.

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

Чтобы узнать алгоритм карманной сортировки – надо записаться ко мне на урок!

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

Если стартовый массив состоит из дробных чисел, то количество карманов может достигать миллионов, что в обязательном порядке негативно скажется на общей производительности программы.

У меня для вас плохая новость: поскольку мы разносим исходные элементы массива по «карманам», то потребуется сортировка этих элементов внутри каждого «кармана», следовательно, вам необходимо знать, как минимум еще один способ упорядочивания массивов. Обычно элементы внутри карманов сортируют одним из представленных, так называемых, простых методов:

Сортировка выбором Сортировка вставками Пузырьковая сортировка

Дальше нужно понимать, что непосредственно реализация на уровне программного кода может существенно отличаться. В одной задаче потребуется использовать динамические массивы для временного хранения элементов в карманах, в другой задаче можно использовать статические массивы, в третьей – потребуется провести реализацию на уровне указателей, в четвертой – потребуется применить объектно-ориентированный подход к данному методу сортировки. То есть нет никакой возможности найти в интернете статью, публикацию, которая на 100% перекрывает все разновидности реализации карманной сортировки.

Сложно? Да, сложно! И не нужно мучить себя интеллектуальными изысками или пытаться найти готовый код в глобальной сети. Все это непродуктивно! Единственным правильным вариантом для вас в сложившейся ситуация станет запись к квалифицированному репетитору по информатике и программированию, который доступно, практично и лаконично разъяснит вам все непонятные моменты.

Хотите понять другие методы сортировки данных? Не вижу никаких проблем!

Метод карманной сортировки данных – вершина айсберга. Очень часто у студентов в вузе присутствует дисциплина, ориентированная на различные методы сортировки данных. В этом случае я предлагаю своим ученикам на рассмотрение следующие способы сортировки данных:

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

Сортировка пузырьком

Сортировка перемешиванием

Сортировка вставками

Сортировка слиянием

Сортировка с помощью двоичного дерева

Сортировка подсчетом

Блочная сортировка

Сортировка Шелла

Пирамидальная сортировка

Плавная сортировка

Быстрая сортировка

Терпеливая сортировка

Stooge sort

Поразрядная сортировка

Сортировка перестановкой

Глупая сортировка

Бисерная сортировка

Гномья сортировка

Сортировка Timsort

Сортировка расческой

Интроспективная сортировка

Случайная сортировка

Блинная сортировка

Также хочу обратить ваше внимание на тот факт, что я знаю на профессиональном уровне 7 языков программирования, следовательно, смогу помочь вам написать код программы, реализующий алгоритм карманной сортировки, на любом из этих языках:

Pascal Delphi C C++ C# Basic VBA

Программный код сортировки и видеорешение

А сейчас я предлагаю вашему вниманию мультимедийный ролик, в котором показана реализация метода карманной сортировки.

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

Условие задачи звучит так:

Дан одномерный целочисленный массив, состоящий из 20 элементов. Элементы массива заполняются с помощью генератора случайных чисел из промежутка [0; 40) и подчиняются равномерному закону распределения. Необходимо вывести элементы исходного массива на экран, затем произвести его упорядочивание по неубыванию, используя метод карманной сортировки, и, затем, распечатать на экран уже отсортированный массив.

  1. program BucketSort;
  2. const
  3.   N = 20;   // сортируемое количество чисел
  4.   K = 4;    // количество карманов
  5. // будем разбивать на 4 кармана:
  6. // 1 карман: числа 0-9
  7. // 2 карман: числа 10-19
  8. // 3 карман: числа 20-29
  9. // 4 карман: числа 30-39    
  10. type
  11.   Tv = array[1..N] of byte;
  12.   Telem = record
  13.     inf : Tv;
  14.     count : byte;
  15.   end;
  16. //-----------------------------------------------
  17. // определение номера кармана для помещения числа
  18. //-----------------------------------------------
  19. function getIndexBucket(pn : byte): byte;
  20. begin
  21.   result := ((pn div 10) + 1);
  22. end;
  23. //-----------------------------------------------
  24. // сортировка каждого кармана методом пузырька
  25. //-----------------------------------------------
  26. procedure sort(pv : Telem);
  27. var
  28.   i, j, tmp: byte;
  29. begin
  30. // используем оптимальный вариант сортировки
  31.   for i := 1 to pv.count - 1 do
  32.     for j := i to pv.count - 1 do
  33.       if(pv.inf[j] > pv.inf[j + 1]) then
  34.       begin
  35.         tmp := pv.inf[j];
  36.         pv.inf[j] := pv.inf[j + 1];
  37.         pv.inf[j + 1] := tmp;
  38.       end;
  39. end;    
  40. //-----------------------------------------------
  41. var
  42.   v : Tv;
  43.   i, j : byte;
  44.   nbuck : byte;
  45.   total : byte;
  46.   buck : array[1..K] of Telem;
  47. begin
  48.   writeln('Исходный массив (ДО сортировки): ');
  49.   writeln;
  50. // массив заполняется случайными числами
  51. // и сразу значения элементов выводятся на экран
  52.   for i := 1 to N do
  53.   begin
  54.     v[i] := random(40);
  55.     write(v[i]:3);
  56.   end;
  57.   for i := 1 to K do
  58.     buck[i].count := 0;
  59. // заполняем карманы из исходного массива
  60.   for i := 1 to N do
  61.   begin
  62.     nbuck := getIndexBucket(v[i]);
  63.     buck[nbuck].count := buck[nbuck].count + 1;
  64.     buck[nbuck].inf[buck[nbuck].count] := v[i];
  65.   end;
  66. // начинается сортировка каждого кармана чисел
  67.   for i := 1 to K do
  68.     sort(buck[i]);      
  69.   total := 0;
  70.   for i := 1 to K do
  71.   begin
  72.     for j := 1 to buck[i].count do
  73.     begin
  74.       total := total + 1;
  75.       v[total] := buck[i].inf[j];
  76.     end;
  77.   end;
  78. // выводим на экран отсортированный массив  
  79.   writeln('После: ');
  80.   writeln;
  81.   for i := 1 to N do
  82.     write(v[i]:3);
  83.   writeln;
  84. end.

Отзывы
моих учеников

Белов
Антон

 
Заниматься очень понравилось, преподаватель прекрасно знает преподаваемый материал. Многое узнал дополнительно, задавал много смежных вопросов и получал профессиональные ответы. Также понравилось, что в процессе урока...

Фомин
Глеб

 
Уф, зачет сдан, я очень рад! А все благодаря этому репетитору. Мне понравилось заниматься с Александром, т к на его уроках нет никакой "воды", все четко по делу, серьезно, дисциплинированно. Также мне понравился стиль...

Крылов
Антон

 
Я не ожидал, что получу 83 балла, думал, максимум 70, а результат меня ошеломил. Вы просто мастер Александр Георгиевич, выражаю вам благодарность большую.

Малышев
Евгений

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

Пахмутов
Кирилл

 
Я не знаю почему, но так сложилось, что я не смог сходу понять логические преобразования и обратился за помощью к профессиональному репетитору Александру Георгиевичу. Результат превзошел все мои ожидания, я досконально...

Орлов
Максим

 
Спасибо большое вам Александр Георгиевич. Было очень интересно и увлекательно решать с вами данные лабораторные. Они оказались не такими сложными, какими они казались изначально. Оказывается процесс программирования...

Фролова
Екатерина

 
Я очень довольна, что познакомилась с таким прекрасным преподавателем как  Александр Георгиевич. Все кто хочет повысить свою успеваемость и знания в этой области, обязательно обратитесь...

Ланцев
Дмитрий

 
Я был очень круто подготовлен. Александр Георгиевич натаскивал меня по полной программе, мы прорерашли более 200 задач по программированию, научились строить выйгрышные стратегии. Я сам виноват, что не повторил...

Иванов
Денис

 
Очень много нового узнал о ДС, Александр Георгиевич показал несколько способов построения бинарного дерева, а также реализацию функций повышенного уровня сложности. Когда шел на экзамен, то абсолютно не волновался, так...

Камю
Константин

 
Я сдал курсовой проект на отлично благодаря помощи репетитора Александра. Он очень доступно дает незнакомый и сложный материал. Понравилось еще то, что он старается все свои объяснения подкреплять визуальными...

Волков
Павел

 
Спасибо вам большое. Да, курсовая была непростой, но я сдал ее на 5-ку. Хочу отметить атмосферу проводимых уроков: во-первых, мы занимались в чистой и опрятной комнате, во-вторых, на уроке стоит здоровая учебная...

Курцева
Мария

 
Я очень довольна результатами)) Меня бы даже устроило бы и 70 баллов. Положительные стороны репетитора: интересно доносит материал, является экспертом в своей области, уроки ориентированы на практику. Из отрицательных...

Трунин
Сергей

 
На редкость сильный репетитор, абсолютно компетентен в преподаваемом предмете, знает язык программирования Turbo Pascal просто "насквозь". Было интересно заниматься и очень познавательно, так как в школе мы ничего этого...

Шамшуров
Денис

 
Спасибо вам большое Александр Георгиевич! Вы практически сделали невозможное - натаскали меня к экзамену по программированию, которое я очень плохо понимал до того, как обратился к вам. Хочу отдельно отметить, что урок...

Павленко
Илья

 
Жаль, что я потерял 1 балл)) Александр Георгиевич подготовил меня очень круто. Когда я увидел задания на экзамене, то понял, что я могу решить абсолютно все. На экзамене я не переживал, т к был уверен в собственных...
Смотреть все отзывы
 
 
 
 
 
 
Авторизация на сайте
 
 
 
Обнаружили
ошибку на сайте?
Занятия по информатике