Algorithm

Searching

•

순차 탐색

•

이분 탐색 Binary Search 

Sorting

어떤 데이터들이 주어졌을 때 이를 정해진 순서대로 나열하는 것

정렬 알고리즘 성능

평균적인 경우가 가장 이상적으로 보이지만 알고리즘이 복잡해질수록 평균적인 경우는 구하기가 매우 어려워짐 → 최악의 경우로 알고리즘의 성능을 파악하는 것이 좋다.

안정 정렬

동일한 값에 기존 순서가 유지

•

거품 정렬 Bubble Sort

•

삽입 정렬 Insertion Sort

•

병합 정렬 Merge Sort

•

기수 정렬 Radix Sort

불안정 정렬

동일한 값에 기존 순서가 유지되지 않음

•

선택 정렬 Selection Sort

•

퀵 정렬 Quick Sort (in place 기준)

•

Search

이분 탐색 Binary Search

이분 탐색 Binary Search

병합 정렬 Merge Sort

병합 정렬 Merge Sort

퀵 정렬 Quick Sort

퀵 정렬 Quick Sort

선택 정렬 Selection Sort

선택 정렬 Selection Sort

삽입 정렬 Insertion Sort

삽입 정렬 Insertion Sort

거품 정렬 BubbleSort

거품 정렬 BubbleSort

Reference

파이썬으로 정렬 알고리즘 구현하기

탐색과 정렬 알고리즘은 서로 뗄레야 뗄 수 없는 사이다. 원하는 값을 찾을 때까지 값을 차례로 살펴보는 순차탐색(sequential search)은 데이터가 정렬되어 있지 않아도 사용할 수 있지만 $O(n)$이다. 데이터를 절반씩 버리면서 원하는 값을 찾아나가는 이진탐색(binary search) 은 $O(\log n)$으로 시간복잡도가 낮지만 데이터가 순서에 맞게 정렬되어 있어야 한다는 제약이 있다. 따라서 효율적인 정렬 알고리즘이 필수다.

http://ejklike.github.io/2017/03/04/sorting-algorithms-with-python.html