여정 3. 정렬 알고리즘 정리.

정렬이 왜 필요할까? 무언가를 찾을때 순서대로 배치해두거나, 같은 부류 끼리 색인을 해놓으면, 찾기가 훨씬 수월할 것이다. 그래서 필요한것이 정렬이고, 이를 컴퓨터가 자동으로 처리하게 하는게 알고리즘 일 것이다.

 

그러니, 정렬알고리즘 들에 대해 공부하고 구현해 보자.

 

나무위키를 참조하였습니다.

 

우선은

O(n²)인 것

즉대개 계산 시간이 정렬할 자료의 수의 제곱에 비례해서 늘어난다. 즉, 1만 개를 1초에 정렬하면 10만 개를 정렬하는 데에는 100초 정도가 필요하다.

버블정렬(bubble sort)

은 간단하고 무식합니다.  2 3 1 5 4 7 6 9 8 이라는 숫자를 오름차순 버블정렬하려면 어떻게 하면 될까요?

 

step1. 2 와 3을 비교한다 ->  그대로 둔다.     2 3 1 5 4 7 6 9 8 

 

step2. 3 과 1을 비교한다. - > 둘을 바꾼다.   2 1 3 5 4 7 6 9 8 

 

step3. 2 와 1을 비교한다. -> 둘을 바꾼다.    1 2 3 5 4 7 6 9 8 

 

↓계속

 

이런 식으로 두개씩 비교하여 바꾸거나, 그대로 둔다.

 

당연히 데이터가 많아질수록 실행횟수가 기하급수적으로 늘어난다.

 

최대 실행 횟수는 다음과 같다.

 

$\frac{n(n-1)}{2}$

 

위의 경우는 n=9 이므로 최대 실행횟수는 36회이다. 최소는물론 0회(정렬되어있는상태)이다.

 

거의 모든 상황에서 최악의 성능을 보여준다. 단, 이미 정렬된 자료에서는 1번만 돌면 되기 때문에 최선의 성능을 보여준다. 이미 정렬된 자료를 정렬하는 바보짓을 왜 하냐는 의문이 들 수 있지만, 정렬 알고리즘은 자료가 정렬되어 있는지 아닌지는 모르고 작동하기 때문에 의미가 있다.
가장 손쉽게 구현하여 사용할 수 있지만, 만들기가 쉽고 직관적일 뿐이지 알고리즘적 관점에서 보면 대단히 비효율적인 정렬 방식이다. 다른 몇 가지 정렬 방식과 비교해도 효율이 매우 좋지 않다. 실제 개발에서는 쓰지 않는다.

https://gmlwjd9405.github.io/2018/05/06/algorithm-bubble-sort.html

https://gmlwjd9405.github.io/2018/05/06/algorithm-bubble-sort.html

시간 복잡도가 좋지않아, 쓰이지 않는다. 한마디로, 데이터를 찾는데 시간이 오래 걸린다.

https://hanamon.kr/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-time-complexity-%EC%8B%9C%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84/

또 한가지 알아야 할 개념은 Big-O이다.

Big-O 표기법

👉 시간 복잡도를 표기하는 방법
Big-O(빅-오) ⇒ 상한 점근
Big-Ω(빅-오메가) ⇒ 하한 점근
Big-θ(빅-세타) ⇒ 그 둘의 평균
위 세 가지 표기법은 시간 복잡도를 각각 최악, 최선, 중간(평균)의 경우에 대하여 나타내는 방법이다.

👉 가장 자주 사용되는 표기법은?
빅오 표기법은 최악의 경우를 고려하므로, 프로그램이 실행되는 과정에서 소요되는 최악의 시간까지 고려할 수 있기 때문이다.“최소한 특정 시간 이상이 걸린다” 혹은 “이 정도 시간이 걸린다”를 고려하는 것보다 “이 정도 시간까지 걸릴 수 있다”를 고려해야 그에 맞는 대응이 가능하다.

👉 시간 복잡도 최선의 경우를 고려한 경우
결과를 반환하는 데 최선의 경우 1초, 평균적으로 1분, 최악의 경우 1시간이 걸리는 알고리즘을 구현했고, 최선의 경우를 고려한다고 가정하겠다.이 알고리즘을 100번 실행한다면, 최선의 경우 100초가 걸린다.만약 실제로 걸린 시간이 1시간을 훌쩍 넘겼다면, ‘어디에서 문제가 발생한 거지?’란 의문이 생긴다.최선의 경우만 고려하였으니, 어디에서 문제가 발생했는지 알아내기 위해서는 로직의 많은 부분을 파악해야 하므로 문제를 파악하는 데 많은 시간이 필요하다.

👉 시간 복잡도 중간의 경우를 고려한 경우
평균값을 기대하는 시간 복잡도를 고려한다면 어떨까?알고리즘을 100번 실행할 때 100분의 시간이 소요된다고 생각했는데, 최악의 경우가 몇 개 발생하여 300분이 넘게 걸렸다면 최선의 경우를 고려한 것과 같은 고민을 하게 된다.

👉 시간 복잡도 최악의 경우를 고려한 경우
극단적인 예이지만, 위와 같이 최악의 경우가 발생하지 않기를 바라며 시간을 계산하는 것보다는 ‘최악의 경우도 고려하여 대비’하는 것이 바람직하다.따라서 다른 표기법보다 Big-O 표기법을 많이 사용한다.Big-O 표기법은 ‘입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가?’를 표기하는 방법이다.

👉 Big-O 표기법의 종류
O(1) / O(n) / O(log n) / O(n2) / O(2n)

https://noahlogs.tistory.com/27

O(1)은