CS50. Семінар 3

GDB - це засіб для налагоджування програм або "дебагер". Налагоджування або "дебаг" загалом - це процес пошуку та усунення помилок у коді. Для того, щоб знайти помилки, треба якимось чином дізнатись, як виконується програма та які значення мають змінні в будь-який момент роботи програми. Це можна легко зробити за допомогою спеціального інструмента - дебагера.

Одним із них і є GDB: завдяки ньому можна не використовувати printf кожного разу, коли ви хочете знайти помилку.

GDB працює лише на виконуваних файлах. Для запуску GDB, просто наберіть у командному рядку:

gdb [ім'я програми]

Відкриється командний рядок для дебагера програми. У ньому ви можете вводити одну з наступних команд (і не лише їх):

• run [аргументи командного рядка програми]

  Запустити програму.

• break [номер рядка/ім'я функції]

  Встановити точку зупинки програми на певному рядку або функції.

• next

  Перейти на наступний рядок, не заходячи всередину функцій.

• step

  Перейти на наступний рядок. Якщо на рядку виклик функції - зайти всередину неї.

• list

  Вивести код програми навколо поточного місця.

• print [змінна]

  Вивести значення змінної на екран.

• info locals

  Вивести усі локальні (поточні) змінні: всередині циклу, функції абощо. Зручно, щоб не вводити підряд декілька команд print

• display [змінна]

  Виводитиме значення змінної на кожному кроці дебагу.

• help 

  Показати список усіх команд GDB.

Запуск дебагера:

gdb [ім'я програми]

• break 

  У програмі caesar є одна функція, main. Встановимо точку зупинки програми на функції main:

  

• run

  Запустимо програму caesar з аргументом "3":

  

• print

  Припустимо, нам треба перевірити значення argc:

  

• next

  Продовжимо покроково виконувати програму далі:

  

  Тут відбувається присвоєння значення змінній key. Перевіримо, яке значення вона має на цьому рядку:

  

  Чому "0"? Адже ми ввели "3"? Річ у тому, що присвоєння відбувається саме на цьому рядку. Команду просто ще не було виконано. Щоб її виконати, треба ввести next ще раз:

  

  Коли ми знову введемо next, то почне виконуватись функція GetString(). Вона очікує на введення даних з клавіатури, тому треба щось ввести:

  

  Виконавши команду next ще раз, зайдемо всередину циклу і опинимося на умові:

  

• info locals

  Як програма повинна виконуватись далі? Щоб дізнатись це, нам потрібно переглянути значення усіх локальних змінних (тих, що існують в межах циклу):

  

  Умову буде виконано, і, увівши next ще декілька разів, ми виконаємо інструкції всередині циклу, і опинимося на початку наступної ітерації циклу:

  

  Зверніть увагу, що змінилось значення змінної text.

• list

  Подивимось код біля того рядка, де ми зупинились:

  

• display

  Щоб відловити момент, коли змінюється значення змінної text, необхідно використати команду display:

  

• help 

  Приклад:

  

Необхідно знайти у масиві число 7:

Спершу, подивимось в середину масиву (чи array[3] більше, менше або рівне 7?):

Значення 6 менше ніж шукане число 7, тому ліву частину масиву можна відкинути і продовжити пошук у правій частині. Тепер перевірятимемо значення array[5]:

Оскільки 9 більше за шукане 7, шукатимемо далі у лівій половині:

Ось ми і знайшли шукане значення, всього лише за 3 кроки!

Для семи вхідних значень розв'язок можна знайти у найгіршому випадку за 3 кроки. Для чотирьох мільярдів вхідних значень - лише за 32 кроки! (2^32 ~ 4 000 000 000)

Вправа

Нижче подано заготовку функції бінарного пошуку. Необхідно доповнити її власним кодом:

/**
*  Повертає значення true, якщо значення value є в масиві
*  values, інакше - false.
*/

bool search(int value, int values[], int n)
{
  // Встановити значення верхньої і нижньої межі пошуку
  int lower = 0;
  int upper = n - 1;
  
  while(lower <= upper)
  {
    // Що треба робити тут?
  }
  
  return false;
}

/**
*  Повертає значення true, якщо значення value є в масиві
*  values, інакше - false.
*/

bool search(int value, int values[], int n)
{
  // Встановити значення верхньої і нижньої межі пошуку
  int lower = 0;
  int upper = n - 1;
  
  while(lower <= upper)
  {
    // Знайти середину
    int middle = (upper + lower) / 2;
    
    //Порівняти значення в середині з шуканим
    if(values[middle] == value)
    {
      return true;
    }
    else if (value[middle] < value)
    {
      lower = middle + 1;
    }
    else if (value[middle] > value)
    {
      upper = middle - 1;
    }
  }
  
  return false;
}

• Найкращий випадок - Ω(1)
• Найгірший випадок - O(log n)
• Вхідний список повинен бути відсортованим

1. Пройти по всьому списку значень, міняючи місцями сусідні значення, якщо вони не впорядковані;
2. Повторити крок 1, якщо було зроблено хоча б один обмін.

Застосуємо алгоритм сортування бульбашкою, щоб впорядкувати за зростанням такий масив:

Прохід 1

Здійснюємо три обміни (червоним виділено елементи, що порівнюються):

Прохід 2

Оскільки на проході 1 ми здійснили обмін, то робимо ще один прохід (тут також здійснюємо три обміни):

Прохід 3

Лише один обмін:

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

Прохід 4

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

Ініціалізувати лічильник
повторювати
{
  Встановити лічильник на 0
  
  Пройти в циклі весь масив
    якщо n-те значення більше за n+1-ше
      обміняти їх місцями
      збільшити лічильник  
} поки (лічильник > 0)

Вправа

Нижче подано заготовку функції сортування бульбашкою. Необхідно доповнити її власним кодом:

void sort(int array[], int n)
{
  //Циклічний прохід по масиву
  for(int k = 0; k < n - 1; k++)
  {
    //Оптимізація: перевірка на здійснення обмінів
    int swaps = 0;
    
    //обміняти сусідні елементи, якщо вони не впорядковані
        
    //Пройтися по масиву
    
    if(!swaps)
      break;
  }
}

void sort(int array[], int n)
{
  //Циклічний прохід по масиву
  for(int k = 0; k < n - 1; k++)
  {
    //Оптимізація: перевірка на здійснення обмінів
    int swaps = 0;
    
    //обміняти сусідні елементи, якщо вони не впорядковані
      //Пройтися по масиву
      for(int i = 0; i < n - 1 - k; i++)
      {
        //Перевірити елементи i та i+1
        if(array[i] > array[i+1])
        {
          int temp = array[i+1];
          array[i+1] = array[i];
          array[i] = temp;
          swaps++;
        }
      }
    if(!swaps)
      break;
  }
}

• Найгірший випадок - O(n²)
• Найкращий випадок - Ω(n)
• Примітивний і повільний алгоритм сортування.

1. Знайти найменше невпорядковане значення.
2. Поміняти це значення місцями з першим невпорядкованим значенням.
3. Повторити з кроку 1, якщо ще є невпорядковані значення.

Впорядкуємо за зростанням масив, зображений нижче.

На початку роботи алгоритму, всі значення є невпорядкованими.

Шукаємо у масиві найменше невпорядковане значення. Це - 2, тому ми міняємо його місцями із першим невпорядкованим значенням 3:

Далі ми обробляємо лише невідсортовану частину:

Отже, масив упорядковано.

Для i в межах від 0 до n-2
  min = i
  для j в межах від i+1 до n-1
    якщо array[j] < array[min]
      min = j
    якщо min != i
      обмін array[min] та array[j]

Вправа

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

/**
* Сортування масиву із використанням сортування вибором.
*/

void sort(int array[], int size)
{
	//Пройти по масиву
	for(int i = 0; i < size - 1; i++)
	{
		//Найменший елемент у відсортованій частині
		
		//Пройти по невідсортованій частині масиву
		
			// Знайти наступний найменший елемент
			
		//Обміняти місцями
		int temp = array[i];
		array[i] = smallest;
		array[position] = temp;
	}
}

/**
* Сортування масиву із використанням сортування вибором.
*/

void sort(int array[], int size)
{
	//Пройти по масиву
	for(int i = 0; i < size - 1; i++)
	{
		//Найменший елемент у відсортованій частині
		int smallest = array[i];
		int position = i;
		
		//Пройти по невідсортованій частині масиву
		for (int k = i + 1; k < size; k++)
		{
			// Знайти наступний найменший елемент
			if(array[k] < smallest)
			{
				smallest = array[k];
				position = k;
			}
		}
		
		//Обміняти місцями
		int temp = array[i];
		array[i] = smallest;
		array[position] = temp;
	}
}

• Найгірший випадок - O(n²)
• Найкращий випадок - Ω(n²)
• Простий і легкий в реалізації алгоритм, проте менш ефективний ніж сортування включенням.

Для кожного невпорядкованого елемента n:

1. Визначити позицію n у впорядкованій частині масиву
2. Зсунути впорядковані елементи вправо так, щоб звільнити місце для n
3. Вставити n у впорядковану частину масиву.

Для і в межах від 0 до n - 1
  element = array[i]
  j = i
  поки ((j > 0) та array[j-1] > element)
    array[j] = array[j - 1]
    j = j - 1
  array[j] = element

Як і в алгоритмі сортування вибором, спершу всі елементи масиву є невпорядкованими.

На першій ітерації алгоритму, ми беремо перше значення із масиву, і вставляємо його у список впорядкованих значень

Далі, на другій ітерації алгоритму, ми беремо перше значення у невідсортованій частині масиву, і починаємо шукати для нього підходяще місце у вже відсортованій частині масиву. Оскільки 5 > 3, то ми вставляємо нове значення праворуч від старого.

На наступній ітерації, ми беремо значення 2. Оскільки 2 < 5 та 2 < 3, необхідно вставити 2 ліворуч 3 та 5. Щоб зробити це, ми посуваємо трійку та п'ятірку праворуч, і вставляємо двійку на її місце:

Оскільки наступний елемент, 6, - найбільше значення у відсортованій частині масиву, вставляємо її праворуч від 5.

Останній елемент, 4, - менший за 5 та 6, але більший за 3 - тому ми вставляємо його між 3 та 5.

Масив відсортовано.

• Найгірший випадок - O(n²)
• Найкращий випадок - Ω(n)
• Алгоритм ефективний, коли потрібно відсортувати частково впорядкований масив.

Для масиву з n елементів на вході:

• Якщо n < 2 - закінчити виконання (масив з одного чи нуля елементів вже впорядкований)
• Інакше:
  1. Відсортувати праву половину масиву
  2. Відсортувати ліву половину масиву
  3. Злити відсортовані половини.

Розбиваємо на половинки, доки у кожному підмасиві опиниться лише один елемент.

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

Необхідно доповнити функцію merge своїм кодом так, щоб працювала функція sort.

void sort(int array[], int start, int end)
{
	if(end > start)
	{
		int middle = (start + end) / 2;
		sort(array, start, middle);
		sort(array, middle + 1, end);
		merge(array, start, middle, middle+1, end);
	}
}

void merge (int array[], int start_1, int end_1, int start_2, int end_2)
{
    // Виконайте злиття відсортованих підмасивів, використовуючи допоміжний масив temp
}

• Найгірший випадок - O(nlogn)
• Найкращий випадок - Ω(nlogn)
• Алгоритм сортування злиттям працює значно швидше за інші, розглянуті у цьому конспекті (як видно з графіка нижче)