늘.. 남이 정리해둔 것만 보던 생활을 접고 정리도 할겸 미디엄을 시작하기로 한 2019년
첨 올리는 글은 바로 정렬 알고리즘 정리이다..
정렬 알고리즘을 알기 전에 Big O 와 각 Big O 표기법의 성능에 대해 간단히 알아보자.
- big O : 알고리즘의 퍼포먼스를 나타내는 표기법
- 시간복잡도, 공간복잡도로 나뉘어지며 시간복잡도는 알고리즘 수행시간에 대한 퍼포먼스 표기이며, 공간복잡도는 알고리즘을 수행할 때 필요한 공간(리소스)에 대한 퍼포먼스 표기이다.
- 시간복잡도는 아래 순으로 퍼포먼스를 판단하며 값이 작을 수록 빠른 시간에 결과가 나온다는 말 ( 퍼포먼스가 좋다 )
- O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!) < O(nⁿ)
1. Bubble Sort
버블정렬은 가장 쉬운 알고리즘이다.
처음부터 끝까지 자신과 자신의 다음 데이터를 비교해가면서 가장 큰 수를 맨 뒤로 보내는 식으로 동작하는 알고리즘이다.
- 배열 전체를 순회하며 비교하기 때문에 시간복잡도는 O(n²)이며
- 배열 하나만 사용하기 때문에 공간복잡도는 O(1) 이다.
2. Selection Sort
선택정렬이라고도 불리며, 배열의 가장 작은 값을 가지는 인덱스를 찾아서 가장 작은 값을 앞에서부터 채워나가면서 정렬하는 방식.
- for loop 2번을 통해 배열을 훑고, swap하는 방식으로 시간복잡도는 O(n²)
- 공간복잡도는 O(1) 이다.
3. Insertion Sort
삽입정렬이라고 불리며, 최소값을 찾아서 이하 배열들의 원소와 비교하여 자신이 위치해야할 곳을 찾아 삽입해나가며 정렬하는 방식이다.
- for loop 혹은 while loop를 2중첩으로 구현되어 시간복잡도는 O(n²)
- 공간복잡도는 O(1) 이다.
4. Merge Sort
병합정렬이라고도 불리며, 배열을 반씩 쪼개서 하나의 원소를 가진 배열로 만든 후 비교를 통해 각 배열을 정렬하여 병합하여 최종 정렬된 배열을 구하는 정렬방식이다.
- 배열을 반씩 쪼개며 정렬을 하고 다시 그것을 병합하는 방법으로 시간복잡도는 O(nlogn)이다.
- 공간복잡도는 O(n) 이다.
5. Quick Sort
병합정렬과 어찌보면 비슷한 로직으로 돌아가는 정렬이며, 기준이 되는 기준점을 가지고 앞/뒤 배열로 쪼개서 각 앞/뒤배열을 기준값 보다 작은수를 앞으로 몰고 기준값보다 큰 수를 재귀함수를 통해 뒤로 몰아가는 정렬방식
- 배열을 기준점으로 나누어 해당 기준값을 기준으로 좌,우의 배열을 다시한번 탐색하며 정렬하는 방식으로 시간복잡도는 O(nlogn)
- 공간복잡도는 O(n) 이다.
공부하면서 정리했는데, 완벽히 손코딩을 할 정도는 아닌것같아서 자주 복습하기위해 자료를 남기며 마칩니다.
