데이터 구조 기말 준비

Graph 5문제

Sort 5문제 

AVL 2문제

Huffman 1문제

Hash 1문제

STL 1문제 --> stack이나 vector 둘 중에 하나 선택해서 하는 문제

 

 

Selection -- >가장 작은 놈 찾아서 가장 앞으로

Insertion -- > 1번부터 n번까지 한 명 한 명 가면서 앞에 애들이랑 비교해서 가야할 위치에 Insert

Bubble -- > 앞 뒤로만 비교해서 가장 뒤로 보

1) 각 사이클 첫 원소 = 최솟값으로 박아놓고 시작.

2) 첫 원소 빼고 돌면서 작은 애가 나오면 걔가 최솟값으로 됨.

  (   2)는 사실 첫 원소보다 작은 애가 있는지 보려고 하는 거  )

3) for int j 사이클에서 항상 마지막에는 첫 원소와 가장 작다고 나온 원소의 위치를 교환한다

  (중간에 첫 원소보다 작은 게 나왔으면 그 원소랑 자리를 바꿀 것이고,

    아니라면 자기자신과 자리를 바꿈 )

 

++나는 숫자로 해서 했는데, 원소의 인덱스로 해야할 땐, 숫자를 교환하고 돌리는 게 아니라 인덱스 번호를 돌리는 거라고 생각해야함

ex)  for (int k = j + 1; k < n; k++)

           if (a[k].s_id < a[min_i].s_id)

                min_i = k;

 

 

 

---

K+1 인덱스에 temp를 넣는 이유

K는 앞에 뭐가 있는지 찔러보는 막대기 느낌.

앞에 가면 안 되는 게 찔리면 내 자리에 있음.

근데 막대기는 앞으로 갔으니까 한 칸 땡김.

 

 

---

 

마지막 반복문 시작이  [ n-1 ] 인 이유

adjust할 때 마지막으로 간 가장 큰 값은 이미 sorted이므로

걔 빼고 하려고 

 

따라서 내가 for 문에서 n으로 쓸거면 adjust할 때 b 1 i-1로 해야함. 안 그러면 제일 뒤로 보낸 게 제일 앞으로 감

 

 

 

---

1. pivot = a[left]임  << a[0]으로 실수함

    do > do while에서 (i<=right) 빼먹음

2. 시작할 떄 if 리턴

    do > do while에서 (i<=right) 빼먹음

   + do while 에서 while 뒤에는 ; 붙임.