정렬 알고리즘

https://en.wikipedia.org/wiki/Sorting_algorithm

Sequential Sort

• 1대1로 두 원소를 순차적으로 비교하는 방식
• 가장 기초적인 방법

void Switching(int& x, int& y)
{
	//실제로 바껴야 하기 때문에 참조형을 씀
	int temp{};
	temp = x;
	x = y;
	y = temp;
}
//순차 정렬
//time complexity : n^2
//space comlexity : 
void SequentialSort(int input[], int size)
{
	for (int i = 0; i < size; i++)
	{//0!n-1
		for (int j = i+1; j < size; j++)
		{//n-1,n-2,n-3,n-4.....1=> (n-1)n/2[sigma] 그럼 O(n^2)
			if (input[i] > input[j])
			{
				Switching(input[i], input[j]);
			}
		}
	}
}

---

Selection Sort

• 가장 작은 것을 찾아서 앞으로 보내는 정렬 방식
• 반복 작업을 줄이는 방법

//sellectionSort
//SPACE COM : O(1)
//TIME COM : 0(n^2)
void SelectionSort(int input[], int size)
{
	for (int i = 0; i < size; i++)
	{
		int minIndex{ i }; 
		//첫번째 원소를 최대값 또는 최소값으로 써야함
		for (int j = i; j < size; j++)
		{
			if (input[j] > input[minIndex]);
		} //최소값의 위치를 minIndex에 저장함(4
		if (minIndex != i)
		{//최소값이 MININDEX가 아니면 바꾸면됨
			Switching(input[i], input[minIndex]);
		}
	}
}

---

Bubble Sort

• 두 개씩 짝을 지어서 정렬
• 0,1버블 1,2버블 그 다음 버블을 쭉 비교
• 가장 큰 것은 마지막으로 이동
• 0,1버블부터 마지막 빼고까지 모두 비교함

//bubbleSort
//spcae : o(1)
//time : n-1 ,n-2,n-3.....1 => (n-1)n/2=> n^2
void BubbleSort(int input[], int size)
{
	for (int i = 0; i < size-1; i++) //하나 적은것 까지만 데려옴
	{
		for (int j = 0; j <size-1-i; j++)
			//하나 적은 것부터 0까지 줄어야함 
			//i를 또 빼야함(비교하는 대상이 계속 줄어들어야 하기 때문)
		{
			if (input[j] > input[j + 1])
			{
				Switching(input[i], input[j + 1]);
			}
		}
	}
}

---

BIG O Worst Case

성능 측정은 최악의 경우를 가장 중요하게 생각하고 계산해야함

---

insertion sort

• 찾아서 삽입하는 방식

//insertion sort
//spcae com : o(1)
//time com : n , n-1,n-2...1 =>o(n^2)
void InsertionSort(int input[], int size)
{
	for (int i = 1; i < size; i++)
	//0을 n개 까지 만들어냄 그런데 1개일때는 필요없음 
	{
		int j = i;
		//내 위치를 찾아서 들어가야함
		//앞으로만 가거나 안 갈 수 있음
		int target = input[i];
		//비교대상보다 클 때까지 갈 수 있음
		//타겟을 목적지로 잡아둠
		while (--j>=0&&target<input[j])
			//이동할 값이 비교대상보다 작으면 이동하고 크면 멈춤
		{
			input[j + 1] = input[j];//뒤에있는것을 앞에 있는 것으로 넣으면됨
			input[j] = target;
			//타켓을 저장한 이유는  target값을 고정이기 때문(바꾸기 안쓰기 위해서)
		}
		//j는 0번까지만 갈 수 있음
	}
}

---

Divide and conquer

• computational thinking
• 갈라치기
• von Neumann
• 가운데를 기준으로 나누고(divide) 비교하고 남은 것을 합침(conquer)
• 재귀함수
• divide를 위한 코드

mergeSort(array,start,end)
{
//base case
if(start>=end)
{//예외처리 위한 것
	return;
}

//recursive case
int half = (시작+끝)/2;

mergeSort(array,start,half);
mergeSort(array,half+1,end);

conquer(array,start,half,end);

merge(0,4)>>m(0,2)>>m(o,1)>>m(0,0)>>basecase>>
m(0,1)시점에서 두번째 mergeSort로 들어감>>m(1,1)>>
base case>>함수 끝남>>m(0,2)로 돌아감>>m(2,2)>>
base case>>함수 끝남>>m(0,4)로 돌아감>>m(3,4)

• conquer지점 : 베이스 케이스를 만나고 돌아왔을 떄 conquer
• conquer sudo code

conquer(int input[],int start,int half,int end)
{
	while(집합)
    {
    	왼쪽 / 오른쪽에서 작은 것 선택
    }
	if(왼쪽에 남으면)
    왼쪽에 남은 것 있으면 붙인다
    else if(오른쪽에 남으면)
    오른쪽에 남은 것 있으면 붙인다
}

• 임시 배열이 필요함 ( 합쳐서 넣을 공간 )

merge sort

void Merge(int input[], int start, int end, int temp[])
{
	//첫번째 부분에서 시작하는 i 
    //두 번째 부분에서 시작하는 j
	//temp 부분의 k
    int i = start;
    int j = half+1;
    int k = 0;
    //왼쪽블럭과 오른쪽 블럭 병합
    while(i<=half && j<=end)
    {
    	if(input[i]<input[j])
        { temp[k++] = input[i++];}
        else
        { temp[K++] = input[j++];}
        //먼저 집어넣고 증가
    }
    
    //남은 블럭 병합
    while(i<=half) //왼쪽 남은 블럭
    {temp[k++] = input[i++]}
    //쭉 가져오는 것
    while(j<=end)
    {temp[k++] = input[j++]}
   //원래 배열로 복사
  for (int i = start, k = 0; i <= end; ++i, ++k)
	{
		input[i] = temp[k++];
	}
}


void MergeSort(int input[], int start, int end, int temp[])
{
	//base case
    if(start>=end)
    {
    	end;
    }


	//recursive case
    int half = (start+end)/2;
    
    MergeSort(input,start,half,temp);
	MergerSort(input,half+1,end,temp);
_____여기까지 divide_________________________    

Merge(input,start,half,end,temp);

• divide algorithm

  10개를 1/2로 나눔 그걸또 1/2로나눔 그걸 또 1/2로 나누고 반복하다 1이 될 때가지 나눔 >> log(2)10

• conquer algorithm

  while : n번 + for문(원래 배열로 복사) :n번 >> 2n번

• logn x 2n(모든 나눈 경우마다 merge가 발생하기 때문)

• time comp : o(nlogn)

• space comp :

---

QuickSort

• 가장 많이 사용되는 알고리즘
• divide & conquer 개념 이용

1. 배열의 특정 값을 피벗으로 지정함
2. 중심 축보다 작은 것은 왼쪽으로, 큰 것은 오른쪽으로
3. 피벗을 기준으로 나눔 (중심값의 위치는 고정이 아님)
4. 왼쪽과 오른쪽을 비교해서 만날때까지(피벗이 바뀔 때가지) 정렬 1차가 완료
5. 다시 피벗을 기준으로 나눔
6. 나눠진 블록 안에서 피벗을 기준으로 나누고 위 작업을 반복

• merge와 divide가 같이 일어나는 버전
• pivot을 잘못 잡으면 n번이 나올 수 있음 >> n^2
• pivot을 어떻게 선택하는 지가 중요함
• 보편적인 경우는 center를 잡음

void QuickSort(int input[], int left, int right) 
{
	int i = left;
	int j = right;
	int pivot = input[(left + right)/2];//중심
	do {
		while (input[i]<pivot)
		{
			i++;
		}
		while (input[j]>pivot)
		{
			j--;
		}
		if(i<=j)//크로스가 일어나면 바꿀 필요가 없음
		{
			Switching(input[i], input[j]);
				i++;
				j--;
			
		}
	} while (i <= j);
	//pivot인덱스가 필요없음 
	//반복이 끝나면 i보다 j가 무조건 크기 때문
	if (left < j) {
		QuickSort(input, left, j);
	}
	if(i<right){ QuickSort(input, i, right); }
	
	//base case는 i=j인경우인데 이 경우라면 그냥 종료됨 while문 때문에

}