3. 선형 검색
-
선형검색은 자료가 정렬되어있지 않거나, 어떤 정보도 없어 하나씩 찾아야 할 때 유용함.
-
구조체
c언어에서는 새로운 자료형을 정의할 수 있다.
아래와 같이 하면 person.name / person.number 로 접근 가능
typedef struct
{
string name;
string number;
}
person;구조체를 정의하는 코드가 js를 배우던 내겐 특이하다.
이후 person을 배열에 넣으려면 아래처럼 할 수 있다.
int main(void)
{
person people[4];
people[0].name = "EMMA";
people[0].number = "617–555–0100";
}4.버블정렬
버블정렬은 O(n^2) 이며 또한 오메가(n^2)이다.
하지만 직관적이다. 배열이 작을 때 유리할 듯.
n개의 요소가 들어간 배열이라면,
n-1번 동안 반복하는데,
index가 0부터 n-2가 될때까지 진행되야 하기 때문이다.
(n-1)*(n-1)
5.선택정렬
선택정렬은 O(n^2) 이며 오메가(n^2)이다. 버블과 같다.
선택 정렬은 가장 작은 숫자를 찾고, 그다음 작은 수를 찾고, 그 다음 작은수를 찾아가며, 가장 작은 수를 인덱스0부터 1,2,3,4 차곡차곡 바꿔주는 정렬이다.
n-1번 동안, 숫자를 전부 하나씩 들여다 보기 때문에 (n-1)
n^2이 나오게 된다.
이를 업그레이드 시킨 것이 퀵소트가 아닌가 싶다.
6.정렬 알고리즘의 실행시간
위에서 버블정렬을 O(n^2) Omega(n^2)라고 했다.
그러나 이를 개선할 여지가 있다.
'만약 아무런 swap이 없다면 동작을 멈춘다'라는 조건을 하나 넣는 것이다.
7. 재귀 (recursion)
구글에 recursion을 검색하면 재밌는 결과가 하나 나온다.ㅎㅎ
재귀는 계속적으로 자기(함수)를 부르는 것이다.
- 언제 return할지 조건문이 있어야함
- return을 하는 시작으로 계속 다시 밖으로 나오면서 함수를 마저 실행함, 이를 잘 이용할 수 있어야 함.
8. 병합정렬
- if 배열의 요소가 하나라면 return
- 왼쪽을 정렬한다.
- 오른쪽을 정렬한다.
- 둘을 합친다 (merge, 병합)
O(nlogn) 이며 Omega(nlogn)이다.'
theta라는 새로운 표기법이있다. 빅오와 오메가가 같을 때 쓴다.
theta(n^2) = selection sort
theta(nlogn) = merge sort
사실 n log n 이 이론적으로 또는 그래프에서 빠르다는건 알았지만 막상 비교영상을 보니 정말 충격적이었다.
https://www.edwith.org/boostcourse-cs-050/lecture/119026/
마지막 부분에 sort비교영상이 있다.
병합정렬은 최악을 많이 개선했다. 대신 O(n)은 절대 나올 수 없다. 모든것엔 trade-off가 있기 마련, 상한선을 개선하면 하한선에서의 손해를 감수해야 한다. 등가교환의 법칙.
