3672

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

Лекция

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

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

Украинкский

2012-11-05

42.5 KB

48 чел.

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

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

Існують різні методи сортування. Будемо розглядати кожний з методів на прикладі завдання сортування по зростанню масиву з 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();


 

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

75112. Конкурентная стратегия 15.62 KB
  Конкурентная стратегия организации нацелена на достижение конкурентных преимуществ рис. Стратегия лидерства по издержкам низких издержек производство продукции сравнимого товара с минимальными издержками с затратами меньшими чем у конкурентов при осуществлении ценовой конкуренции. Конкурентные базовые стратегии Стратегия наиболее успешна если: на рынке доминирует ценовая конкуренция покупателей много конкурентная борьба на рынке идет в основном вокруг цены; производимый товар стандартен недифференцирован его использование...
75114. Основные части и движущие силы организации 59.28 KB
  В стратегическую вершину входят все управляющие звенья компании. Основная цель управление стратегией и развитием компании управление границами компании. Производственное ядро профессионалы цеха люди выполняющие основную деятельность по профилю компании...
75115. Традиционные модели организационных структур: звёздчатая, линейно-функциональная, дивизиональная, холдинговая, ТНК 2.46 MB
  Под организационной структурой управления понимается совокупность подразделений и уровней управления обеспечивающих развитие компании и ее конкурентоспособность. Оргструктура имеет определенные элементы: структурные подразделения выполняющие определенные функции управления; уровни управления как совокупность подразделений и руководителей занимающих определенную иерархическую ступень; горизонтальные и вертикальные связи обеспечивающие взаимодействие всех подразделений и руководителей; полномочия право руководителей использовать...
75116. Стратегические партнёрства. Управление проектами 46.52 KB
  Управление проектами. Управление проектами заключается в осуществлении и доведении проекта до логического завершения путем организации и управления людьми временем издержками и ресурсами. Функциональная структура управления проектами включает в себя девять разделов: Управление координацией Project Integrtion Mngement. Управление целями Project Scope Mngement.
75117. Бизнес-планирование. Содержание и цель бизнес-плана 21.64 KB
  Бизнес-план краткое точное доступное и понятное описание предполагаемого бизнеса важнейший инструмент при рассмотрении большого количества различных ситуаций позволяющий выбрать наиболее перспективный желаемый результат и определить средства для его достижения. Бизнес-план является документом позволяющим управлять бизнесом поэтому его можно представить как неотъемлемый элемент стратегического планирования и как руководство для исполнения и контроля.
75118. Управление изменениями. Эволюционный и революционный подходы 18.15 KB
  Не затрагивает глубинных качественных изменений в организации а касается оптимизации процессов и повышения общей рентабельности производства. РЕВОЛЮЦИОННЫЕ изменения изменения 2го уровня носят иной качественный характер; сопровождаются переформатированием ряда процессов или организации в целом...
75119. Глобальные менеджеры. Основные профессиональные качества, способы подготовки и условия работы 64.24 KB
  Для того чтобы думать глобально руководителю необходимо изменить свое мышление. Думать глобально означает распространять концепции и модели от двусторонних отношений мы им к одновременному учету многочисленных реалий и отношений профессионально действовать внутри этого более сложного окружения. Эволюция бизнеса к глобально ориентированной деятельности потребует нового мышления и управленческих навыков. Одной из основных стратегических задач функции управления персоналом в многонациональных корпорациях является переориентация узких...
75120. Глобальный менеджмент 57.27 KB
  Революционные трансформации экономических и социальных структур в ХХ веке подвели мир к формированию принципиально нового глобального мирового порядка и адекватной ему системы глобального менеджмента. К системе глобального менеджмента следует отнести систему глобального прогнозирования моделирования и программирования инициированную международными организациями и прежде всего ООН. Речь идет о системе глобального менеджмента пригодную для периода перехода от экономического человека...