[Algorithm/알고리즘] 정렬(Sorting)과 재귀(Recursion)

Some Observations on Sorting

- Efficient management of space: in-place sorting

- Efficiency is generally measured in terms of number of comparisons and/or number of exchange operations

 

 

Methods of Sorting

(1) Simple methods

- Bubble sort

- Selection sort

- Insertion sort

- Roughly n^2 comparisons

 

(2) Fast methods

- Merge sort

- Heap sort

- Quick sort

- Roughly nlogn comparisons

 

 

Bubble Sort 버블정렬

데이터집합을 순회하면서 집합 내의 이웃 요소들끼리의 교환을 통해 정렬

 

Number of comparisons: (independent of the original ordering and the values)

Number of moves: 

Mmax는 C의 3배.

 

 

Selection Sort 선택정렬

전체 원소들 중에서 기준 위치에 맞는 원소를 선택하여 자리를 교환하는 방식

Number of comparisons: (independent of the original ordering)

Number of moves: 

 

 

Insertion Sort 삽입정렬

데이터 집합을 순회하면서 정렬이 필요한 요소를 뽑아내어 이를 다시 적당한 곳에 삽입해 나가는 방법

Number of comparisons: 

Number of moves: 

 

Recursion 재귀

- Procedure that calls itself

- Termination condition to stop recursion

- Multiple recursions: if a procedure calls itself multiple times

- Mutual recursion: if multiple procedures call each other recursively

 

단어장
permutation: 순열
iteration: 반복