3672

Алгоритми сортування в одновимірних масивах

Лекция

Информатика, кибернетика и программирование

Алгоритми сортування в одновимірних масивах Найпростіше завдання сортування полягає в упорядкуванні елементів масиву по зростанню або убуванню. Іншим завданням є впорядкування елементів масиву відповідно до деякого критерію. Звичайно як такий критер...

Украинкский

2012-11-05

42.5 KB

45 чел.

Алгоритми сортування в одновимірних масивах

Найпростіше завдання сортування полягає в упорядкуванні елементів масиву по зростанню або убуванню. Іншим завданням є впорядкування елементів масиву відповідно до деякого критерію. Звичайно як такий критерій виступають значення певної функції, аргументами якої виступають елементи масиву. Цю функцію прийнято називати функцією, що впорядковує.

Існують різні методи сортування. Будемо розглядати кожний з методів на прикладі завдання сортування по зростанню масиву з N цілих чисел.

Сортування вибором

Ідея методу полягає в тім, що перебуває максимальний елемент масиву й міняється місцями з останнім елементом (з номером N). Потім, максимум шукається серед елементів з першого до передостаннього й ставиться на N-1 місце, і так далі. Необхідно знайти N-1 максимум. Можна шукати не максимум, а мінімум і ставити його на перше, друге й так далі місце. Також застосовують модифікацію цього методу з одночасним пошуком максимуму й мінімуму. У цьому випадку кількість кроків зовнішнього циклу N div 2.

Обчислювальна складність сортування вибором - величина порядку N*N, що звичайно записують як O(N*N). Це порозумівається тим, що кількість порівнянь при пошуку першого максимуму дорівнює N-1. Потім N-2, N-3, і так далі до 1, разом: N*(N-1)/2.

Приклад 22.1.: Сортування вибором по зростанню масиву A з N цілих чисел.

Console.WriteLine("Введите число ");

int n = Int32.Parse(Console.ReadLine());

int[] a = new int[n + 2];

Random r = new Random();

int i;

for (i = 1; i <= n; i++)

{

a[i] = r.Next(100);

Console.Write(a[i] + " ");

}

Console.WriteLine();

for (i = n; i >= 2; i--)

{

int i1 = 1; //{ m - місце max }

for (int j = 2; j <= i; j++)

if (a[j] > a[i1]) i1 = j;

//міняємо місцями елементи з номером m і номером k}

int x = a[i1]; a[i1] = a[i]; a[i] = x;

for (int k = 1; k <= n; k++)

{

Console.Write(a[k] + " ");

}Console.WriteLine();

}

Console.ReadLine();

Приклад 22.2. : Те ж завдання з одночасним вибором max й min.

Console.WriteLine("Введите число ");

int n = Int32.Parse(Console.ReadLine());

int[] a = new int[n + 2];

Random r = new Random();

int i;

for (i = 1; i <= n; i++)

{

a[i] = r.Next(100);

Console.Write(a[i] + " ");

}

Console.WriteLine();

for (i = 1; i <= n/2 ; i++)

//{max й min шукаються серед елементів з i до n-i+1}

{

int i1 = i; //{ - місце max }

int i2 = i; //{ - місце min }

for (int j = i + 1; j <= n - i + 1; j++)

{

if (a[j] > a[i1]) i1 = j;

if (a[j] < a[i2]) i2 = j;

}

Console.WriteLine(a[i1] + " " + i1 + " " + a[i2] + " " + i2);

//міняємо місцями елементи з номером i1 і номером i}

int x = a[i2]; a[i2] = a[i]; a[i] = x;

//якщо max стояв на місці i, то зараз він на місці i2;

if (i1==i) i1=i2;

//міняємо місцями елементи з номером i1 і номером n-k+1

x = a[i1]; a[i1] = a[n - i + 1]; a[n - i + 1] = x;

for (int k = 1; k <= n; k++)

{

Console.Write(a[k] + " ");

}Console.WriteLine();

}

Сортування обміном (методом "пухирця")

Ідея методу полягає в тім, що послідовно рівняються пари сусідніх елементів масиву. Якщо вони розташовуються не в тім порядку, то робимо перестановку, міняючи місцями пари сусідніх елементів. Після одного такого проходу на останнім місці номер N виявиться максимальний елемент ("сплив" перший "пухирець"). Наступний прохід повинен розглядати елементи до передостаннього й так далі. Усього потрібно N-1 прохід. Обчислювальна складність сортування обміном O(N*N).

Приклад 22.3. Сортування обміном по зростанню масиву A з N цілих чисел. (Базовий варіант)

Console.WriteLine("Введите число ");

int n = Int32.Parse(Console.ReadLine());

int[] a = new int[n + 2];

Random r = new Random();

int i;

for (i = 1; i <= n; i++)

{

a[i] = r.Next(100);

Console.Write(a[i] + " ");

}

Console.WriteLine();

for (i = 1; i <= n - 1; i++)

{

for (int j = 1; j <= n - 1; j++)

{

if (a[j] > a[j + 1])

{

int x = a[j]; a[j] = a[j + 1]; a[j + 1] = x;

}

}

for (int k = 1; k <= n; k++)

{

Console.Write(a[k] + " ");

} Console.WriteLine();

}

Console.ReadLine();

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

Приклад 22.4. : Сортування обміном з перевіркою факту перестановки.

Console.WriteLine("Введите число ");

int n = Int32.Parse(Console.ReadLine());

int[] a = new int[n + 2];

Random r = new Random();

int i;

for (i = 1; i <= n; i++)

{

a[i] = r.Next(100);

Console.Write(a[i] + " ");

}

Console.WriteLine();

int l = n - 1;

int f = 1;

while (f == 1)

{

f = 0;

for (int j = 1; j <= l; j++)

if (a[j] > a[j + 1])

{

int x = a[j]; a[j] = a[j + 1]; a[j + 1] = x; f = 1;

}

l = l - 1;

for (int k = 1; k <= n; k++)

{

Console.Write(a[k] + " ");

} Console.WriteLine();

}

Console.ReadLine();

Наступна модифікація алгоритму сортування обміном виходить при запам'ятовуванні місця останньої перестановки. Якщо при черговому проході останньою парою елементів, які помінялися місцями, були A[i] й A[i+1], то елементи масиву з i+1 до останнього вже коштують на своїх місцях. Використання цієї інформації дозволяє нам зробити кількість пар для наступного проходу рівним i-1.

Приклад 22.5. : Сортування обміном із запам'ятовуванням місця останньої перестановки.

Console.WriteLine("Введите число ");

int n = Int32.Parse(Console.ReadLine());

int[] a = new int[n + 2];

Random r = new Random();

int i;

for (i = 1; i <= n; i++)

{

a[i] = r.Next(100);

Console.Write(a[i] + " ");

}

Console.WriteLine();

int l = n - 1;

while (l>0)

{

int m = 0;

for (int j = 1; j <= l; j++)

if (a[j] > a[j + 1])

{

int x = a[j]; a[j] = a[j + 1]; a[j + 1] = x; m = j;

}

l = m - 1;

for (int k = 1; k <= n; k++)

{

Console.Write(a[k] + " ");

} Console.WriteLine();

}

Console.ReadLine();


 

А также другие работы, которые могут Вас заинтересовать

27069. Синтетический учет материальных запасов 16.14 KB
  Приобретение материальных запасов по фактической сформированной стоимости отражается по дебету соответствующих счетов аналитического учета счета 010500000 Материальные запасы 010531340 010536340 и кредиту счетов 030234730 Уменьшение кредиторской задолженности по приобретению материальных запасов 020834660 Уменьшение дебиторской задолженности подотчетных лиц по приобретению материальных запасов . Безвозмездное получение материальных запасов в том числе по централизованному снабжению распоряжению извещению отражается по дебету...
27070. Документальное оформление, порядок ведения и отражения в учете кассовых операций 16.09 KB
  Для учета кассовых операций применяются приходный кассовый ордер – форма № КО1 расходный кассовый ордер – форма КО2 журнал регистрации приходных и расходных кассовых документов форма КО3 кассовая книга форма КО4 книга учета принятых и выданных кассиром денежных средств форма КО5. Все операции по поступлению и расходованию денежных средств кассир записывает в кассовую книгу которая должна быть пронумерована прошнурована и опечатана сургучной печатью. В дебет его записывают поступление денежных средств в кассу а в кредит выбытие...
27071. Инвентаризация материальных запасов 15.97 KB
  Инвентаризация материальных запасов Методические указания по инвентаризации имущества и финансовых обязательств от 13 июня 1995 г . Инвентаризационной комиссией в описях заполняются данные о фактическом наличии товарноматериальных ценностей. Результаты проведенной инвентаризации материальных запасов отражают в инвентаризационной описи сличительной ведомости по объектам нефинансовых активов ф. При хранении материальных запасов в разных изолированных помещениях у одного материально ответственного лица инвентаризация проводится...
27072. Учет прочих доходов и расходов. Назначение счета «Прочие доходы и расходы» и его структура. Организация аналитического учета для формирования отчета «О прибылях и убытках» 23.5 KB
  Назначение счета Прочие доходы и расходы и его структура. Доходы и расходы организации формирующие финансовый результат ее деятельности В соответствии с Положением по бухгалтерскому учету Доходы организации ПБУ 9 99 введено в действие с 1 января 2000 г. Прочие поступления зачисляются на счет 91 Прочие доходы и расходы Прочими доходами признаются в учете: штрафы пени неустойки за нарушения условий договоров возмещения причиненных организации убытков – в отчетном периоде в котором судом вынесено решение об их взыскании или они...
27073. Архитектура SCM-систем 174.21 KB
  Объяснить что такое ERP Что такое архитектура Как архитектура относится к классу данной системы ИСТОРИЯ В начале 60х в США начались работы по автоматизации управления запасами. В результате активного роста крупносерийного и массового производства товаров народного потребления и торговли после Второй мировой войны стало очевидно что использование математических моделей планирования спроса и управления запасами ведет к существенной экономии средств замороженных в виде запасов и незавершенного производства. Управление складами в современных...
27074. Информация в бизнесе. Инф поддержка в бизнесе. Класс-ция корпоративных информационных систем 711.94 KB
  Что такое бизнес Бизнес – это экономическая деятельность направленная на систематическое получение прибыли от производства и или продажи товаров оказания услуг. Тк бизнесэто коммерческиориентировнная деятельность в конкурентной среде. Деятельность предприятия происходит в реальном физическом мире в котором протекают преимущественно энергетические процессы. Деятельность связанная с управлением предприятием анализ ситуаций выбор вариантов и иная интеллектуальная деятельность продуктом которой являются оценки и принятие решений...
27075. Системы электронного документооборота 139.67 KB
  Системы электронного документооборота 1. Что такое документооборот Документооборо́т это частный способ информационной системы обеспечивающее взаимодействие. Системы электронного документооборота обладают рядом преимуществ к числу которых можно отнести возможность однократной регистрации электронного документа параллельное выполнение необходимых операций с отслеживанием ответственного за их исполнение а также наличие эффективно организованной системы поиска документа и развитой системы отчетности. Электронный документооборот является...
27076. Стр-ра КИС. Основные функциональные задачи 921.26 KB
  Главной задачей такой системы является информационная поддержка производственных административных и управленческих процессов бизнеспроцессов формирующих продукцию или услуги предприятия то есть необходимо рассмотрение всех бизнеспроцессов и как следствие поддержка основных бизнеспроцессов. Технологическая стрра инф системы. 3уровневая архитектура: 1 подсистемы сбора хр накопления данных В каком виде может существовать Распределенные системы данных; БДболее жестко поддерживают структуру; КорпХДболее абстрагированная...
27077. Управленческие автоматизированные ИС. Концепция интегрированной управленческой АИС 249.57 KB
  Интегрированная АСУ обеспечивает согласованное и координированное решение задач с учетом временной и уровневой иерархии за счет разделения общей задачи управления по фазам планирования регулирования учета анализа а также временной иерархии задач внутри каждой фазы. В ИАСУ обеспечиваются координация процессов исследования хода производства оперативного и перспективного планирования и адаптация системы за счет изменения состава и взаимосвязей между задачами а также характера взаимодействия между ее компонентами. История развития ERP 6070...