소트

Overview

입출력 연산만 함
슈퍼컴퓨터 : 버스를 광케이블로 연결

서로 관련이 다 있음

Array, Linked List : 선형구조(프로그래밍 적 얘기)
tree, graph : 비선형구조
Heap :

스택 : top만 접근 허용해야 함
큐 : front, rear만 접근 허용해야 함

 

트리
논리적 관계(부모-자식간에 직접적 관계로 구성)
형제와 링크가 되어 있다면 그건 트리가 아님(부모가 같으면 형제)

트리의 순회방법
preorder
inorder
postorder

 

partial order
트리상에서 자식부터 부모로 갈 때 정렬되어 있는 경우
큰값->작은값(min트리)
total order

 

sorting

compare, swap
1차원 데이터만 대소비교 가능.
복소수는 대소비교를 할 수 없다.
기준이 2개 이상이면 대소비교를 할 수 없다.

 

bubble sort
인접한 2개끼리 비교하며 교환
마지막 결과값에 대해서는 비교를 수행할 필요 없음.

문제분해 n => n-1:1
compare : n-1
1번에 reading연산
swap : 0~n-1 (common work)
3번에 writing연산

 

selection sort
문제분해 : n => 1:n-1
compare : n-1(common work)
비교 연산이 많이 필요
swap : 0~1

 

insertion sort
정렬되어 있다는 가정에서 추가로 정렬
minMAX와 maxMIN값을 찾아서 그 사이에 값을 추가한다.
compare & shift연산
문제분해 : n=> 1:n-1
compare : 0~n-1
swap : 0~1
shift(common work)

 

shell sort
1/3로 나누어서

 

Merge Sort
Devide and Conquer전략 : 분해는 쉽다.
나눠서 1등을 찾는 방식
공간(자원)이 많이 필요
합병하는 과정이 common work

 

Quick Sort
분해 과정을 어렵게 합치는 과정을 쉽게
pivot : 아무거나 정함.

 

Radix Sort
기준이 여러개 있을 때 사용. (중요한 기준(MSD), 덜 중요한 기준(LSD)으로 나누어져 있음.)
덜 중요한 기준을 먼저 적용. (예 : 헌법에 의해 법률이 변경됨.)
bucket : 갈 위치가 결정되어 있음, bucket 자체가 정렬되어 있음.

 

기타 이야기

engineer
선입관을 가지면 안됨.
상대적(상황에 따라 다름)