1. ' Bubble Sort ' vs ' Merge Sort '

[첫번째 수업시간]

교수님 曰

	Array	Sorted Array	Linked List	Binary Tree	Balanced Binary Tree
Insert (삽입)	Slow	Slow	Fast	Fast	Fast
Search (검색)	Slow	Fast	Slow	Slow	Fast
Delete (삭제)	Fast	Slow	Fast	Fast	Fast

그렇다면 Sorted Array , Linked List, Binary Tree, Balanced Binary Tree 는 각각 무엇일까?

1. Sorted Array ?

  = A sorted array is an array data structure in which each element is sorted in numerical, alphabetical, or some other order, and placed at equally spaced addresses in computer memory.  라고 위키피디아에서 정의를 내린다.

  즉, Sorted array 는 컴퓨터 메모리 상에서 숫자,글자 혹은 다른 것들을 기준으로 정렬된 데이터 구조이다.

  Sorted Array의 종류로는  Selection sort, Bubble Sort, Insertion Sort, Merge sort, Quicksort, heapsort, counting sort 등이 있다.

 (출처 : https://en.wikipedia.org/wiki/Sorted_array)

2. Linked List ?

 = a linked list is a linear collection of data elements, called nodes pointing to the next node by means of pointer.

   즉, 다음 노드까지 포인터를 이용하여 연결된 선형 데이터 모음이다. (출처 : https://en.wikipedia.org/wiki/Linked_list)

  이런 식이란 소리다. 데이터와 다음 갈 곳을 바라보고 있는 포인터의 결합으로 데이터가 구조화 되어 있다는 것이다.

3. Binary Tree ?

 = a binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child 

     and the right child. (출처 : https://ko.wikipedia.org/wiki/%EC%9D%B4%EC%A7%84_%ED%8A%B8%EB%A6%AC)

    즉, 각 데이터마다 2개의 Child를 갖고 있다는 것이다. 노드간 부모-자식의 관계란 소리다.

  이런 식이란 소리다.

  이 이진트리(Binary Tree)는 한글 위키피디아가 있어 해석하기가 수월했다(ㅠㅠ) 

  조금 더 이진트리에 대해서 알아보자. 

  1) 구성 : 

     - 방향 간선 : 부모에서 자식으로 가는 경로                   - 루트 노드 : 부모가 없는 노드 (위에서 보면 가장 위에 있는 2 라고 보면 된다)

     - 단말 노드 : 자식이 없는 노드 ( 맨 밑에 있는 5, 11, 4 )     - 각 노드의 깊이 : 루트 노드에서 자신까지 가는 길이

     - 레벨 : 특정 깊이를 갖는 노드의 집합                        - 트리의 높이 : 루트 노드에서 가장 깊이 있는 노드까지의 길이

     - 형제 : 같은 부모를 갖는 노드

   2) 탐색방법 : 이진트리를 탐색하는 방법에는 여러가지가 있다

     ① in-order : 왼쪽 자식노드 → 내 노드 → 오른쪽 자식노드

     ② pre-order : 내 노드 → 왼쪽 자식노드 → 오른쪽 자식노드

     ③ post-order : 왼쪽 자식노드 → 오른쪽 자식노드 → 내 노드

     ④ level-order : 내노드 → 내 노드로부터 깊이 1인 노드들 → 내 노드로부터 깊이 2인 노드들 … → 내 노드로부터 깊이 N인 노드들

4. Balanced Binary Tree ?

 =  a self-balancing (or height-balanced) binary search tree is any node-based binary search tree that automatically keeps its height (maximal number of levels below the root) small in the face of arbitrary item insertions and deletions.

  즉, 균형 이진트리는 삭제나 삽입 시 자동으로 그 높이(루트 노드로부터 내려갈 수 있는 최대 레벨)를 최소한으로 유지시키는 이진코드이다. 

                                                

         [균형이 맞지 않는 트리의 예]                                                                    [높이 균형을 맞춘 후의 상태]   

자 여기까지 교수님께서 말씀하신 데이터 저장 방법들에 대해서 알아보았다.

이제 본격적으로 데이터 구조의 느리고 빠름 & Bubble sort, Merge sort에 대해 알아보자!

※ Array에 입력 시 시간에 영향을 미치는 것 ?

  1. Size of array

  2. Array가 Full 인가?

  3. Speed of Computer

+ Full Array 시 New item을 입력할 때  => 새로운 곳에 기존 데이터를 복사하고 새 데이터를 붙여야하므로 시간에 영향을 미친다. 

■ Bubble Sort & Merge Sort

 1. Bubble Sort : Quadratic Time. 즉 ∝   이란 것이다.

 여기서 Wagner 교수님은 자신의 컴퓨터 속도를 참고해서 데이터 구조를 처리하는데 걸리는 시간이 

이라고 하셨다.   

   

 여기서 앞의 계수인  1/200,000 은  각 컴퓨터 스펙마다 다르다. 고스펙일 수록 더욱 작아지는 것이다.

 이 계수가 데이터 처리 속도에 영향을 미치기는 하지만 뒤에 있는 n^2이 훨 씬 중요하다

그렇다면 Bubble sort는 어떻게 작동하는 것일까?

 이런 Array가 있다고 해보자. 이런 Array를 정렬해보자

①  5 / 7 / 1 / 6 / 2    : 5개의 데이터를 갖고 있는 array 이다. 1항과 2항인 5와 7일 compare 한다. 5<7이므로 바꾸지 않는다

②  5 / 1 / 7 / 6 / 2    : 같은 방법으로 7과 1을 compare 한다. 7>1이므로 바꿨다.

③  5 / 1 / 6 / 7 / 2    : 같은 방법으로 7과 6을 compare 한다. 7>6이므로 바꿨다.

④  5 / 1 / 6 / 2 / 7    : 같은 방법으로 7과 2를 compare 한다. 7>2이므로 바꿨다. 

여기까지 진행하니 Array의 가장 오른쪽 항은 7로 되었다.

이 방법을 반복해서 진행하면 결국 

1 / 2 / 5 / 6 / 7 로 정렬될 것이다.

그렇다면 처음 5 / 7 / 1 / 6 / 2  Array가  1 / 2 / 5 / 6 / 7 으로 정렬되는데 총 몇 번의 과정을 거쳤을까?

일반적으로 넓혀서 생각해보자

N개의 데이터를 갖는 Array가 있다면 

  의 과정을 거친다.

이 결과를 잘 살펴보면 ?

  

n^2 과 관련이 있다 !  = n이 커질 수록 더욱 더 ! 

위에서 살펴본 Quadratic Time 이란 것이다.

2. Merge Sort 

=  time 이다

( 왜 이런지는 아직 안알려주셨다....)

오늘은 여기까지...