SujinLee

Search means finding the desired data among the data list
Sequential Search: Find the data you want by comparing the list one by one from the front

  • Time complexity
    • Worst case: when list length is n, it should be compared n times
    • $O(n)$
  • C++ example
#include<iostream>
#include<cstdio>

using namespace std;

bool sequentialSearch(int* data, int size, int key)
{
	for(int i = 0; i < size; ++i)
	{
		if(data[i] == key)
		{
			return true;
		}
	}
	return false;
}

int main()
{
	int list_s[] = {5,4,3,2,1};
	
	int len = sizeof(list_s) / sizeof(list_s[0]);
	
	if(sequentialSearch(list_s, len, 3))
		cout << "search success" << endl;
	else
		cout << "search fail" << endl;
}

Binary Search: Divide the data to be searched into half to search for the desired data
Divide and Conqure

  • Binary search
    • Divide: Divide the data list into two sublists
    • Conqure
      • data > Medium value: Search for the number to search in the sub-list at the back
      • data < Medium value: Search for the number to search in the previous sub-list

Time Complexity

  • Divide n lists in half every times and perform comparison operations k times until 1
    • n X $\frac { 1 }{ 2 }$ X $\frac { 1 }{ 2 }$ X $\frac { 1 }{ 2 }$ … = 1
    • n X $\frac { 1 }{ 2 }^k$ = 1
    • n = $2^k$ = $log_2 n$ = $log_2 2^k$
    • $log_2 n$ = k
    • In big O notation, k + 1 is the final time complexity (even when it becomes 1, comparison operation is performed once)
      • Eventually, $O(log_2 n + 1)$, 2 and 1, constant are deleted so, $O(log n)$

C++

#include<iostream>
#include<cstdio>

using namespace std;

void binarySearch(int* data, int left, int right, int key)
{
	if(right < left)
	{
		cout << "search fail" << endl;
		return;
	}
	
	int mid = left + (right-left)/2;
	
	if(data[mid] == key)
	{
		cout << "search success" << endl;
		return;
	}
	
	if(data[mid] < key)
		binarySearch(data, mid+1, right, key);
	else
		binarySearch(data, left, mid-1, key);
}

int main()
{
	int list_s[] = {2,5,8,12,16,23,38,56,72,91};
	
	int len = sizeof(list_s) / sizeof(list_s[0]);
	
	binarySearch(list_s, 0, len-1, 23);
	binarySearch(list_s, 0, len-1, 10);
	
	return 0;

}
SujinLee

Quick sort

Quick! Sort Algorithm is fast - low time complexity
Set pivot among the data, and divide data smaller than the pivot to the left and data larger than the pivot to the right
For each left and right, repeat the above operation by calling the same function again using recursive call

quick_sort

  • Main Point : There is a pivot and divides data to the left and right based on the pivot

  • And recursively do the above

  • The pivot is set according to the rule.
    • Usually, the first data or the last data is set as the pivot.

Analysis

  1. Select last data as pivot
  2. Going from left (i) to right, finding a data smaller than the pivot
  3. Exchange the elements for each index i, j
  4. Repeat steps 2 and 3
  5. If it is impossible to proceed 2 or 3 , exchange it with the current pivot.
  6. Now, based on the exchanged pivot, there are only smaller values on the left and larger values on the right.

Time Complexity

$O(nlogn)$

C++ code implementation

#include<iostream>
using namespace std;

void swap(int* a, int* b);

int quickSplit(int* data, int low, int high)  
{  
    int pivot = data[high]; //last element as pivot
    int i = low; // Index of smaller element
    
    for (int j = low; j < high; j++)
    {
        // If current element is smaller than the pivot
        if (data[j] < pivot)
        {
            i++; // increment index of smaller element
            swap(&data[i-1], &data[j]);
        }
    }
    swap(&data[i], &data[high]);
    return i;
}

void quickSort(int* data, int start, int end)
{
	if(start >= end)
		return;
	
	//index means the pivot data's index of the result for quickSplit 
	int index = quickSplit(data, start, end); 
	
	quickSort(data, start, index-1);
	quickSort(data, index+1, end);
	
}
int main()
{
	int list_q[] = {5,3,1,8,7,4,9,2};
	
	int len = sizeof(list_q) / sizeof(list_q[0]);
	cout  << len << endl;
		
	quickSort(list_q, 0, len-1);
	
	for(int i = 0; i < len; ++i)
		cout << list_q[i] << " ";
		
	return 0;
	
}

void swap(int* a, int* b)  
{  
    int temp = *a;  
    *a = *b;  
    *b = temp;  
}
SujinLee

Merge sort

Merge sort: Merge sort is implemented through a Divide-and-Conquer algorithm

  • Algorithm that separates, sorts, and merges(collects) large problems into smaller problems
  • After dividing the elements, merging them again by sorting them

not a Dynamic Programming
Using Recursive call

  1. Split the list in half
    • divide the data list into two equally sized partial lists
  2. Sort each partial list recursively using merge sort
  3. Merging(Collecting) two sub-lists back into one sorted list

Analysis

  • When there are four datas
  • data_list = [1, 9, 3, 2]
    • First, divide by [1, 9], [3, 2]
    • The front part is divided into [1] and [9]
    • Sort and merge [1, 9]
    • Next [3, 2] is divided into [3] and [2]
    • Sort and merge [2, 3]
    • Now merge [1, 9] and [2, 3] together
      • Since 1 <2 [1]
      • Since 9> 2 [1, 2]
      • Since 9> 3 [1, 2, 3]
      • Since there are only 9, [1, 2, 3, 9]

Time Complexity

$O(n log n)$

C++ code implementation

#include<iostream>
#include<cstdio>

using namespace std;

void merge(int * data, int * left, int * right, int medium, int size)
{
	int left_point = 0;
	int right_point = 0;
	int data_point = 0;
	// when left and right both have datas
	while(left_point < medium && right_point < size-medium)
	{
		if(left[left_point] > right[right_point])
		{
			data[data_point] = right[right_point];
			right_point++;
			data_point++;
		}
		else
		{
			data[data_point] = left[left_point];
			left_point++;
			data_point++;
		}
	}
	// only left has data
	while(left_point < medium)
	{
		data[data_point] = left[left_point];
		left_point++;
		data_point++;
	}
	// only right has data
	while(right_point < size-medium)
	{
		data[data_point] = right[right_point];
		right_point++;
		data_point++;
	}
}

void mergeSort(int * data, int size)
{
	if(size == 1)
		return;
	
	int medium = size/2;
	int leftData[medium];
	int rightData[size - medium];
	
	for(int i = 0; i < medium; ++i)
	{
		leftData[i] = data[i];
	}
	
	for(int i = 0; i < size - medium; ++i)
	{
		rightData[i] = data[medium + i];
	}
	
	//Divide
	mergeSort(leftData, medium); 
	mergeSort(rightData, size - medium);
	//Merge
	merge(data, leftData, rightData, medium, size);
	
}
int main()
{
	int list_s[] = {1,9,3,2};
	
	int len = sizeof(list_s) / sizeof(list_s[0]);
	cout  << len << endl;
	
	for(int i = 0; i < len; ++i)
		cout << list_s[i]<< " ";
	cout << endl;
	
	mergeSort(list_s, len);
	
	for(int i = 0; i < len; ++i)
		cout << list_s[i] <<" ";
	cout <<endl;	
		
	return 0;
	
}